Parallelizing Deadlock Resolution in Symbolic Synthesis of Distributed Programs
Abstract
Previous work has shown that there are two major complexity barriers in the synthesis of fault-tolerant distributed programs, namely generation of fault-span, the set of states reachable in the presence of faults, and, resolving deadlock states, where the program has no outgoing transitions. Although symbolic techniques can improve the performance of synthesis algorithms by orders of magnitude, efficient heuristics are still needed to overcome the aforementioned obstacles. Thus, motivated by the idea of partitioning the transition relation of distributed programs across multiple threads, in this paper, we introduce an efficient parallel "shared memory" algorithm for resolving deadlock states in symbolic synthesis of distributed programs. In spite of notorious resistance of symbolic algorithms for parallelization, experimental results show that our parallel algorithm exhibits superlinear performance improvement.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2008
- Accession Number
- ADA487982
Entities
People
- Borzoo Bonakdarpour
- Fuad Abujarad
- Sandeep S. Kulkarni
Organizations
- Michigan State University