Decidability and Complexity Results for Verification of Asynchronous Broadcast Networks
Decidability and Complexity Results for Verification of Asynchronous Broadcast Networks
复制标题
异步广播网络验证的可判定性和复杂性结果
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Riccardo Traverso
中科院分区：
文献类型：
--
作者：
G. Delzanno;Riccardo Traverso
我们研究的可判定性和复杂性的验证问题的网络中，节点通过异步广播消息进行通信。这种类型的通信是通过使用分布式模型来实现的，其中节点具有本地缓冲区。我们认为这里的安全性表示为一个覆盖性问题与任意的初始配置。该公式自然地模拟了可能导致协议中的错误状态的初始拓扑的搜索。
We study decidability and complexity of verification problems for networks in which nodes communicate via asynchronous broadcast messages. This type of communication is achieved by using a distributed model in which nodes have a local buffer. We consider here safety properties expressed as a coverability problem with an arbitrary initial configuration. This formulation naturally models the search of an initial topology that may lead to an error state in the protocol.