Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-6444
Main Title: Breaking symmetries
Author(s): Peters, Kirstin
Nestmann, Uwe
Type: Article
Language Code: en
Abstract: A well-known result by Palamidessi tells us that πmix (the π-calculus with mixed choice) is more expressive than πsep (its subset with only separate choice). The proof of this result analyses their different expressive power concerning leader election in symmetric networks. Later on, Gorla offered an arguably simpler proof that, instead of leader election in symmetric networks, employed the reducibility of ‘incestual’ processes (mixed choices that include both enabled senders and receivers for the same channel) when running two copies in parallel. In both proofs, the role of breaking (initial) symmetries is more or less apparent. In this paper, we shed more light on this role by re-proving the above result – based on a proper formalization of what it means to break symmetries – without referring to another problem domain like leader election. Both Palamidessi and Gorla rephrased their results by stating that there is no uniform and reasonable encoding from πmix into πsep. We indicate how their proofs can be adapted and exhibit the consequences of varying notions of uniformity and reasonableness. In each case, the ability to break initial symmetries turns out to be essential. Moreover, by abandoning the uniformity criterion, we show that there indeed is a reasonable encoding. We emphasize its underlying principle, which highlights the difference between breaking symmetries locally instead of globally.
URI: https://depositonce.tu-berlin.de//handle/11303/7169
http://dx.doi.org/10.14279/depositonce-6444
Issue Date: 2014
Date Available: 23-Nov-2017
DDC Class: 004 Informatik
Usage rights: Terms of German Copyright Law
Journal Title: Mathematical structures in computer science
Publisher: Cambridge University Press
Publisher Place: Cambridge
Volume: 26
Issue: 6
Publisher DOI: 10.1017/s0960129514000346
Page Start: 1054
Page End: 1106
EISSN: 1469-8072
ISSN: 0960-1295
Notes: 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.
Appears in Collections:Fachgebiet Modelle und Theorie Verteilter Systeme » Publications

Files in This Item:
File Description SizeFormat 
breaking_symmetries.pdf1.25 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.