
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 ofbreaking (initial) symmetriesis 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 πmixinto π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.
ddc:004, FOS: Computer and information sciences, Computer Science - Logic in Computer Science, QA75.5-76.95, Logic in Computer Science (cs.LO), Electronic computers. Computer science, Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.), QA1-939, 004 Datenverarbeitung; Informatik, Mathematics
ddc:004, FOS: Computer and information sciences, Computer Science - Logic in Computer Science, QA75.5-76.95, Logic in Computer Science (cs.LO), Electronic computers. Computer science, Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.), QA1-939, 004 Datenverarbeitung; Informatik, Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 10 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
