loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
24th IEEE International Conference on Distributed Computing Systems (ICDCS'04)
Dining Philosophers with Crash Locality 1
Hachioji, Tokyo, Japan
March 24-March 26
ISBN: 0-7695-2086-3
Scott M. Pike, Ohio State University
Paolo A. G. Sivilotti, Ohio State University
Ideally, distributed algorithms isolate the side-effects of faults within local neighborhoods of impact. Failure locality quantifies this concept as the maximum radius of impact caused by a given fault. We present new locality results for the dining philosophers problem subject to crash failures. The optimal crash locality for dining is 0 in synchronous networks, but degrades to 2 in asynchronous networks. Using the eventually-perfect failure detector ♢P , we construct the first known dining algorithms with crash locality 1 under partial synchrony. These algorithms close the failure-locality complexity gap and improve the crash tolerance of resource allocation algorithms in practical networks. We prove the optimality of our results with two fundamental theorems. First, no dining solution using ♢P achieves locality 0. Second, ♢P is the weakest failure detector in the Chandra-Toueg hierarchy to realize locality 1.
Citation:
Scott M. Pike, Paolo A. G. Sivilotti, "Dining Philosophers with Crash Locality 1," icdcs, pp.22-29, 24th IEEE International Conference on Distributed Computing Systems (ICDCS'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.