Bounds on the time to reach agreement in the presence of timing uncertainty
Hagit Attiya, Cynthia Dwork, Nancy Ann Lynch, Larry Stockmeyer · Journal of the ACM · 1994
Upper and lower bounds are proved for the time complexity of the problem of reaching agreement m a distributed network m the presence of process fwlures and inexact information about time.It is assumed that the amount of (real) time between any two consecutwe steps of any ncmfatrhy process is at least c1 and at most C2; thus, C = cz/cl is a measure of the timing uncertainty.It E also assumed that the time for message dehvery ]s at most d.Processes are assumed to fail by stopping, so that process fdures can be detected by timeouts.A straightforward adaptation of an (~+ 1)-round round-based agreement algorithm takes time (f + l)Cd If there are f potential faults, while a straightforward mochflcation of the proof that f'+ 1 rounds are required yields a lower bound of time (~+ 1)d.The frost result of this paper is m agreement algorlthm in which the uncerttimty factor C is only incurred for one round, yielding A preliminary version of this work appeared in Proceedings of the 23rd ACM SvrnposamZ on Theon of Corrrputmg (New Orleans, La., May 6-8).ACM, New York, 1991, pp.359-369.