The Real-Time Cost of Timing Uncertainty: Consensus and Failure Detection

In real distributed systems, processes may have only inexact information about the amount of real time needed for primitive operations such as process steps. This thesis studies the effect of this timing uncertainty on the real-time behavior of distributed systems. We consider a semi-synchronous model in which the amount of real time between process steps is known to be in the interval and every message is known to be delivered within time d of when it is sent. We use as a measure of the timing uncertainty. We first study the problem of reaching agreement in the presence of f omission failures. An easily derived lower bound on the time required is (f + 1)d and a simple upper bound is (f + 1) Cd. By adapting the algorithm of Attiya, Dwork, Lynch and Stockmeyer, we show an upper bound of 4(f + 1)d. We also consider the case of f arbitrary, or Byzantine, failures, and give an interesting algorithm that runs in time 3(f + 1) Cd, which is much faster than previously known. Finally, we define a more realistic model of message links by limiting and quantifying their "capacity". We prove nearly matching upper and lower bounds on the time to detect stopping failures in systems with such links.