Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
An expressiveness study of priority in process calculi
Ist Teil von
Mathematical structures in computer science, 2009-12, Vol.19 (6), p.1161-1189
Ort / Verlag
Cambridge, UK: Cambridge University Press
Erscheinungsjahr
2009
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
Priority is a frequently used feature of many computational systems. In this paper we study the expressiveness of two process algebras enriched with different priority mechanisms. In particular, we consider a finite (that is, recursion-free) fragment of asynchronous CCS with global priority (FAP, for short) and Phillips' CPG (CCS with local priority), and contrast their expressive power with that of two non-prioritised calculi, namely the π-calculus and its broadcast-based version, called bπ. We prove, by means of leader-election-based separation results, that, under certain conditions, there exists no encoding of FAP in π-Calculus or CPG. Moreover, we single out another problem in distributed computing, which we call the last man standing problem (LMS for short), that better reveals the gap between the two prioritised calculi above and the two non-prioritised ones, by proving that there exists no parallel-preserving encoding of the prioritised calculi in the non-prioritised calculi retaining any sincere (complete but partially correct, that is, admitting divergence or premature termination) semantics.