2006-03-23 : Automatic synchronization of multithreaded programs. Create concurrent threads and let these run independently each doing some kind of task. This could be the most concurrent code. The interleavings exhibited by such a code are unrestricted. Hey, but we know that a particular interleaving would lead to race condition or data hazard. Eliminate that that interleaving. How do we specify bad interleavings! By bad behaviours. Model check for bad behaviours and remove inteleavings leading to bad behaviour. Prune off from the computation tree!

comments expected!
muj20@cam.ac.uk

---

2006-03-24 : It would help your cause if you spoke more clearly. Ok, let me see what you are talking about here. There are two goals in concurrent code, safety and liveness. You propose starting out with zero safety and complete liveness (no synchronization) - ok. It sounds like you are suggesting we look at the set of all possible interleavings. From that set, we need to remove the bad interleavings, which are distinguishable by their bad behaviors. It's an interesting idea, but it doesn't get you much. What you are determining is all possible correct ways at arriving at a correct solution, when all you really care about is arriving at a correct solution. Why waste time looking at things you don't care about? The set of all possible interleavings is factorially huge. It's fine to consider it in a theoretical sense, but you'll want to keep it theoretical until you can apply rules to shrink it down. It's not something you can work with in a practical sense.

Let's assume we are keeping it theoretical. You'd need to look at the generator for the set, (the program) and have rules for modifying the generator until it could not produce bad interleavings. I agree, this would be a great thing to have. But you'll have to give me some concrete examples before I believe this will work. In this situation, you are talking about a program that writes programs. Sure, very possible. But you're actually asking for a program to understand and manipulate another program. That's a huge challenge. Parallelizing compilers haven't worked as well as people have hoped (to date, to my knowledge) and genetic / simulated annealing algorithms take time to run. You'll find it very hard to compete with a human programmer.

Still, I'm willing to hear more. Tell me what you would do with a concrete example: summing up all the elements of an array of integers, concurrently. How would what you propose work, when given this problem?
-- Louis! :)