Parallelizing Deadlock Resolution in Symbolic Synthesis of Distributed Programs
Open Access
- 15 December 2009
- journal article
- research article
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 14 (14) , 92-106
Abstract
Previous work has shown that there are two major complexity barriers in the synthesis of faulttolerant distributed programs: (1) generation of fault-span, the set of states reachable in the presence of faults, and (2) resolving deadlock states, from where the program has no outgoing transitions. Of these, the former closely resembles with model checking and, hence, techniques for efficient verification are directly applicable to it. Hence, we focus on expediting the latter with the use of multi-core technology. We present two approaches for parallelization by considering different design choices. The first approach is based on the computation of equivalence classes of program transitions (called group computation) that are needed due to the issue of distribution (i.e., inability of processes to atomically read and write all program variables). We show that in most cases the speedup of this approach is close to the ideal speedup and in some cases it is superlinear. The second approach uses traditional technique of partitioning deadlock states among multiple threads. However, our experiments show that the speedup for this approach is small. Consequently, our analysis demonstrates that a simple approach of parallelizing the group computation is likely to be the effective method for using multicore computing in the context of deadlock resolution.Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Multicore Constraint-Based Automated StabilizationLecture Notes in Computer Science, 2009
- Measuring and Evaluating Parallel State-Space Exploration AlgorithmsElectronic Notes in Theoretical Computer Science, 2008
- Diconic addition of failsafe fault-tolerance2007
- Parallelising Symbolic State-Space Generators2007
- Exploiting Symbolic Techniques in Automated Synthesis of Distributed Programs with Large State Space2007
- A work-efficient distributed algorithm for reachability analysisFormal Methods in System Design, 2006
- Achieving Speedups in Distributed Symbolic Reachability Analysis Through Asynchronous Computation2005
- Component based design of multitolerant systemsIEEE Transactions on Software Engineering, 1998
- Synthesis of fault-tolerant concurrent programs1998
- Using branching time temporal logic to synthesize synchronization skeletonsScience of Computer Programming, 1982