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

摘要

In real distributed systems, processes may have only inexact information aboutthe 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 sub 1, c sub 2) and every message is known to be delivered within time d of when it is sent. We use C = c sub 2/c sub 1 as a measure of the timing uncertainty. We first study the problem of reaching agreement in the presence of failures. A simple argument derived from the case of synchronous processes shows that at least time (f + 1) d is required to tolerate f failures, while time (f + 1) Cd is sufficient to tolerate f stopping or omission failures by directly simulating the rounds of any synchronous consensus algorithm. We narrow this gap for omission failures, building on the nearly optimal algorithm of Attiya, Dwork, Lynch, and Stockmeyer which tolerates only stopping failures.