The asynchronous bounded-cycle model

Peter Robinson, Ulrich Schmid

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationStabilization, Safety, and Security of Distributed Systems - 10th International Symposium, SSS 2008, Proceedings
PublisherSpringer Verlag
Number of pages17
ISBN (Print)3540893342, 9783540893349
StatePublished - 2008
Externally publishedYes
Event10th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2008 - Detroit, MI, United States
Duration: Nov 21 2008Nov 23 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5340 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference10th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2008
Country/TerritoryUnited States
CityDetroit, MI


  • Clock synchronization
  • Fault-tolerant distributed algorithms
  • Partially synchronous models

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'The asynchronous bounded-cycle model'. Together they form a unique fingerprint.

Cite this