H. Attiya et al., BOUNDS ON THE TIME TO REACH AGREEMENT IN THE PRESENCE OF TIMING UNCERTAINTY, Journal of the Association for Computing Machinery, 41(1), 1994, pp. 122-152
Upper and lower bounds are proved for the time complexity of the probl
em of reaching agreement in a distributed network in the presence of p
rocess failures and inexact information about time. It is assumed that
the amount of (real) time between any two consecutive steps of any no
nfaulty process is at least c1 and at most c2; thus, C = c2/c1 is a me
asure of the timing uncertainty. It is also assumed that the time for
message delivery is at most d. Processes are assumed to fail by stoppi
ng, so that process failures can be detected by timeouts. A straightfo
rward adaptation of an (f + 1)-round round-based agreement algorithm t
akes time (f + 1)Cd if there are f potential faults, while a straightf
orward 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 2 fd + Cd in
the worst case. (It is assumed that c2 << d.) The second result shows
that any agreement algorithm must take time at least (f - 1)d + Cd in
the worst case. The new agreement algorithm can also be applied in a m
odel where processors are synchronous (C = 1), and where message delay
during a particular execution of the algorithm is bounded above by a
quantity delta which could be smaller than the worst-case upper bound
d. The running time in this case is approximately (2f - 1)delta + d.