[Back]

U. Schmid:
"Synchrony and Time in Fault-Tolerant Distribiuted Algorithms";
Talk: FORMATS 2010 (Formal Modeling and Analysis of Times Systems), Klosterneuburg, Austria (invited); 2010-09-08 - 2010-09-10; in: "Formal Modeling and Analysis of Timed Systems", Springer, 6246 (2010), ISBN: 9783642152962.

In 1985, Fischer, Lynch and Paterson published their celebrated impossibility of solving distributed agreement (consensus) in purely asynchronous distributed systems with crash failures. Synchrony requirements, i.e., constraints on the occurrence of certain events in a distributed system, are hence mandatory for being able to solve interesting distributed computing problems. Timing requirements are the most obvious, though not the only, possibility to express synchrony conditions. We will survey existing partially synchronous distributed computing models and their ability to circumvent impossibility results, and explore the role of time and clocks in designing fault-tolerant distributed algorithms in such models.