Skip to topic | Skip to bottom
Minfo.DistTD6r1.17 - 06 Nov 2015 - 13:06 - FrancoiseBaudetopic end

Start of topic | Skip to actions
Exercise for Monday 15 of October 2015 You have to write the answer for the Exercise number 1 of the Exam from 2009. This exercise is about deadlock detection. It takes some inspiration from the Dijkstra-VanGastern termination detection algorithm. Here is a correction


The exercices related to this chapter content, plus some additional exercices taken from Chapter9 from the book of Ghosh.

Here you find the best solutions given by students last years, one in French, and another in English.

For those who are interested, they can study this other termination algorithm, due to Dijkstra and Scholten, published in Information Processing Letters in 1980. A nice synthesis is also available in the book of Ghosh. This is an interesting probe-echo algorithm. If you decide to summarize how it works, you can illustrate it using a simple network of processes.

You find a correction regarding exercice 5 of Ghosh's exercices here

Here Proof of the 4 counters algorithm (sorry in French) for termination detection, by Mattern, as a complement of Exercise 1.

It is encouraged to read e.g. chapter 14 of Ghosh Book which constitutes a very nice summary of key problems in distributed transactions management.


A Zookeper version for the 2PC: consult this interesting recipe described here

Commment about the number of messages complexity, that is quoted as being a drawback: "There are two important drawbacks of the approach described above. One is the message complexity, which is O(nē)."

-- FrancoiseBaude - 16 Oct 2015
to top

You are here: Minfo > DistributedAlgo > DistTD6

to top

Copyright © 1999-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding WIKIDeptinfo? Send feedback