Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation

Soundness of the Quasi-Synchronous Abstraction

Guillaume Baudart 1 Timothy Bourke 1 Marc Pouzet 1 
1 Parkas - Parallélisme de Kahn Synchrone
DI-ENS - Département d'informatique - ENS Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : We study the link between real-time quasi-periodic architectures where computing units execute 'almost periodically' and the discrete-time quasi-synchronous abstraction that P. Caspi proposed for analyzing them. The simplicity of the abstraction is appealing: the only events are node activations; logical steps account for transmission delays; and no node may be activated more than twice between two successive activations of any other. The motivation is to verify properties of real-time distributed systems in the simpler discrete model. By formalizing the relation between quasi-periodic architectures and the quasi-synchronous abstraction using L. Lamport's happened before relation, we show that the abstraction is sound for systems of two nodes. After showing that the abstraction is not sound for general systems with three or more nodes, we give necessary and sufficient restrictions on communication topologies to recover soundness.
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Guillaume Baudart Connect in order to contact the contributor
Submitted on : Monday, August 17, 2015 - 2:51:28 PM
Last modification on : Thursday, March 17, 2022 - 10:08:44 AM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:20:19 AM


Files produced by the author(s)


  • HAL Id : hal-01175571, version 2



Guillaume Baudart, Timothy Bourke, Marc Pouzet. Soundness of the Quasi-Synchronous Abstraction. [Research Report] RR-8755, INRIA Paris-Rocquencourt; INRIA. 2015, pp.19. ⟨hal-01175571v2⟩



Record views


Files downloads