Skip to topic | Skip to bottom
Minfo.DistTD2r1.30 - 01 Oct 2018 - 13:57 - FrancoiseBaudetopic end

Start of topic | Skip to actions
For Monday October 8th 2018

Solve the exercise about Cristian's physical clock accuracy. Indeed, this corresponds to solving exercise 2 of the Exam given in 2012. The pdf file URL is recalled here.

Solve this question: If events corresponding to vector timestamps Vt1, Vt2, ... , Vtn are mutually concurrent (or independent), then explain ("explain" means informally prove, use examples of your own, etc) that Vt1[1] , Vt2[2], ... Vtn[n] == max (Vt1,Vt2, ..., Vtn). The operation max means that , as we have done in the lesson, you take the max of all Vti line per line.


You find here all the exercices for this course about logical and physical time, including an English translation for the first 2 exercices.

To get more details about Clocks, you can browse the Krakowiak paper (in additional material section)

About the Exercice 2 and some follow-ups:

You can get a correction of this exercise as it appears on the official list of exercises (notice that it does not include a specific answer to the two specific questions that you had to solve below, but it is a good general answer).

Use vector clocks, to continue the second exercise. In particular, solve the question 6. For this, consider the following definition of what is the vector clock associated to a cut that goes through (i.e. that cuts) the set of processes P1...Pn

* For all events that constitute the frontier of the cut, represented respectively by their vector clocks VC1, VC2...VCn, the vector clock associated to the cut VCut is defined by VCut[j]=max(VC1[j],VC2[j],...,VCn[j]) for all 1<=k<=n

* A cut is consistent if for any k, 1<=k<=n, VCut[k]=VCk[k]

Use that definition to show, and to explain using your own words, if the cuts C, C', and C'' are consistent or not. Draw an additional cut onto the diagram, D, whose frontier is defined by events d1, b2, c3. Explain why D is non consistent.

You find a reasonable solution for exercise 3, but in French.

You should understand the exercise 4 as follows: the goal is to receive messages in the order of the timestamp that is shown in the received messages. We do not really care about at which local time, each process treats each message. Here, eventually a solution for this apparently not so easy exercise!

Here is an acceptable answer for exercice 5!

Here is a nice and more advanced slides set corresponding to this course

How to make vector clocks less memory consuming (i.e. not using N entries mandatorily if N processes are in the system). For this, study this nice proposition An Exercise which was proposed in 2013 consisted in the following : read the above paper, and apply the proposition to the diagram of exercise 2. Showing in particular on process P1,how it is possible to handle a clock of size less than 3 entries, until event d1 happens.

-- FrancoiseBaude -

to top

You are here: Minfo > DistributedAlgo > DistTD2

to top

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