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 (i.e., recursion-free) fragment of asynchronous CCS with global priority (FAP, for short) and Phillips’ CPG (CCS with local priority), and we contrast their expressive power with that of two non-prioritized calculi, namely the pi-calculus and its broadcast-based version, called b. We prove, by means of leader-election-based separation results, that there exists no encoding of FAP into -Calculus or CPG, under certain conditions. Moreover, we single out another problem in distributed computing, 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 into the non-prioritised calculi retaining any sincere (complete but partially correct, i.e., admitting divergence or premature termination) semantics.

C. Versari, N. Busi, R. Gorrieri (2007). On the Expressive Power of Global and Local Priority in Process Calculi. HEIDELBERG : Springer-Verlag.

On the Expressive Power of Global and Local Priority in Process Calculi

VERSARI, CRISTIAN;BUSI, NADIA;GORRIERI, ROBERTO
2007

Abstract

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 (i.e., recursion-free) fragment of asynchronous CCS with global priority (FAP, for short) and Phillips’ CPG (CCS with local priority), and we contrast their expressive power with that of two non-prioritized calculi, namely the pi-calculus and its broadcast-based version, called b. We prove, by means of leader-election-based separation results, that there exists no encoding of FAP into -Calculus or CPG, under certain conditions. Moreover, we single out another problem in distributed computing, 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 into the non-prioritised calculi retaining any sincere (complete but partially correct, i.e., admitting divergence or premature termination) semantics.
2007
Concurrency Theory.
241
255
C. Versari, N. Busi, R. Gorrieri (2007). On the Expressive Power of Global and Local Priority in Process Calculi. HEIDELBERG : Springer-Verlag.
C. Versari; N. Busi; R. Gorrieri
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/52773
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 10
social impact