58/2009 : Synchronous Consensus under Hybrid Process and Link Failures

RR Number

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 process faulty; up to 0≤l^sa≤l^s and 0≤l^ra≤l^r links may even generate erroneous messages rather than just omissions. In a companion paper (Schmid, Weiss and Keidar, 2009), 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 most existing 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 presence of unrestricted link failures and mobile 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, and that even non-optimal algorithms can benefit from hybrid failure models. We also explore the power and limitations of authentication in presence of link failures, and consider uniform consensus algorithms, which guarantee the consensus properties also for benign faulty processes.

Bibtex

@techreport{BSW09:hyb,
  author =       "Martin Biely and Ulrich Schmid and Bettina Weiss",
  title =        "Synchronous Consensus under Hybrid Process and Link Failures",
  institution =  "Technische Universit{\"a}t Wien, Institut f{\"u}r Technische Informatik",
  address =      "Treitlstr. 1-3/182-2, 1040 Vienna, Austria",
  type =         "Research Report",
  year =         "2009",
  number =       "58/2009"
}

Download

Get paper.pdf - Adobe PDF-format, (426.66 KB; posted at September 13 2010; )