Faculty of Electrical Engineering
Haifa 32000, Israel
Instituto de Matemáticas
Mexico City, D.F. 04510, Mexico
We perform a model-independent analysis of the consensus problem in terms of abstract connectivity properties of layering functions. By defining particular layerings in specific models, we derive several popular (and some new) lower bounds and impossibility results for consensus in various classical models. These results are often stronger in the sense that they apply to the submodel induced by the layering. The proofs obtained in this way are also simpler and more direct than existing ones. Moreover, the analysis is done in a uniform fashion and demonstrates the fundamental common structure of the consensus problem in the presence of failures.
The analysis is then extended to general decision problems (1-resilient in the asynchronous models, t-rounds in the t-resilient synchronous model), providing a characterization of solvability of decision problems in the style of [O. Biran, S. Moran and S. Zaks, "Tight Bounds on the Round Complexity of Distributed 1-solvable Tasks," Theoretical Computer Science, Vol. 145 (1995) pp. 271-290], which, for some of the models, is given for the first time.
paper (10 pages), in Proc. 17th ACM Symposium on Principles of Distributed Computing (PODC), p. 133-142, June 1998.