Skip to topic | Skip to bottom
Minfo.DistTD1r1.36 - 28 Sep 2018 - 06:59 - FrancoiseBaudetopic end

Start of topic | Skip to actions
You find in this partly French written document some interesting exercices related to this first course. Do not forget that additional, smaller exercises, may be spread in the slides. And additional interesting exercises are provided below.

For Monday 1st of October 2018: two exercises


Relevant use of the Probe/Echo Algorithm :

Design a specific application of the Echo algorithm presented in exercise 3, to count the number of processes in a network whose topology is a connected graph. Take the Echo algorithm sketched here and further commented (in English) on pages 1 and 2 of this document.

Each process is supposed to have an identifier, but you can (must) solve the problem without needing to take advantage of this knowledge. The only assumption about the network that is needed is which are your neighbour processes. Be careful in this algorithm, because the graph is not mandatory a tree... meaning that you can receive, as in the Echo algorithm, a "info" message more than once, from more than one of your neighbours. So be careful in this case! The algorithm starts when an initiator node (assume we have exactly one such) sends out a "info message" to each of its neighbors, and ends when the initiator has received an echo or an info from each neighbor. When the algorithm terminates, the initiator of the algorithm should figure out the count. Also, do not forget to define which precise sort of information an "info" or an "echo" message must propagate. Briefly argue why your solution gives the correct total number.


Tel election algorithm

Sketch a possible execution of the Tel Election leader algorithm, on the following graph of nodes, assuming communication links are bi-directional. You can read on the algorithm code, and from the exercise description, that we will elect the leader whose identity is the largest. The algorithm for this election for any kind of topology, is described from page 3 of this document, section 3.2.

First write it down on the paper that you will give back to me, so to make it clearer than it is. In particular, take the chance to correct the typos that are indicated as comments in the PDF: these typos are about the leader_trouvé message type, that at some places should replace the chercher_leader message type. Explain why we need this additional message type, what role(s) messages of this type play in the whole algorithm. For this, refer to course at slide number 16. Explain why we could remove the parameter K in the messages tagged "leader_trouvé".

Secondly explain why we don't need an explicit echo message type as we had in the Probe Echo algorithm ? However, this echo is somehow still needed, but, how do a process knows that it has to send an echo to its father ? To make things not too long (for you, and for me), first, exemplify how a Echo algorithm execution initiated by node F execute. Then, do the same from node B. Then generalize by synthetically describing, assuming all nodes spontaneously start the election process, how this algorithm elects F as the leader. As we have done in the course, none of the process has a global knowledge of the whole network (i.e., it just knows who are its neighbours it can send or receive messages from).

Here is the graph description:

(source node id, destination node id) => on Node A: (A,B) (A,C); on Node B: (B,A) (B,C) (B,D); on Node C: (C,A) (C,B) (C,D); on Node D: (D,B) (D,C) (D,E) (D,F); on Node E: (E,D); on Node F: (F,D);

============ Previous years homeworks ================

Exercise around Zookeeper

Start documenting yourself about the virtual shared memory model defined by Zookeeper (abstraction of globally shared, hierarchically organized znodes).

Then, consult at the following URL, how Election in Zookeeper could be designed.

Add the Proclamation phase that is mentioned as missing.

Compare this approach with the next client(s) server exercise.


1) A Simple central server based election algorithm (distributed but not purely peer-to-peer algorithm) Here you find a correction by one student

Define a client(s)-server message-passing based approach to support election. The server process that hosts "the election service", is the receiver of the information sent by candidates which are the client processes. Describe the respective server and client message-based algorithms. You will have to devise an algorithm where the elected process is not the one that has the greatest identity in the network. Indeed, remember that we do not really care who is elected ! The only thing we care is that one and only one is elected and that all agree about the election outcome.

Do not forget to define how the server proclaims the result of the election, i.e. how a client is informed of the result of the election, be it candidate or simply willing to know who is currently the leader. As we have done in the course, none of the processes has a global knowledge of the whole network (i.e., the server process does not even know how many client processes could contact it to be elected). The topology might be considered here as a star, where the server stands in the center, and each client is able to communicate with this server process; but the server does not know how many clients know its identity: this is why we assume the server does not know how many clients there is in total.

In this version, assume there is an external knowledge (an oracle), that might allow to detect that the current leader has failed, and that a new election must take place. Say differently, the problem to detect when the current leader identity is not anymore valid is outside the scope of this exercise. However, just for you, think about how this detection could happen. This will be a good transition for the course of the next monday.

What is the cost (in terms of parallel time, and total number of exchanged messages) of this algorithm. As for the first exercise above, you can assume that all client processes are candidates to be elected. Discuss about its drawbacks.

2) A relevant use of the Probe Echo algorithm

