skip to main content
Lingue:

On the completeness of bounded model checking for threshold-based distributed algorithms: Reachability

Konnov, Igor ; Veith, Helmut ; Widder, Josef

Information and Computation, February 2017, Vol.252, pp.95-109 [Rivista Peer Reviewed]

Fulltext disponibile

Citazioni Citato da
  • Titolo:
    On the completeness of bounded model checking for threshold-based distributed algorithms: Reachability
  • Autore: Konnov, Igor ; Veith, Helmut ; Widder, Josef
  • Note di contenuto: Counter abstraction is a powerful tool for parameterized model checking, if the number of local states of the concurrent processes is relatively small. In recent work, we introduced parametric interval counter abstraction that allowed us to verify the safety and liveness of threshold-based fault-tolerant distributed algorithms (FTDA). Due to state space explosion, applying this technique to distributed algorithms with hundreds of local states is challenging for state-of-the-art model checkers. In this paper, we demonstrate that reachability properties of FTDAs can be verified by bounded model checking. To ensure completeness, we need an upper bound on the distance between states. We show that the diameters of accelerated counter systems of FTDAs, and of their counter abstractions, have a quadratic upper bound in the number of local transitions. Our experiments show that the resulting bounds are sufficiently small to use bounded model checking for parameterized verification of...
  • Fa parte di: Information and Computation, February 2017, Vol.252, pp.95-109
  • Soggetti: Model Checking ; Fault-Tolerant Distributed Algorithms ; Byzantine Faults ; Computational Models ; Model Checking ; Fault-Tolerant Distributed Algorithms ; Byzantine Faults ; Computational Models ; Engineering ; Computer Science
  • Lingua: Inglese
  • Tipo: Articolo
  • Identificativo: ISSN: 0890-5401 ; E-ISSN: 1090-2651 ; DOI: 10.1016/j.ic.2016.03.006
  • Fonte: ScienceDirect Journals (Elsevier)

Ricerca in corso nelle risorse remote ...