TR#:  CS0803 
Class:  CS 
Title:  TIGHT BOUNDS ON THE
ROUND COMPLEXITY OF DISTRIBUTED 1SOLVABLE TASKS. 
Authors:  O. Biran, S. Moran and S. Zaks 
Not Available  
Abstract: 
A distributed task T is 1solvable is there exists a protocol that solves it in the presence of (at most) one crash failure. A precise characterization of the 1solvable 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 1solves a given 1solvable 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_{(N1)} R(T), and an upper bound of 2+\Lceil \Log_{(N1)} 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 1solved 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]).

Copyright  The 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/cgibin/trinfo.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