loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN'07)
Eventually k-Bounded Wait-Free Distributed Daemons
Edinburgh, UK
June 25-June 28
ISBN: 0-7695-2855-4
Yantao Song, Texas A&M University, USA
Scott M. Pike, Texas A&M University, USA
Wait-free scheduling is unsolvable in asynchronous message-passing systems subject to crash faults. Given the practical importance of this problem, we examine its solvability under partial synchrony relative to the eventually perfect failure detector \diamondsuit P. Specifically, we present a new oracle-based solution to the dining philosophers problem that is wait-free in the presence of arbitrarily many crash faults. Additionally, our solution satisfies eventual k-bounded waiting, which guarantees that every execution has an infinite suffix where no process can overtake any live hungry neighbor more than k consecutive times. Finally, our algorithm uses only bounded space, bounded-capacity channels, and is also quiescent with respect to crashed processes. Among other practical applications, our results support wait-free distributed daemons for fairly scheduling self-stabilizing protocols in the presence of crash faults.
Index Terms:
self-stabilization, daemons, wait-freedom
Citation:
Yantao Song, Scott M. Pike, "Eventually k-Bounded Wait-Free Distributed Daemons," dsn, pp.645-655, 37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.