[Back]


Publications in Scientific Journals:

M. Biely, U. Schmid, B. Weiss:
"Synchronous consensus under hybrid process and link failures";
Theoretical Computer Science, 412 (2011), 40; 5602 - 5630.



English abstract:
We introduce a comprehensive hybrid failure model for synchronous distributed systems, which extends a conventional hybrid process failure model by adding communication failures: Every process in the system is allowed to commit up to l_s send link failures and experience up to l_r receive link failures per round here, without being considered faulty; up to some l_sa <= l_s and l_ra <= l_r among those may even cause erroneous messages rather than just omissions. In a companion paper (Schmid et al. (2009) [14]), devoted to a complete suite of related impossibility results and lower bounds, we proved that this model surpasses all existing link failure modeling approaches in terms of the assumption coverage in a simple probabilistic setting. In this paper, we show that several well-known synchronous consensus algorithms can be adapted to work under our failure model, provided that the number of processes required for tolerating process failures is increased by small integer multiples of l_s, l_r, l_sa, l_ra. This is somewhat surprising, given that consensus in the presence of unrestricted link failures and mobile (moving) process omission failures is impossible. We provide detailed formulas for the required number of processes and rounds, which reveal that the lower bounds established in our companion paper are tight. We also explore the power and limitations of authentication in our setting, and consider uniform consensus algorithms, which guarantee their properties also for benign faulty processes.

Keywords:
Fault-tolerant distributed systems; Byzantine agreement; Hybrid failure models; Link failures; Uniform consensus; Authentication


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1016/j.tcs.2010.09.032


Created from the Publication Database of the Vienna University of Technology.