page 1  (33 pages)
2to next section

Expanding the text here will generate a large amount of data for your browser to display

Fault-Local Distributed Mending

Shay Kutten ? David Peleg y

November 28, 1994

Abstract

As communication networks grow, existing fault handling tools that involve global measures such as global time-outs or reset procedures become increasingly unaffordable, since their cost grows with the size of the network. Rather, for a fault handling mechanism to scale to large networks, its cost must depend only on the number of failed nodes (which, thanks to today's technology, grows much slower than the networks), and moreover, it should allow the non-faulty regions of the networks to continue their operation even during the recovery of the faulty parts. This abstract introduces the concept of fault-local algorithms, which are algorithms whose cost depends only on the (unknown) number of faults, and demonstrates the feasibility of fault locality via developing such algorithms for a number of key problems, including MIS and ? + 1 coloring.

?I.B.M. T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, New York 10598, USA. kutten@watson.ibm.com.
yDepartment of Applied Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, 76100 Israel. peleg@wisdom.weizmann.ac.il. Supported in part by a Walter and Elise Haas Career Development Award and by a grant from the Basic Research Foundation. Part of the work was done while visiting IBM T.J. Watson Research Center.