Structured derivation of semi-synchronous algorithms
作者： Hagit Attiya , Fatemeh Borran , Martin Hutle , Zarko Milosevic , André Schiper
DOI: 10.1007/978-3-642-24100-0_37
关键词:
摘要: The semi-synchronous model is an important middle ground between the synchronous and asynchronous models of distributed computing. In this model, processes can detect (timeout) when other fail. However, since detection done by timing out, it incurs a cost much higher than typical delay messages. The paper presents new communication primitive, TimelyAnnounced Broadcast (TAB), uses in algorithms for consensus set model. Separate implementations TAB, withstanding different types failures, allow to derive under crash omission failures. The time bounds obtained our asymptotically match, or improve, previously known bounds.
springer.com
sci-hub.st 参考文章(19)
Eli Gafni, Round-by-Round Fault Detectors: Unifying Synchrony and Asynchrony (Extended Abstract). principles of distributed computing. pp. 143- 152 ,(1998)
Eli Gafni, Round-by-Round Fault Detectors: Unifying Synchrony and Asynchrony” ,(1998)
Hagit Attiya, Jennifer L. Welch, Distributed Computing: Fundamentals, Simulations and Advanced Topics ,(1998)
Maurice Herlihy, Sergio Rajsbaum, Concurrent computing and shellable complexes international symposium on distributed computing. pp. 109- 123 ,(2010) , 10.1007/978-3-642-15763-9_10
S. Chaudhuri, More choices allow more faults : set consensus problems in totally asynchronous systems Information & Computation. ,vol. 105, pp. 132- 158 ,(1993) , 10.1006/INCO.1993.1043
Eli Gafni, Round-by-round fault detectors (extended abstract): unifying synchrony and asynchrony principles of distributed computing. pp. 143- 152 ,(1998) , 10.1145/277697.277724
Cynthia Dwork, Nancy Lynch, Larry Stockmeyer, Consensus in the presence of partial synchrony Journal of the ACM. ,vol. 35, pp. 288- 323 ,(1988) , 10.1145/42282.42283
Hagit Attiya, Taly Djerassi-Shintel, Time Bounds for Decision Problems in the Presence of Timing Uncertainty and Failures Journal of Parallel and Distributed Computing. ,vol. 61, pp. 1096- 1109 ,(2001) , 10.1006/JPDC.2001.1730
Hagit Attiya, Cynthia Dwork, Nancy Lynch, Larry Stockmeyer, Bounds on the time to reach agreement in the presence of timing uncertainty Journal of the ACM. ,vol. 41, pp. 122- 152 ,(1994) , 10.1145/174644.174649
D. Dolev, H. R. Strong, Authenticated Algorithms for Byzantine Agreement SIAM Journal on Computing. ,vol. 12, pp. 656- 666 ,(1983) , 10.1137/0212045