Bounds on the time to reach agreement in the presence of timing uncertainty

. Upper and lower bounds are proved for the time complexity of the problem of reaching agreement in a distributed network in the presence of process failures and inexact information about time. It is assumed that the amount of (real) time between any two consecutive steps of any nonfaulty process is at least c 1 and at most c 2 ; thus, C = c 2 =c 1 is a measure of the timing uncertainty. It is also assumed that the time for message delivery is at most d. Processes are assumed to fail by stopping, so that process failures can be detected by timeouts. A straightforward adaptation of an (f + 1)-round round-based agreement algorithm takes time (f + 1)Cd if there are f potential faults, while a straightforward modification of the proof that f + 1 rounds are required yields a lower bound of time (f + 1)d. The first result of this paper is an agreement algorithm in which the uncertainty factor C is only incurred for one round, yielding a running time of approximately 2fd + Cd in the worst ca...