The asynchronous bounded-cycle model

ABSTRACT

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.

REFERENCES

• 1: Matthias Fugger , Ulrich Schmid , Gottfried Fuchs , Gerald Kempf, Fault-Tolerant Distributed Clock Generation in VLSI Systems-on-Chip, Proceedings of the Sixth European Dependable Computing Conference, p.87-96, October 18-20, 2006 [doi>10.1109/EDCC.2006.11]
• 2: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 3: P. Robinson and U. Schmid. The Asynchronous Bounded-Cycle Model. Research Report 24/2008, Technische Universitaet Wien.
• 4: J. Widder, G. Le Lann, and U. Schmid. Failure detection with booting in partially synchronous systems. Proceedings EDCC-5, Springer LNCS 3463, pages 20--37, Apr. 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms, Theory

Keywords:
fault-tolerant distributed algorithms, lock-step round simulation, partially synchronous system models, vlsi