[Back]

U. Schmid, B. Weiss, I. Keidar:
"Impossibility Results and Lower Bounds For Consensus Under Link Failures";
SIAM JOURNAL ON COMPUTING, 38 (2009), 5; 1912 - 1951.

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.

Fault-tolerant distributed algorithms, consensus, transient link failures, impossibility results, lower bounds, assumption coverage analysis

http://dx.doi.org/10.1137/S009753970443999X