Technical Report CS0654

TR#:CS0654
Class:CS
Title: ON THE COMPLEXITY OF COMPUTATION IN THE PRESENCE OF LINK FAILURES: THE CASE OF A RING
Authors: 0, Galdreich and L. Shrira
PDFCS0654.pdf
Abstract: We investigate the message complexity of distributed computations on rings of asynchronous processors. In such computations, each processor has an initial local value and the task is to compute some predetennined function of all local values. Our work deviates from previous works concerning the complexity of ring computations in that we consider the effect of link failures. A link is said to fail if some message sent through it never reaches its destination. We show that the message complexity of any function, which is "sensative to all its inputs", is 8(n log n) when n, the number of processors, is a-priori known; and is S(n2) when n is not known. Interestingly, these tight bounds do not depend on whether the identity of a leader is apriori known before the computation starts. These results stand in sharp contrast to the situation in asynchronous rings with no link failures, where the message complexity is effected by the apriori knowledge of a leader but is not affected by the knowledge of n.
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/1990/CS/CS0654), 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 1990
To the main CS technical reports page

Computer science department, Technion
admin