15/2011 : Synchronous consensus under hybrid process and link failures

RR Number

15/2011

Comment

Published version of RR 58/2009.

Conference

Theoretical Computer Science, Volume 412, Issue 40, 16 September 2011, Pages 5602-5630

Author(s)

Martin Biely, Ulrich Schmid, Bettina Weiss

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.

Bibtex

@article{BSW11:hyb,
title = "Synchronous consensus under hybrid process and link failures",
journal = "Theoretical Computer Science",
volume = "412",
number = "40",
pages = "5602 - 5630",
year = "2011",
issn = "0304-3975",
doi = "DOI: 10.1016/j.tcs.2010.09.032",
url = "http://www.sciencedirect.com/science/article/pii/S0304397510005359",
author = "Martin Biely and Ulrich Schmid and Bettina Weiss",
}

Download

Get TCS_8014_final.pdf - Adobe PDF-format, (898.07 KB; posted at September 12 2011)