Detecting unrealizability of distributed fault-tolerant systems

DOI10.2168/LMCS-11(3:12)2015MaRDI QIDQ3196343zbMATH OpenOpenAlexFDO

Authors Bernd Finkbeiner, Leander Tentrup

Publication date 29 October 2015

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.06862

zbMATH Keywords

fault-tolerancedistributed synthesiscoordination logic

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Reliability, testing and fault tolerance of networks and computer systems (68M15) Specification and verification (program logics, model checking, etc.) (68Q60) Temporal logic (03B44) Logic in computer science (03B70)

Abstract: 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.

Recommendations

• Synthesis of fault-tolerant distributed systems
• A short counterexample property for safety and liveness verification of fault-tolerant distributed algorithms
• Distributed synthesis for regular and contextfree specifications
• Synthesis of self-stabilising and Byzantine-resilient distributed systems
• Diagnostic Information for Realizability

Cited in

(7)

• scientific article; zbMATH DE number 7447736 (Why is no real title available?)
• Diagnostic Information for Realizability
• Distributed synthesis for parameterized temporal logics
• Synthesis from hyperproperties
• Two SAT solvers for solving quantified Boolean formulas with an arbitrary number of quantifier alternations
• Synthesis of fault-tolerant distributed systems
• scientific article; zbMATH DE number 1006803 (Why is no real title available?)

This page was built for publication: Detecting unrealizability of distributed fault-tolerant systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3196343)