On the Complexity of Protocol Validation Problems for Protocols with Bounded Capacity Channels (Special Section on Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, it is proven that the following three decision problems on validation of protocols with bounded capacity channels are NP-complete. (1) Given a protocol with the channel capacity being 1, determine whether or not there exist deadlocks in the protocol. (2) Given a protocol with the channel capacity being 1, determine whether or not there exist unspecified receptions in the protocol. (3) Given a protocol with the channel capacity being 2, determine whether or not there exist overflows such that the channel capacity is not bounded by in the protocol. These results suggest that, even when all channels in a protocol are bounded by 1 or 2, protocol validation should be in general interactable. It also clarifies the boundary of computational complexity of protocol validation problems because the cahnnel capacity 0 does not allow protocols to transmit and recieve messages.
- 社団法人電子情報通信学会の論文
- 1994-04-25
著者
-
Kikuno Tohru
Faculty Of Engineering Hiroshima University
-
Kakuda Yoshiaki
Faculty Of Engineering Science Osaka University
-
Takada Yoshihiro
Faculty of Engineering Science, Osaka University
-
Takada Yoshihiro
Faculty Of Engineering Science Osaka University
関連論文
- A Dynamic Index Allocation Scheme for Data Retrieval and Provision in Peer-to-Peer Networks
- Service Discovery Using Self-Regulating Agents in Ad Hoc Networks
- Service Discovery Using Self-Regulating Agents in Ad Hoc Networks
- Service Discovery Using Self-Regulating Agents in Ad Hoc Networks
- An Adaptive Multihop Clustering Scheme for Ad Hoc Networks with High Mobility
- Automated Synthesis of Protocol Specifications from Service Specifications with Parallelly Executable Multiple Primitives (Special Section on Net Theory and Its Applications)
- Testing for High Assurance System by FSM(Testing)(Assurance Systems and Networks)
- A New Conformance Testing Technique for Localization of Multiple Faults in Communication Protocols
- Reconfiguration Algorithm for Modular Redundant Linear Array
- A Hierarchical Routing Protocol Based on Autonomous Clustering in Ad Hoc Networks
- A Class of Hierarchical Routing Protocols Based on Autonomous Clustering for Large Mobile Ad Hoc Networks
- A Hybrid Greedy Routing with Location Information for Mobile Ad Hoc Networks
- On Common Sequence Problems (Applied Combinatorial Theory and Algorithms)
- A Distributed Algorithm for Deadlock Detection in Replicated Database Systems(Mathematical Foundations of Computer Science and Their Applications)
- Synthesis of Protocol Specifications for Design of Responsive Protocols (Special Issue on Responsive Computer Systems)
- An Autonomous Clustering-Based Hierarchical Multicast Routing for Mobile Ad Hoc Networks
- On the Complexity of Protocol Validation Problems for Protocols with Bounded Capacity Channels (Special Section on Discrete Mathematics and Its Applications)
- IEICE/IEEE Joint Special Issue on Assurance Systems and Networks
- A Distributed Routing Protocol for Finding Two Node-Disjoint Paths in Computer Networks (Special Issue on Distributed Processing for Controlling Telecommunications Systems)
- Effective Automated Testing for Graphical Objects(テスト技法・保守技術)
- Experimental Evaluation of Dynamic Scheduling for Parallel Logic Simulation Using Benchmark Circuits (Special Section of Letters Selected from the 1994 IEICE Spring Conference)
- The Multidimensional Benefits of Participation in Masters Sports: A Case Study of the "Masters Koshien"