We examine the tolerance of dining philosopher algorithms subject to process
crash faults in arbitrary conflict graphs. This classic problem is unsolvable in asynchronous
message-passing systems subject to even a single crash fault. By contrast,
dining can be solved in synchronous systems capable of implementing the perfect
failure detector P (from the Chandra-Toueg hierarchy). We show that dining is also
solvable in weaker timing models using a combination of the trusting detector T and
the strong detector S; Our approach extends and composes two currents of previous
research. First, we define a parametric generalization of Lynch’s classic algorithm
for hierarchical resource allocation. Our construction converts any mutual exclusion
algorithm into a valid dining algorithm. Second, we consider the fault-tolerant mutual
exclusion algorithm (FTME) of Delporte-Gallet, et al., which uses T and the
strong detector S to mask crash faults in any environment. We instantiate our dining
construction with FTME, and prove that the resulting dining algorithm guarantees
masking tolerance to crash faults. Our contribution (1) defines a new construction
for transforming mutual exclusion algorithms into dining algorithms, and (2) demonstrates
a better upper-bound on the fault-detection capabilities necessary to mask
crash faults in dining philosophers.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-1072 |
| Date | 15 May 2009 |
| Creators | Idimadakala, Vijaya K. |
| Contributors | Pike, Scott M. |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Thesis, text |
| Format | electronic, application/pdf, born digital |
Page generated in 0.0022 seconds