Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMPSCI 711

SEMESTER TWO 2020

COMPUTER SCIENCE

Parallel and Distributed Computing

Question 1 [10 marks]  Time Complexity for Distributed Algorithms

Discuss the time complexity measures for distributed algorithms, comparing the synchronous and the asynchronous measures (with and without FIFO).

(a) Briefly describe the typical definitions of the time complexity for synchronous distributed algorithms.

(b) Briefly describe the typical definition of the normalised time complexity for asynchronous distributed algorithms, detailing its specific variants for

I.      the FIFO scenario, and

II.      the NON-FIFO scenario.

(c) Briefly discuss the relationship between the synchronous and normalised asynchronous cases. Which one is always greater or equal than the other, and why? Outline a convincing argument (proof).

Question 2 [10 marks] - Logical clocks and applications

Discuss logical clocks, compare Lamport clocks with vector clocks, and - as an application - illustrate the Money count distributed snapshot.

(a) Define logical time in terms of the happens-before relation between events.

(b) Consider the  following  events  sequences  at processes P1, P2, P3, where  si   and ri   are corresponding send and receive events.

P1 time-line:  s1,  r2,  r6,  r5

P2 time-line:  s2,  r1,  s3,  r4,  s5

P3 time-line:  s4,  r3,  s6

(c) Annotate all events with Lamport clock values one line for each process, e.g. P1 time-line:  s1 :1,  …

(d) Consider that  each process  starts with  an  initial  value  of  100  $$  and  each message represents a transfer of 10 $$.

(e) According to the Money Count algorithm, what are the processes’ balances at Lamport time 4.5?

(f)  Annotate all events with vector clock values, e.g.

P1 time-line:  s1 :(1,0,0),  …

(g) Critically compare Lamport clocks with vector clocks (essential differences, why would one use vector clocks instead of Lamport clocks).

Question 3 [10 marks]  Cidon’s DFS

Discuss Cidon’s distributed DFS and explain how it improves over the naïve distributed DFS. If needed, use the following network diagram to clarify your arguments.

As an example, consider the following network, where node #1 is the start, and the following message types: fwd (forward), ret (return), vis (visited), and assume that fwd also carries the vis token.

 

(a) Using the  above  diagram,  identify  a particular  asynchronous  execution  in which  the forward token is sent to an already visited node.

Illustrate  this  execution  by  time-lines,  one  for  each  node,  indicating  sent/received messages and their global timestamps, using integer numbers (so the smallest time unit will be 1), e.g.:

P1 timeline:  send1(fwd):0,  …

P2 timeline:  receive1(fwd):1,  send2(fwd):1,  send3(vis):1,  …

(b) How many messages are sent in scenario (b) and what is its normalised time complexity?

Question 4 [10 marks]  Bellman-Ford async vs sync

Discuss   the   distributed   Bellman-Ford   algorithm,   and   compare   its   synchronous   and asynchronous versions. Explain why the exponential worst case for the asynchronous version cannot be adapted to construct a similar worst case for the synchronous version.

(a) Complete  the  diagrams  that  highlight  the  exponential  message  complexity  of the asynchronous Bellman-Ford algorithm, by actually indicating required arc delays as integer numbers, starting with 1 for the fast (up/down green) edges.

For example, if delay(e,f) = delay(f,g) =  1, then delay(e, g) = 3. What are delay(c,e), delay(a,c), delay(g,h)?

(b) Counting the hops” from right to left, we have delay0 = delay(e,g) = 3, delay1 = delay(c,e) = ?, delay2 = delay(a,c) = ?. What is the general formula, for delayk?

(c) A delay of m time units could be synchronously simulated by inserting m- 1 intermediate nodes. For example, to achieve a delay of 3 time units, we could insert two additional nodes between e and g.

Discuss why this construction could not force an exponential number of messages in the synchronous Bellman-Ford algorithm.

 

Question 5 [10 marks]  Distributed MST / Boruvka

Assuming that edge weights are unique, prove that:

(a) In any multi-way merge there is always one Common MWOE.

(b) The Common MWOE is unique.

Question 6 [10 marks] - Byzantine agreement

Outline a convincing proof that three (3) participants cannot solve the Byzantine agreement in the possible presence of one (1) faulty processor. Use a proof by contradiction based on the hexagon thought experiment.

Hint: this proof is a thought experiment, based on the following diagram:

 

Question 7 [10 marks]  EIG Trees measures

Consider an EIG tree, for N processes, at most F of which faulty, and L messaging rounds. A node is called distinguished if its label ends in a non-faulty participant number.

(a) List the EIG tree, one line per level, for the case when N=3, L=3. Each node should appear with itsfull label, e.g. x.y.z, not just z.

(b) List, in left-to-right order, the nodes of a common path covering, for the case when N=3, L=3, when processes #1 and #2 are faulty.

(c) Give a general formula that determines the number of all EIG nodes at given level K (as a function of N and K). Briefjustification required.

(d) Give a general formula that determines the number of EIG sibling groups at given level K (as a function of N and K). Briefjustification required.

(e) Give a general formula that determines the number of EIG siblings in a group, at given level K (as a function of N and K). Briefjustification required.

(f)  Give a general formula that determines the message size (number of values) at messaging round K (as a function of N and K). Briefjustification required.