ACM/IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Fourteenth Annual IEEE Symposium on

Logic in Computer Science (LICS 1999)

Paper: On the Verification of Broadcast Protocols (at LICS 1999)

Authors: Javier Esparza Alain Finkel Richard Mayr


We analyze the model-checking problems for safety and liveness properties in parameterized broadcast protocols, a model introduced in [Emerson,Namjoshi, LICS'98]. We show that the procedure suggested in [Emerson,Namjoshi, LICS'98] for safety properties may not terminate, whereas termination is guaranteed for the procedure of [Abdulla, Cerans, Jonnson, Tsay, LICS'96] based on upward closed sets. We show that the model-checking problem for liveness properties is undecidable. In fact, even the problem of deciding if a broadcast protocol may exhibit an infinite behavior is undecidable.


    author = 	 {Javier Esparza and Alain Finkel and Richard Mayr},
    title = 	 {On the Verification of Broadcast Protocols},
    booktitle =  {Proceedings of the Fourteenth Annual IEEE Symposium on Logic in Computer Science (LICS 1999)},
    year =	 {1999},
    month =	 {July}, 
    pages =      {352--359},
    location =   {Trento, Italy}, 
    publisher =	 {IEEE Computer Society Press}

Last modified: 2022-10-3113:49
Sam Staton