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
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/DSN.2007.44
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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||