Causal computational complexity of distributed processes
Causal computational complexity of distributed processes
复制标题
分布式过程的因果计算复杂性
DOI：
10.1016/j.ic.2022.104998
复制
发表时间：
2023
影响因子：
1
通讯作者：
Demangeon R
中科院分区：
文献类型：
--
作者：
Demangeon R
这篇文章研究了π演算过程的复杂性与传入消息引起的转换数量的关系。首先，我们提出了一个类型的系统整合Bellantoni和库克的多时间可计算功能的特征到邓和Sangiorgi的类型系统的终止。然后，我们定义了分布式消息的计算复杂度的基础上Degano和Priami的因果语义，它确定了交织转换之间的依赖关系。接下来，我们应用必要的语法流分析，以类型化的进程，以确保分布式消息的数量上的计算边界。我们证明了我们的分析是可判定的;在这个意义上，它保证了因果关系依赖于从外部接收的输入请求的消息总数是由这个请求的内容的多项式所限定的;并且是完整的，这意味着每个多项式递归函数可以由一个可类型化的过程来计算。
This article studies the complexity ofπ-calculus processes with respect to the quantity of transitions caused by an incoming message. First, we propose a typing system for integrating Bellantoni and Cook's characterisation of polytime computable functions into Deng and Sangiorgi's typing system for termination. We then define computational complexity of distributed messages based on Degano and Priami's causal semantics, which identifies the dependency between interleaved transitions. Next, we apply a necessary syntactic flow analysis to typable processes to ensure a computational bound on the number of distributed messages. We prove that our analysis isdecidable;soundin the sense that it guarantees that the total number of messages causally dependent of an input request received from the outside is bounded by a polynomial of the content of this request; andcomplete, meaning that each polynomial recursive function can be computed by a typable process.