### The fault span of crash failuresThe fault span of crash failures

Access Restriction
Subscribed

 Author Varghese, George ♦ Jayaram, Mahesh Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2000 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract A $\textit{crashing}$ network protocol is an asynchronous protocol whose memory does not survive crashes. We show that a crashing network protocol that works over unreliable links can be driven to arbitrary global states, where each node is in a state reached in some (possibly different) execution, and each link has an arbitrary mixture of packets sent in (possibly different) executions. Our theorem considerably generalizes an earlier result, due to Fekete et al., which states that there is no correct crashing Data Link Protocol. For example, we prove that there is no correct crashing protocol for token passing and for many other resource allocation protocols such as $\textit{k}-exclusion,$ and the drinking and dining philosophers problems. We further characterize the reachable states caused by crash failures using reliable non-FIFO and reliable FIFO links. We show that with reliable non-FIFO links any acyclic subset of nodes and links can be driven to arbitrary states. We show that with reliable FIFO links, only nodes can be driven to arbitrary states. Overall, we show a $\textit{strict}$ hierarchy in terms of the set of states reachable by crash failures in the three link models. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2000-03-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 47 Issue Number 2 Page Count 50 Starting Page 244 Ending Page 293

#### Open content in new tab

Source: ACM Digital Library