[inria-00201071, v1] Tutorial on separation results in process calculi via leader election problems

Author manuscript, published in "Theoretical Computer Science 388, 1-3 (2007) 267--289" DOI : 10.1016/j.tcs.2007.09.001Tutorial on separation results in processcalculi via leader election problemsa,b cMaria Grazia Vigliotti , Iain Phillips andb,dCatuscia PalamidessiaINRIA Sophia-Antipolis, FrancebINRIA Futurs, FrancecDepartment of Computing, Imperial College London, EnglanddLIX Polytechnique, FranceAbstractWe compare the expressive power of process calculi by studying the problem ofelecting a leader in a symmetric network of processes. We consider the π-calculuswith mixed choice, separate choice and internal mobility, value-passing CCS andMobile Ambients, together with other ambient calculi (Safe Ambients, the Pushand Pull Ambient Calculus and Boxed Ambients). We provide a unified approachfor all these calculi using reduction semantics.Key words: leader election, π-calculus, Mobile Ambients, CCS1 IntroductionIn this tutorial we consider expressiveness results regarding different processcalculi.Inthelasttwentyyears,agreatvarietyofconcurrentcalculihavebeendeveloped, and most of them are Turing complete, i.e. they can compute thesame class of functions as Turing machines. However, function computabilityis only one possible way to evaluate the power of a concurrent language; otheraspects, related to the concurrent nature of the model, should also be takeninto account. Our focus is on the synchronisation capabilities of a calculus,and more precisely on ...