9/2009 : Impossibility Results and Lower Bounds for Consensus under Link Failures

RR Number

9/2009

Conference

SIAM Journal on Computing 38(5), p. 1912-1951, 2009

Author(s)

Ulrich Schmid, Bettina Weiss, Idit Keidar

Abstract

We provide a suite of impossibility results and lower bounds for the required number of processes and rounds for synchronous consensus under transient link failures. Our results show that consensus can be solved even in presence of $O(n^2)$ moving omission and/or arbitrary link failures per round, provided that both the number of affected outgoing and incoming links of every process is bounded. Providing a step further towards the weakest conditions under which consensus is solvable, our findings are applicable to a variety of dynamic phenomena such as transient communication failures and end-to-end delay variations. We also prove that our model surpasses alternative link failure modeling approaches in terms of assumption coverage.

Bibtex

@article{SWK09,
  TITLE =	 {Impossibility Results and Lower Bounds for Consensus under Link Failures},
  AUTHOR =	 {Ulrich Schmid and Bettina Weiss and Idit Keidar},
  JOURNAL =      {SIAM Journal on Computing},
  volume = {38},
  number = {5},
  pages = {1912-1951},
  YEAR =	 2009,
}

Download

Get paper.pdf - Adobe PDF-format, (531.22 KB; posted at January 09 2009; )