COMPSCI 711 Parallel and Distributed Computing 2020
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.
2022-06-11