DocumentCode :
3398746
Title :
Tight fault locality
Author :
Kutten, Shay ; Peleg, David
Author_Institution :
IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA
fYear :
1995
fDate :
23-25 Oct 1995
Firstpage :
704
Lastpage :
713
Abstract :
The notion of fault local mending was suggested as a paradigm for designing fault tolerant algorithms that scale to large networks. For such algorithms the complexity of recovering is proportional to the number of faults. We refine this notion by introducing the concept of tight fault locality to deal with problems whose complexity (in the absence of faults) is sublinear in the size of the network. For a function whose complexity on an n-node network is f(n), a tightly fault local algorithm recovers a legal global state in O(f(x)) time when the (unknown) number of faults is x. We illustrate this concept by presenting a general transformation for MIS algorithms to make them fault local. In particular, our transformation yields an O(logx) randomized mending algorithm and a 2√βlogx deterministic mending algorithm for MIS. Similar results are obtained for other local functions such as a Δ+1 coloring. We also present the first tight fault local mending algorithm for global functions, using our results for MIS. This improves (by a logarithmic factor) the complexity of a previous fault-local mending algorithm for global functions
Keywords :
computational complexity; fault tolerant computing; system recovery; complexity; deterministic mending algorithm; fault local mending; fault tolerant algorithms; global functions; tightly fault local algorithm; Algorithm design and analysis; Career development; Computer networks; Computer science; Fault tolerance; IP networks; Information processing; Law; Legal factors; Mathematics;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on
Conference_Location :
Milwaukee, WI
ISSN :
0272-5428
Print_ISBN :
0-8186-7183-1
Type :
conf
DOI :
10.1109/SFCS.1995.492672
Filename :
492672
Link To Document :
بازگشت