Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2009-12-14
EPTCS 14, 2009, pp. 92-106
Computer Science
Distributed, Parallel, and Cluster Computing
Scientific paper
10.4204/EPTCS.14.7
Previous work has shown that there are two major complexity barriers in the synthesis of fault-tolerant 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 multi-core computing in the context of deadlock resolution.
Abujarad Fuad
Bonakdarpour Borzoo
Kulkarni Sandeep S.
No associations
LandOfFree
Parallelizing Deadlock Resolution in Symbolic Synthesis of Distributed Programs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Parallelizing Deadlock Resolution in Symbolic Synthesis of Distributed Programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallelizing Deadlock Resolution in Symbolic Synthesis of Distributed Programs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-623958