Logic in Computer Science (LICS 2003)

Paper: Model Checking Guarded Protocols (at LICS 2003)

Authors: E. Allen Emerson Vineet Kahlon

Abstract

The Parameterized Model Checking Problem (PMCP) is to decide whether a temporal property holds for a uniform family of systems, C||U, comprised of a control process, C, and finitely, but arbitrarily, many copies of a user process, U, executing concurrently with interleaving semantics. We delineate the decidability/undecidability boundary of the PMCP for all possible systems that arise by letting processes coordinate using different subsets of the following communication primitives: conjunctive boolean guards, disjunctive boolean guards, pairwise rendezvous, asynchronous rendezvous and broadcast actions. Our focus will be on the following linear time properties: (p1) LTL\X formulae over C, (p2) LTL formulae over C, (p3) regular properties specified as regular automata, and (p4) w-regular properties specified as w-regular automata. We also establish a hierarchy based on the relative expressive power of the primitives by showing that disjunctive guards and pairwise rendezvous are equally expressive, in that we can reduce the PMCP for regular and w-regular properties for systems with disjunctive guards to ones with pairwise rendezvous and vice versa, but that each of asynchronous rendezvous and broadcasts is strictly more expressive than pairwise rendezvous (and disjunctive guards). Moreover, for systems with conjunctive guards, we give a simple characterization of the decidability/undecidability boundary of the PMCP by showing that allowing stuttering sensitive properties bridges the gap between decidability (for p1) and undecidability (for p2). A broad framework for modeling snoopy cache protocols is also presented for which the PMCP for p3 is decidable and that can model all snoopy cache protocols given in [13] thereby overcoming the undecidability results.

BibTeX

  @InProceedings{EmersonKahlon-ModelCheckingGuarde,
    author = 	 {E. Allen Emerson and Vineet Kahlon},
    title = 	 {Model Checking Guarded Protocols},
    booktitle =  {Proceedings of the Eighteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2003},
    year =	 2003,
    editor =	 {Phokion G. Kolaitis},
    month =	 {June}, 
    pages =      {361--370},
    location =   {Ottawa, Canada}, 
    publisher =	 {IEEE Computer Society Press}
  }