Bounds on the Time to Reach Agreement in the Presence of Timing Uncertainty
Abstract
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 sub1 and at most sub2; thus, C = sub1/sub2 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 adaption of an (function + 1)-round round-based agreement algorithm takes time (function + 1)Cd if there are function faults, while a straightforward reduction from a timing-based algorithm to a round-based algorithm yields a lower bound of (function + 1)d. The first major results major 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 function d + Cd in the worst case. The second major result shows that any agreement algorithm must take time at least (function - 1)d + Cd in the worst case. The new agreement algorithm can also be applied in a model 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 (2 function - 1)delta + d.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1990
- Accession Number
- ADA229766
Entities
People
- Cynthia Dwork
- Hagit Attiya
- Larry Stockmeyer
- Nancy Lynch
Organizations
- Massachusetts Institute of Technology