Breaking Symmetries - Computer Science > Logic in Computer ScienceReport as inadecuate

Breaking Symmetries - Computer Science > Logic in Computer Science - Download this document for free, or read online. Document in PDF available to download.

Abstract: A well-known result by Palamidessi tells us that {\pi}mix the {\pi}-calculuswith mixed choice is more expressive than {\pi}sep its subset with onlyseparate choice. The proof of this result argues with their differentexpressive power concerning leader election in symmetric networks. Later on,Gorla of- fered an arguably simpler proof that, instead of leader election insymmetric networks, employed the reducibility of -incestual- processes mixedchoices that include both enabled senders and receivers for the same channelwhen running two copies in parallel. In both proofs, the role of breaking ini-tial symmetries is more or less apparent. In this paper, we shed more light onthis role by re-proving the above result-based on a proper formalization ofwhat it means to break symmetries-without referring to another layer of thedistinguishing problem domain of leader election.Both Palamidessi and Gorla rephrased their results by stating that there isno uniform and reason- able encoding from {\pi}mix into {\pi}sep . We indicatehow the respective proofs can be adapted and exhibit the consequences ofvarying notions of uniformity and reasonableness. In each case, the ability tobreak initial symmetries turns out to be essential.

Author: Kirstin Peters, Uwe Nestmann


Related documents