Bounds on the Time to Reach Agreement in the Presence of Timing Uncertainty* (Extended Abstract)
Hagit Attiyat, Cynthia Dworkl, Nancy Ann Lynch, Larry Stockmeyer · 1991
Upper and lower bounds are proved for the real time complexity of the problem of reaching agreement in a distributed network, in the presence of process failures and inexact infor- mation about time. It is assumed that the amount of (real) time between any two consecutive steps of any nonfaulty process is at least c1 and at most CZ; thus, C = c2/cl is a measure of the timing uncertainty. It is also assumed that the time for message delivery is at most d. Processes are as- sumed to fail by stopping, so that process failures can be detected by timeouts. Let T denote the worst-case time to detect a failure, i.e., the elapsed time between tlhe failure of some process p and the time when all correct processes determine that p has failed; a straight- forward approach yields T roughly eqr.lid to Cd. Letting ~ denote the number of faults to be toler- ated, a simple adaptation of an (~+ 1)-rownd syn-