Detecting Unrealizability of Distributed Fault-tolerant Systems
Writing formal specifications for distributed systems is difficult. Even simple consistency requirements often turn out to be unrealizable because of the complicated information flow in the distributed system: not all information is available in every component, and information transmitted from othe...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2015-09-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/1588/pdf |
| _version_ | 1811313068670451712 |
|---|---|
| author | Bernd Finkbeiner Leander Tentrup |
| author_facet | Bernd Finkbeiner Leander Tentrup |
| author_sort | Bernd Finkbeiner |
| collection | DOAJ |
| description | Writing formal specifications for distributed systems is difficult. Even
simple consistency requirements often turn out to be unrealizable because of
the complicated information flow in the distributed system: not all information
is available in every component, and information transmitted from other
components may arrive with a delay or not at all, especially in the presence of
faults. The problem of checking the distributed realizability of a temporal
specification is, in general, undecidable. Semi-algorithms for synthesis, such
as bounded synthesis, are only useful in the positive case, where they
construct an implementation for a realizable specification, but not in the
negative case: if the specification is unrealizable, the search for the
implementation never terminates. In this paper, we introduce counterexamples to
distributed realizability and present a method for the detection of such
counterexamples for specifications given in linear-time temporal logic (LTL). A
counterexample consists of a set of paths, each representing a different
sequence of inputs from the environment, such that, no matter how the
components are implemented, the specification is violated on at least one of
these paths. We present a method for finding such counterexamples both for the
classic distributed realizability problem and for the fault-tolerant
realizability problem. Our method considers, incrementally, larger and larger
sets of paths until a counterexample is found. For safety specifications in
weakly ordered architectures we obtain a decision procedure, while
counterexamples for full LTL and arbitrary architectures may consist of
infinitely many paths. Experimental results, obtained with a QBF-based
prototype implementation, show that our method finds simple errors very
quickly, and even problems with high combinatorial complexity, like the
Byzantine Generals' Problem, are tractable. |
| first_indexed | 2024-04-13T10:47:43Z |
| format | Article |
| id | doaj.art-2eb05a67ae344885bd0b75daf747d1d7 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-13T10:47:43Z |
| publishDate | 2015-09-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-2eb05a67ae344885bd0b75daf747d1d72022-12-22T02:49:45ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742015-09-01Volume 11, Issue 310.2168/LMCS-11(3:12)20151588Detecting Unrealizability of Distributed Fault-tolerant SystemsBernd FinkbeinerLeander TentrupWriting formal specifications for distributed systems is difficult. Even simple consistency requirements often turn out to be unrealizable because of the complicated information flow in the distributed system: not all information is available in every component, and information transmitted from other components may arrive with a delay or not at all, especially in the presence of faults. The problem of checking the distributed realizability of a temporal specification is, in general, undecidable. Semi-algorithms for synthesis, such as bounded synthesis, are only useful in the positive case, where they construct an implementation for a realizable specification, but not in the negative case: if the specification is unrealizable, the search for the implementation never terminates. In this paper, we introduce counterexamples to distributed realizability and present a method for the detection of such counterexamples for specifications given in linear-time temporal logic (LTL). A counterexample consists of a set of paths, each representing a different sequence of inputs from the environment, such that, no matter how the components are implemented, the specification is violated on at least one of these paths. We present a method for finding such counterexamples both for the classic distributed realizability problem and for the fault-tolerant realizability problem. Our method considers, incrementally, larger and larger sets of paths until a counterexample is found. For safety specifications in weakly ordered architectures we obtain a decision procedure, while counterexamples for full LTL and arbitrary architectures may consist of infinitely many paths. Experimental results, obtained with a QBF-based prototype implementation, show that our method finds simple errors very quickly, and even problems with high combinatorial complexity, like the Byzantine Generals' Problem, are tractable.https://lmcs.episciences.org/1588/pdfcomputer science - logic in computer science |
| spellingShingle | Bernd Finkbeiner Leander Tentrup Detecting Unrealizability of Distributed Fault-tolerant Systems Logical Methods in Computer Science computer science - logic in computer science |
| title | Detecting Unrealizability of Distributed Fault-tolerant Systems |
| title_full | Detecting Unrealizability of Distributed Fault-tolerant Systems |
| title_fullStr | Detecting Unrealizability of Distributed Fault-tolerant Systems |
| title_full_unstemmed | Detecting Unrealizability of Distributed Fault-tolerant Systems |
| title_short | Detecting Unrealizability of Distributed Fault-tolerant Systems |
| title_sort | detecting unrealizability of distributed fault tolerant systems |
| topic | computer science - logic in computer science |
| url | https://lmcs.episciences.org/1588/pdf |
| work_keys_str_mv | AT berndfinkbeiner detectingunrealizabilityofdistributedfaulttolerantsystems AT leandertentrup detectingunrealizabilityofdistributedfaulttolerantsystems |