טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentShraer Alexander
SubjectTimeliness, Failure-Detectors and Consensus Performance
DepartmentDepartment of Computer Science
Supervisor Professor Idit Keidar


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 α-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 ◊S and the Ω 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.