TY - GEN
T1 - The asynchronous bounded-cycle model
AU - Robinson, Peter
AU - Schmid, Ulrich
N1 - Funding Information:
✩ This research is supported by the Austrian Science Foundation (FWF) projects P17757 and P20529. A preliminary version of this paper (Robinson and Schmid∗ Correspondingauthor.Tel.:+4315880118253;fax:+4315880118297.(2008))receivedthebestpaperawardatSSS’08. E-mail addresses: robinson@ecs.tuwien.ac.at (P. Robinson), s@ecs.tuwien.ac.at (U. Schmid).
PY - 2008
Y1 - 2008
N2 - This paper shows how synchrony conditions can be added to the purely asynchronous model in a way that avoids any reference to message delays and computing step times, as well as any global constraints on communication patterns and network topology. Our Asynchronous Bounded-Cycle (ABC) model just bounds the ratio of the number of forward- and backward-oriented messages in certain ("relevant") cycles in the space-time diagram of an asynchronous execution. We show that clock synchronization and lock-step rounds can easily be implemented and proved correct in the ABC model, even in the presence of Byzantine failures. We also prove that any algorithm working correctly in the partially synchronous Θ-Model also works correctly in the ABC model. Finally, we relate our model to the classic partially synchronous model, and discuss aspects of its applicability in real systems.
AB - This paper shows how synchrony conditions can be added to the purely asynchronous model in a way that avoids any reference to message delays and computing step times, as well as any global constraints on communication patterns and network topology. Our Asynchronous Bounded-Cycle (ABC) model just bounds the ratio of the number of forward- and backward-oriented messages in certain ("relevant") cycles in the space-time diagram of an asynchronous execution. We show that clock synchronization and lock-step rounds can easily be implemented and proved correct in the ABC model, even in the presence of Byzantine failures. We also prove that any algorithm working correctly in the partially synchronous Θ-Model also works correctly in the ABC model. Finally, we relate our model to the classic partially synchronous model, and discuss aspects of its applicability in real systems.
KW - Clock synchronization
KW - Fault-tolerant distributed algorithms
KW - Partially synchronous models
UR - http://www.scopus.com/inward/record.url?scp=58049128225&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=58049128225&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-89335-6_20
DO - 10.1007/978-3-540-89335-6_20
M3 - Conference contribution
AN - SCOPUS:58049128225
SN - 3540893342
SN - 9783540893349
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 246
EP - 262
BT - Stabilization, Safety, and Security of Distributed Systems - 10th International Symposium, SSS 2008, Proceedings
PB - Springer Verlag
T2 - 10th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2008
Y2 - 21 November 2008 through 23 November 2008
ER -