[Back]

U. Schmid, P. Robinson:
"Brief Announcement: The Asynchronous Bounded Cycle Model";
Talk: ACM Symposium on Principles of Distributed Computing, Toronto, Canada; 2008-08-18 - 2008-08-21; in: "PODC'08 Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing", Association for Computing Machinery (ACM), (2008), ISBN: 978-1-59593-989-0; 423.

In this paper, we introduce the Asynchronous Bounded-Cycle (ABC) model, which considerably relaxes the Theta-Model proposed by Le Lann and Schmid. The ABC model just bounds the ratio of the number of forward and backward messages in certain cycles in the space-time diagram of an asynchronous execution. It hence avoids any reference to end-to-end delays, allows individual messages to have arbitrary delays, and does not involve global synchrony conditions. 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. Moreover, we show that any correct Theta-algorithm also works correctly in the ABC model. Our proof is based on a novel technique for assigning message delays to asynchronous executions, which is of independent interest.

http://dx.doi.org/10.1145/1400751.1400815