| 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 |
| CS0654.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. |
| 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/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