Thumbnail Image

Synchrony versus causality in distributed systems

Peters, Kirstin; Schicke-Uffmann, Jens-Wolfhard; Goltz, Ursula; Nestmann, Uwe

Given a synchronous system, we study the question whether – or, under which conditions – the behaviour of that system can be realized by a (non-trivially) distributed and hence asynchronous implementation. In this paper, we partially answer this question by examining the role of causality for the implementation of synchrony in two fundamental different formalisms of concurrency, Petri nets and the π-calculus. For both formalisms it turns out that each ‘good’ encoding of synchronous interactions using just asynchronous interactions introduces causal dependencies in the translation.
Published in: Mathematical structures in computer science, 10.1017/s0960129514000644, Cambridge University Press
  • Dieser Beitrag ist mit Zustimmung des Rechteinhabers aufgrund einer (DFG geförderten) Allianz- bzw. Nationallizenz frei zugänglich.
  • This publication is with permission of the rights owner freely accessible due to an Alliance licence and a national licence (funded by the DFG, German Research Foundation) respectively.