Technical Report CS0803

TR#:CS0803
Class:CS
Title: TIGHT BOUNDS ON THE ROUND COMPLEXITY OF DISTRIBUTED 1-SOLVABLE TASKS.
Authors: O. Biran, S. Moran and S. Zaks
PDFNot Available
Abstract:

A distributed task T is 1-solvable is there exists a protocol that solves it in the presence of (at most) one crash failure. A precise characterization of the 1-solvable tasks was given in [BMZ]. In this paper we determine the number of rounds of communication that are required, in the worst case, by a protocol which 1-solves a given 1-solvable task T for n processors. We define the radius R(T) of T, and show that if R(T) is finite, then this number is \Theta(\Log_N R(T)); more precisely, we give a lower bound of \Log_{(N-1)} R(T), and an upper bound of 2+\Lceil \Log_{(N-1)} R(T) \Rceil. The upper bound implies, for example, that each of the following tasks: renaming, order preserving renaming ([ABDKPR]) and binary monotone consensus ([BMZ]) can be solved in the presence of one fault in 3 rounds of communications. All previous protocols that 1-solved these tasks required \Omega(N) rounds. The result is also generalized to tasks whose radii are not bounded, e.g., the approximate consensus and its variants ([DLPSW, BMZ]).

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1994/CS/CS0803), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1994
To the main CS technical reports page

Computer science department, Technion
admin