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

In real distributed systems, processes mayhave 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 #c 1 ;c 2 # and every message is known to be delivered within time d of when it is sent. We use C = c 2 =c 1 as a measure of the timing uncertainty.