NOTE:
COMPSCI 711 THE UNIVERSITY OF AUCKLAND
SEMESTER TWO 2019 Campus: City
COMPUTER SCIENCE Parallel and Distributed Computing
(Time Allowed: TWO hours)
Attempt Question 1 to Question 3.
Attempt THREE questions out of Question 4 to Question 7.
Page 1 of 4
Question 1
The diagram below shows the progress of two processes, P and Q. It should be assumed that the identifiers of processes P and Q are IDP and IDQ respectively. a, b, c, d, e, f and g are the seven events occurred in the processes. An arrow between X and Y represents event X sends a message which is received by event Y.
(a) If the system uses a partially ordered logical clock, what is the timestamp of each of the events in the diagram?
(b) If the system uses a totally ordered logical clock, what is the timestamp of each of the events in the diagram?
(c) Compare and contrast the partially ordered logical clock and the totally ordered logical clock in terms of expressiveness and scalability. You must provide sufficient justification for your answer.
(6 marks)
Question 2
Centralized directory model and document routing model are used in peer-to-peer systems for looking up information.
(a) Describe how the two models work.
(b) Compare and contrast the two models in terms of efficiency, reliability, and scalability. You must provide sufficient justification for your answer.
(6 marks)
Question 3
(a) Why is it difficult to obtain a consistent distributed snapshot in a distributed system? Use an example to support your argument.
(b) What are the conditions that need to be satisfied to make a global state consistent?
(c) Modify the Chandy-Lamport distributed snapshots algorithm so that all the channel states are recorded empty. You need to give a full description of the algorithm and explain why your algorithm can obtain a consistent distributed snapshot in terms of the discussion in point (b).
(18 marks)
COMPSCI 711
Page 2 of 4
Question 4 – Time Complexity for Distributed Algorithms
(a) Briefly describe one of 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).
(d) Mention well-known algorithms where there is a wide difference between:
I. the synchronous and normalised asynchronous time complexities, and
II. the FIFO and NON-FIFO normalised asynchronous time complexities.
For items I and II, NO proof or evidence is required, but indicate the order of magnitude of each time complexity (e.g. linear, polynomial, exponential, in N, in M)
(10 marks)
Question 5 – EIG Trees
Consider an EIG tree, for N participants, 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) Draw a tree diagram and highlight all distinguished nodes, for the case when N=4 and participant #1 is faulty.
(b) For an arbitrary N, assuming that L>F, prove that any root-to-leaves path passes through at least one distinguished node.
(c) For an arbitrary N, assuming that N>3F, prove that, at each level, any sibling group contains a majority of distinguished nodes.
(d) For an arbitrary N, prove that both conditions (b) and (c) are achieved when N 3F +1. (10 marks)
Page 3 of 4
COMPSCI 711
Question 6 – Byzantine Agreement – Impossible Scenario
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:
(10 marks)
Question 7
(a) What is the goal of the distributed Bellman-Ford algorithm, what does it try to achieve
(DFS, BFS, MST, or otherwise)?
(b) Discuss the exponential message complexity of the asynchronous Bellman-Ford algorithm. Base your discussion on the sample diagram below – which is a simplified version of the diagram used in the lectures.
(c) Based on (b), discuss how the time complexity can also be exponential, in the FIFO scenario.
COMPSCI 711
________________________________________
Page 4 of 4
(10 marks)