Skip to topic | Skip to bottom
Minfo.DistTD3r1.23 - 08 Nov 2017 - 17:25 - FrancoiseBaudetopic end

Start of topic | Skip to actions
* New exercise for November 6th 2017 * solve this brand new exercise, that one student suggested to have during the lecture! Here is a correction from one student. CORRECTION

Implement differently as we did in the lecture, the module perfect point 2 point link (pp2p). Instead of relying upon the stubborn p2p module. Apply instead the idea which is to have each receiver of a message to send back an acknowledgment to the emitter. Of course, you can now only rely on the fair loss p2p module (flp2p). That, I recall, drops messages with a non-zero probability. (which implies that a message arrives at its destination with a non zero probability). Make sure to discuss all the expected properties that the pp2p module must feature.

* Now, delayed and optional for November 13th 2017 * solve the exercise 2 of here.

Also complete the exercise 2 by answering to the small 2 questions below:

  • Comment on d(m3) on P2 has VCtimestamp==(2,2,0)
  • Comment on m4 having VCtimestamp==(2,2,1)


You find here the list of exercices related to this lesson, that you are advised to try alone before solving the homework, then check the published solutions. The exercise list needs to include the two space diagrams for respectively exercise 1 and exercise 2 for which you find a CORRECTION . Regarding exercise 3 : CORRECTION

  • In more detail, in exercise 1, continue the scenario illustrating the nice RBcast behaviour. Elements for getting a correct answer are the following: whatever reception order of the various messages on the correct processes, be aware that messages exchanged by the failure detectors must not be drawn, and that you must apply carefully the algorithm (that is, a process save the message emitter, not the message source (s_m), and if it learns the emitter fails, then it rebroadcasts the message in the group)
  • On the slide number 50, you are asked to provide a simple example showing why it is impossible to build a causal order GC, if you do not rely upon a Reliable broadcast GC. Give such an example. Then explain briefly with your own words, how much the properties RB1...RB4 (see slide 64) contribute to finally getting a Causal order broadcast GC.

Access to a concise, however correct, CORRECTION

================================ ADDITIONAL EXERCISE ========================

From a former exam.

Here is a Total order algorithm using a centralized sequencer :

Algorithm for TO-Bcast on each process


* On initialization, r:=0

* To TO-Bcast message m:

RB-multicast() // bcast the message to all, including to the sequencer process

* On RB-deliver()

Place in hold-back queue

* On RB-deliver(<''order'',i,S>)

wait until in hold-back queue and S=r

// the wait does not prevent the process to react to another event

// like, typically, another RB-deliver(...) concerning another i value.



Algorithm for sequencer


* On initialization s:=0

* On RB-deliver()

RB-multicast(<''order'',i,s>) // as order messages are not relevant for

//the sequencer process, we can consider that this RB-multicast

//broadcasts this message order to all processes except the sequencer


  • Question 0: Draw an example with e.g. 3 processes and the sequencer, that shows how this algorithm behaves.
  • Question 1: Explain if the total order obtained is respecting causal order in case point to point channels are not FIFO ?
  • Question 2: Explain if the algorithm as it is can handle the failure of a process (except the particular process that is playing the role of the sequencer)
  • Question 3: Propose solution to handle the failure of the sequencer itself. What is the key difficulty here ?
  • Question 4: Take for instance, in the survey paper of X. Defago, the definition of the Uniform property. In our case, we are interested by Uniform TotalOrder?. In addition to Total Order, Uniform total order adds that: "even if a non correct process delivers a message, then all correct processes must deliver it , in the same order everywhere". (alas, Non Uniform Total order claims that this has to be ensured only for correct processes). Explain why the proposed algorithm enforces Uniform Total Order.

You find here a discussion about how the Question 3 could get a solution. The other questions were solved quite well by more or less all students. However, in Question 2, few (if none) students did explicitly express the fact that the break of the causality order only came out for the case where m1 and m2 were sent by the same process. Indeed, in case m1->m2 but m2 is sent from another process than the one that sent m1, we must first deliver and process m1 on this another process, before we send m2: In this situation, the use of this sequencer algorithm imposes that m2 is delivered after m1. So the only case where total order breaks causal order is when m1 and m2 are sent by the same process, in sequence (a particular case of causality indeed) ===========================================================


Here is a list of some research papers presenting some nice group communications solutions.

But more importantly, the state of the art paper written by Defago and al. is very interesting to read (at least up to section 6 included) and this concerns this course but also a following course about failures models, failures detectors, and consensus;

- Total order broadcast and multicast algorithms: Taxonomy and Survey. By Défago, Schiper, Urban. Accessible here

- Horus, A flexible group communication system, * Horus

- Totem, A Fault-Tolerant Multicast Group Communication System, * Totem

- The Transis Approach to High Availability Cluster Communication, * Transis

- Synchronous and asynchronous group communication, * synchronous anda synchronous GC

- Using Broadcast Primitives in Replicated Databases, * Using Broadcast Primitives in Replicated Databases

- A Step Towards a New Generation of Group Communication Systems, * A Step Towards a New Generation of GCS


Additional links to similar courses, sometimes more detailed

to top

You are here: Minfo > DistributedAlgo > DistTD3

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