On the Expressive Power of Global and Local Priority in Process Calculi
On the Expressive Power of Global and Local Priority in Process Calculi
复制标题
论过程计算中全局优先级和局部优先级的表达力
DOI：
10.1007/978-3-540-74407-8_17
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
R. Gorrieri
中科院分区：
文献类型：
--
作者：
Cristian Versari;N. Busi;R. Gorrieri
优先级是许多计算系统经常使用的功能。在本文中，我们研究了用不同优先级机制丰富的两个过程代数的表达能力。特别是，我们考虑具有全局优先级（简称 FAP）的异步 CCS（简称 FAP）和 Phillips’ CPG（具有本地优先级的 CCS）的有限（即无递归）片段，并将它们的表达能力与两种非优先演算（即 π 演算及其基于广播的版本，称为 bπ）的表达能力进行对比。我们通过基于领导者选举的分离结果证明，在某些条件下，不存在将 FAP 编码为 π 微积分或 CPG。此外，我们提出了分布式计算中的另一个问题，我们称之为最后一个站立问题（简称LMS），通过证明不存在将优先演算到保留任何真诚（完整但部分正确，即承认分歧或提前终止）语义的非优先演算的并行保留编码，更好地揭示了上述两个优先演算和两个非优先演算之间的差距。
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-prioritised calculi, namely theπ-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 thelast man standingproblem (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 anysincere(complete but partially correct, i.e., admitting divergence or premature termination) semantics.
DOI：
--
发表时间：
2021
期刊：
--
影响因子：
--
作者：
通讯作者：
--