Our paper titled "The Weakest Failure Detector for Wait-Free Dining under Eventual Weak Exclusion" has been accepted at SPAA 2009 (Symposium on Parallelism in Algorithms and Architectures).
Here is the 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 shows that any such dining solution can be made eventually fair. We also sketch a reduction for proving that the trusting and strong detectors (T + S) are necessary for wait-free dining under the stricter criterion of perpetual weak exclusion, thus resolving an open question posed by Delporte-Gallet et al. in 2005.
The paper is available here.