Exploiting Symbolic Techniques in Automated Synthesis of Distributed Programs with Large State Space
- 1 January 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 3
Abstract
Automated formal analysis methods such as program verification and synthesis algorithms often suffer from time complexity of their decision procedures and also high space complexity known as the state explosion problem. Symbolic techniques, in which elements of a problem are represented by Boolean formulae, are desirable in the sense that they often remedy the state explosion problem and time complexity of decision procedures. Although symbolic techniques have successfully been used in program verification, their benefits have not yet been exploited in the context of program synthesis and transformation extensively. In this paper, we present a symbolic method for automatic synthesis of fault-tolerant distributed programs. Our experimental results on synthesis of classical fault-tolerant distributed problems such as Byzantine agreement and token ring show a significant performance improvement by several orders of magnitude in both time and space complexity. To the best of our knowledge, this is the first illustration where programs with large state space (beyond 2100) is handled during synthesis.Keywords
This publication has 12 references indexed in Scilit:
- Symbolic Synthesis of Finite-State Controllers for Request-Response Specifications2003
- Polynomial time synthesis of Byzantine agreement2002
- Automating the Addition of Fault-Tolerance2000
- Symbolic controller synthesis for discrete and timed systems1995
- Closure and convergence: a foundation of fault-tolerant computingIEEE Transactions on Software Engineering, 1993
- Symbolic Model Checking1993
- Symbolic model checking: 1020 States and beyondInformation and Computation, 1992
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986
- Defining livenessInformation Processing Letters, 1985
- The Byzantine Generals ProblemACM Transactions on Programming Languages and Systems, 1982