Skip to topic | Skip to bottom
Home
Minfo
Minfo.DistTD2r1.28 - 16 Oct 2017 - 14:15 - FrancoiseBaudetopic end

Start of topic | Skip to actions
For Monday October 9th 2017

Solve (only) exercise 4 of the list of distributed exercises. Provide just an algorithm, and not an implementation (in term of any programming language!)

For Monday October 23th 2017 Second trial ! as an optional exercise before I will make public the answer

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.

=============================

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. Here is an acceptable answer for exercice 5!

Here is a nice and more advanced slides set corresponding to this course http://www.csd.uoc.gr/~hy556/material/lectures/cs556-Section7.pdf

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 https://vs.inf.ethz.ch/edu/HS2010/VS/exercises/DVC_Landes.pdf 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.

___________________Here are additional exercises on the topic, to try on your own :

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, then explain (that means informally prove, use examples of your own, etc) that Vt1 [ 1] , Vt2[2], ... Vtn[n] = max (Vt1,Vt2, ..., Vtn) Here is a concise solution

-- FrancoiseBaude -


to top

You are here: Minfo > DistributedAlgo > DistTD2

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