Exercise from 2014-2015 univ year (just for your information!): this exercise is an application of the Probe/Echo algorithm for any topology. See below about Exercise 3 some links to get an example of the general structure of the Probe-Echo algorithm. The applications is from an initiator, (say A) to get a complete view of the network topology and associated bi-directional links performances. Assume the topology of the network involves some nodes (6 in the example below), each link is bi-directional and the measured in-coming bandwidth performance is indicated. Each node locally (and initially) knows the name of its neighbours, and the measured performance of the link that connects this neighbour to it. For instance, node A knows it has neighbour B, and the measured bandwidth from B to A as measured on A is 1. It also has node C as neighbour, and measured performance is 2. Here, on each node, is the local information

(source node id, destination node id, performance of the link as measured on the source node) on Node A: (A,B, 1) (A,C, 2) on Node B: (B,A,2) (B,C,2) (B,D,4) on Node C: (C,A,3) (C,B,3) (C,D,3) on Node D: (D,B,1) (D,C,1) (D,E,3) on Node E: (E,D,1) on Node F: (F,D,2)

The goal is, say on node A the initiator, to collect all the triples I enumerated above. I.e. on this example, node A could receive two echo messages, one from B, one from C (or alternatively but perhaps less probable, one echo from B and a probe message from C). Depending on the way the probe messages visited the sub-graph rooted at respectively B and C, it could be the case that the first echo message received from B includes only information related to B, whereas the echo message received from C includes the aggregated information coming from the whole spanning tree rooted at C ie, from D, E, and F. In any case, the resulting output from A when it terminates has to be an aggregated set of such triples without any duplicate.

Your algorithm must be written using the notation seen in the course, with guards, block of actions. A local boolean variable initiator is declared on each process, and it is only true on one process. This means a same piece of code is deployed on each process, but in order to make sure that it executes on the initiator only, you write it like this:

Ci: {initiator=true and xxx} code to run

You can tag your messages, like e.g. "probe" or "echo", and if you want a piece of code only executed for a echo message, you can have as guard

REi: {a message of type "echo" is ready to be consumed and contains as information a field named "set_triples"} receive the message; rest of your code, that extracts "set_triples" from message payload and does what is needs to do with it

Provide both your complete algorithm, and one possible execution on the network provided as example. Show explicitly which probes and echos messages are exchanged. Is it the case that each bi-directional link is traversed by exactly one probe and one echo message, each in the opposite direction ? Whether it be yes or no, argument your reply.

Explain why such a probe echo algorithm application that collects all information about the network could be used for making a leader election based upon identifying the process that has the highest identifier ? However, what is the main drawback (think about the obvious fact that the leader is not known prior to be elected!). Consequently, argument with your own words, why the approach for leader election as proposed in correction of the exercise 3 is more appropriate.

YOU FIND HERE THE CORRECTION provided by one student !

==================== Exercices distributed in the course (last stampled pages) ===============

You find here all the exercices related to this first course. Do not forget that additional, smaller exercises, may be spread in the slides.

Some info about Exercice 2: provide a possible execution of the Routing Table computation given the provided graph, and taking ideas from algorithm page 8 of Mattern article. Here is a correction for this exercise 2.

TRY alone to do exercise number 3 about a generalization of Chang and Roberts election algorithm for any connected graph. Take the Echo algorithm sketched here and further commented (in English) on pages 1 and 2 of this document , use it from any process. You can eventually have a look to the correction from page 3 of this document.

Train yourself on the interesting exercise number 4 (take care of using all assumptions given in the instructions). See here a partially correct solution. BUT THIS SOLUTION provided in 2011-2012 was INCORRECT. So, at the end of this incorrect solution, you find additional assumptions that can help to get a correct solution. This constitutes the newest version of the exercise. For which, you FIND here a CORRECTION.

exercise number 5 which I recall here: (from Ghosh book, chapter 5) Consider an *anonymous distributed system consisting of N processes. The topology is a completely connected network and the links are bidirectionnal. Propose an algorithm using which processes can acquire unique identifiers. (Hint: use coin flipping, and organize the computation in rounds).*

Some more explanations: You can assume that the number of processes N is a power of 2. You can provide a solution that is terminating after a number of rounds that is eventually high with a high probability. I think the interesting aspect of this exercise as a training effort for this chapter, is coming from the fact that I'm asking to organize the algorithm in rounds. So give precise information regarding how the processes can be informed about what is the current round executing, and at which moment, each process is aware that the current round has finished. You will assume that the topology is a complete graph which means that any process has N-1 in-going and out-going (so, bidirectional) communication channels (so that means that the total number N of alive processes that run the election algorithm is known). Even if real IDs of processes are never shown, a process can identify from whom a message is arriving by knowing the channel ID. This means that if at the end, a process receives from channel number C indicating that process sending this message on C claiming that it is the leader, this is a way to memorize who is now the leader that has been elected. This means that in the future, if the process needs to send a message to the leader, then it simply will send it using channel number C.


For the fun, here Proof for the total number of messages in average in the Chang & Roberts algorithm

-- FrancoiseBaude -

to top

You are here: Minfo > DistributedAlgo > DistTD1

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