Failure detectors encapsulate fairness
Failure detectors have long been viewed as abstractions for the synchronism present in distributed system models. However, investigations into the exact amount of synchronism encapsulated by a given failure detector have met with limited success. The reason for this is that traditionally, models of...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer-Verlag
2016
|
| Online Access: | http://hdl.handle.net/1721.1/104892 |
| _version_ | 1826200033469399040 |
|---|---|
| author | Pike, Scott M. Welch, Jennifer L. Sastry, Srikanth |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Pike, Scott M. Welch, Jennifer L. Sastry, Srikanth |
| author_sort | Pike, Scott M. |
| collection | MIT |
| description | Failure detectors have long been viewed as abstractions for the synchronism present in distributed system models. However, investigations into the exact amount of synchronism encapsulated by a given failure detector have met with limited success. The reason for this is that traditionally, models of partial synchrony are specified with respect to real time, but failure detectors do not encapsulate real time. Instead, we argue that failure detectors encapsulate the fairness in computation and communication. Fairness is a measure of the number of steps executed by one process relative either to the number of steps taken by another process or relative to the duration for which a message is in transit. We argue that failure detectors are substitutable for the fairness properties (rather than real-time properties) of partially synchronous systems. We propose four fairness-based models of partial synchrony and demonstrate that they are, in fact, the ‘weakest system models’ to implement the canonical failure detectors from the Chandra-Toueg hierarchy. We also propose a set of fairness-based models which encapsulate the G[subscript c] parametric failure detectors which eventually and permanently suspect crashed processes, and eventually and permanently trust some fixed set of c correct processes. |
| first_indexed | 2024-09-23T11:29:52Z |
| format | Article |
| id | mit-1721.1/104892 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:29:52Z |
| publishDate | 2016 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/1048922022-09-27T19:57:11Z Failure detectors encapsulate fairness Pike, Scott M. Welch, Jennifer L. Sastry, Srikanth Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Sastry, Srikanth Failure detectors have long been viewed as abstractions for the synchronism present in distributed system models. However, investigations into the exact amount of synchronism encapsulated by a given failure detector have met with limited success. The reason for this is that traditionally, models of partial synchrony are specified with respect to real time, but failure detectors do not encapsulate real time. Instead, we argue that failure detectors encapsulate the fairness in computation and communication. Fairness is a measure of the number of steps executed by one process relative either to the number of steps taken by another process or relative to the duration for which a message is in transit. We argue that failure detectors are substitutable for the fairness properties (rather than real-time properties) of partially synchronous systems. We propose four fairness-based models of partial synchrony and demonstrate that they are, in fact, the ‘weakest system models’ to implement the canonical failure detectors from the Chandra-Toueg hierarchy. We also propose a set of fairness-based models which encapsulate the G[subscript c] parametric failure detectors which eventually and permanently suspect crashed processes, and eventually and permanently trust some fixed set of c correct processes. National Science Foundation (U.S.) (Grant CCF-0964696) National Science Foundation (U.S.) (Grant CCF-0937274) Texas Higher Education Coordinating Board (grant NHARP 000512-0130-2007) National Science Foundation (U.S.) (NSF Science and Technology Center, grant agreement CCF-0939370) 2016-10-20T19:44:20Z 2016-10-20T19:44:20Z 2012-02 2011-04 2016-08-18T15:27:55Z Article http://purl.org/eprint/type/JournalArticle 0178-2770 1432-0452 http://hdl.handle.net/1721.1/104892 Pike, Scott M., Srikanth Sastry, and Jennifer L. Welch. "Failure detectors encapsulate fairness." Distributed Computing, vol. 25, issue 4, February 2012, pp. 313-333. en http://dx.doi.org/10.1007/s00446-012-0164-x Distributed Computing Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. Springer-Verlag application/pdf Springer-Verlag Springer-Verlag |
| spellingShingle | Pike, Scott M. Welch, Jennifer L. Sastry, Srikanth Failure detectors encapsulate fairness |
| title | Failure detectors encapsulate fairness |
| title_full | Failure detectors encapsulate fairness |
| title_fullStr | Failure detectors encapsulate fairness |
| title_full_unstemmed | Failure detectors encapsulate fairness |
| title_short | Failure detectors encapsulate fairness |
| title_sort | failure detectors encapsulate fairness |
| url | http://hdl.handle.net/1721.1/104892 |
| work_keys_str_mv | AT pikescottm failuredetectorsencapsulatefairness AT welchjenniferl failuredetectorsencapsulatefairness AT sastrysrikanth failuredetectorsencapsulatefairness |