The Weakest Failure Detector for Wait-Free Dining under Eventual Weak Exclusion
Conference Paper
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
Dining philosophers is a classic scheduling problem for local mutual exclusion on arbitrary conflict graphs. We establish necessary conditions to solve wait-free dining under eventual weak exclusion in message-passing systems with crash faults. Wait-free dining ensures that every correct hungry process eventually eats. Eventual weak exclusion permits finitely many scheduling mistakes, but eventually no live neighbors eat simultaneously; this exclusion criterion models scenarios where scheduling mistakes are recoverable or only affect performance. Previous work showed that the eventually perfect failure detector (P) is sufficient to solve wait-free dining under eventual weak exclusion; we prove that P is also necessary, and thus P is the weakest oracle to solve this problem. Our reduction also establishes that any such dining solution can be made eventually fair. Finally, the reduction itself may be of more general interest; when applied to wait-free perpetual weak exclusion, our reduction produces an alternative proof that the more powerful trusting oracle (T) is necessary (but not sufficient) to solve the problem of Fault-Tolerant Mutual Exclusion (FTME). Copyright 2009 ACM.
name of conference
Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures
