Technical Report MSC-2006-15

TR#:MSC-2006-15
Class:MSC
Title: Timeliness, Failure-Detectors, and Consensus Performance
Authors: Alexander Shraer
Supervisors: Idit Keidar
PDFMSC-2006-15.pdf
Abstract: Consensus is a widely-studied fundamental problem in distributed computing, theory and practice. Roughly speaking, it allows processes to agree on a common output. We are interested in the performance of consensus algorithms in different timing models. It is known that consensus is not solvable in a completely asynchronous environment, and a completely synchronous one is often too restrictive for real systems. Therefore, many middle-ground models have been previously suggested. One known model is the Eventually Synchronous model, in which the system is asynchronous for an arbitrary period of time and then becomes synchronous. Another method is assuming that each process has an unreliable failure detector oracle, which eventually gives some level of indication to the process about the failed processes or about a common non-faulty leader.

We study the implications that various timeliness and failure detector assumptions have on the performance of consensus algorithms that exploit them. We present a general framework, GIRAF, for expressing such assumptions, and reasoning about the performance of indulgent algorithms (algorithms that tolerate an arbitrary period of asynchrony). This framework addresses several shortcomings of a previously known framework - RRFD. We use GIRAF to revisit the notion of oracle (or model) reducibility and define $\alpha$-reducibility that takes time complexity of the reduction into account. We investigate several interesting indulgent models (all weaker than Eventual Synchrony) using GIRAF and give upper and lower bounds for the number of rounds needed to reach consensus in these models. Our results have several implications to the understanding of indulgent systems. First, we prove that Eventual Synchrony is not needed to achieve optimal consensus performance. We prove that the $\Diamond$S and the $\Omega$ failure detectors that are known to be equivalent in the literature, are very different when it comes to performance of consensus algorithms. We show an algorithm that works in an oracle-free model that is weaker than Eventual Synchrony but achieves very close performance to what is known to be possible in Eventual Synchrony. Finally, we show that several recently suggested models, and even much stronger models, are too weak to allow bounded-time consensus decision.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2006/MSC/MSC-2006-15), rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2006
To the main CS technical reports page

Computer science department, Technion