Time Bounds for Decision Problems in the Presence of Timing Uncertainty and Failures

✍ Scribed by Hagit Attiya; Taly Djerassi-Shintel

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 182 KB
• Volume: 61
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.2001.1730

✦ Synopsis

This paper studies the time complexity of solving decision problems in a distributed message-passing system when there is inexact information about time and process failures. A semi-synchronous model is assumed, in which the amount of (real) time between two consecutive steps of a nonfaulty process is at least c 1 and at most c 2 ; a message sent by a nonfaulty process is delivered within time at most d. Faulty processes do not always obey the timing requirements on their steps and on messages they send (late timing failures). We present a new stretching technique for deriving lower bounds in the presence of late timing failures. The combination of the stretching technique with known results yields the following lower bounds for this model:

1. The worst-case running time of any comparison-based renaming algorithm for p n participants is 0(log p c 2 c 1 d ), when there are p&1 late timing failures. A similar result holds, under certain restrictions, also for renaming algorithms which are not comparison-based. 2. The worstcase running time of any consensus algorithm is 0( n n& f c 2 c 1 d ), when there are f <n late timing failures. 3. The worst-case running time of any k-set consensus algorithm is 0( n n& f 1 k c 2 c 1 d ), when there are f <n late timing failures.