Computer Science – Logic in Computer Science
Scientific paper
2011-08-09
EPTCS 60, 2011, pp. 56-65
Computer Science
Logic in Computer Science
In Proceedings PACO 2011, arXiv:1108.1452
Scientific paper
10.4204/EPTCS.60.4
We summarize the main results proved in recent work on the parameterized verification of safety properties for ad hoc network protocols. We consider a model in which the communication topology of a network is represented as a graph. Nodes represent states of individual processes. Adjacent nodes represent single-hop neighbors. Processes are finite state automata that communicate via selective broadcast messages. Reception of a broadcast is restricted to single-hop neighbors. For this model we consider a decision problem that can be expressed as the verification of the existence of an initial topology in which the execution of the protocol can lead to a configuration with at least one node in a certain state. The decision problem is parametric both on the size and on the form of the communication topology of the initial configurations. We draw a complete picture of the decidability and complexity boundaries of this problem according to various assumptions on the possible topologies.
Delzanno Giorgio
Sangnier Arnaud
Zavattaro Gianluigi
No associations
LandOfFree
Parameterized Verification of Safety Properties in Ad Hoc Network Protocols does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Parameterized Verification of Safety Properties in Ad Hoc Network Protocols, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parameterized Verification of Safety Properties in Ad Hoc Network Protocols will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-69965