NOTE:
COMPSCI 711 THE UNIVERSITY OF AUCKLAND
SEMESTER TWO 2017 Campus: City
COMPUTER SCIENCE Parallel and Distributed Computing
(Time Allowed: TWO hours)
Attempt ALL questions.
Page 1 of 4
Question 1
(a) In terms of looking up resources in peer-to-peer systems, how do the centralized directory model and the document routing model work?
(b) Assume that a peer-to-peer system uses the Chord protocol for storing/retrieving information in the system. The identifier circle used by the system consists of sixteen identifiers. Three machines have been mapped to identifiers 1, 6 and 11 in the identifier circle. Four documents are mapped to identifiers 0, 1, 2 and 7 in the identifier circle.
I. For each of the machines, indicate which document/documents is/are stored on the machine.
II. Write the finger table of the machine mapped to identifier 11.
Note: In your answer, the finger table should consist of three columns, i.e. start, interval, and finger. The meaning of each of the columns must be the same as defined in the Chord protocol. [In the Chord protocol, column “finger” is also denoted as “succ.”.]
(c) Assume that we want to build a distributed file server on top of a peer-to-peer system using the Chord protocol. How do we ensure that the files stored in the system are not lost when some of the machines in the peer-to-peer system fail permanently? In your answer, you only need to explain the principles of your solution and give an example to show how it works.
Question 2
(a) What constitutes the global state of a distributed system?
(b) What are the conditions that need to be satisfied to make the global state of a distributed system consistent?
(c) Why is obtaining a consistent global snapshot difficult in a distributed system? Use an example to support your argument.
Question 3
(a) What is the difference between the AND and the OR deadlock models?
(b) Use the principles of the weighted reference counting garbage collection to develop an algorithm that finds a set of nodes in a wait-for graph such that the outgoing edges from the nodes in this set always end on nodes in this set.
(i) You should briefly describe the basic principles of your algorithm and how your algorithm works.
(ii) You should state the termination condition of the algorithm.
Page 2 of 4
COMPSCI 711
(10 marks)
(5 marks)
(15 marks)
Question 4 – Cidon’s DFS
(a) Discuss Cidon’s distributed DFS and explain how it improves over the naïve distributed DFS. Use examples and diagrams to clarify your arguments, e.g. you can consider the following network:
(b) Describe a particular asynchronous execution in which the forward token is sent to an already visited node and what messages will be further exchanged in such context.
(7 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) Assuming that L>F, prove that any root-to-leaves path passes through at least one distinguished node.
(c) Assuming that N>3F, prove that, at each level, any sibling group contains a majority of distinguished nodes.
(10 marks)
COMPSCI 711
Page 3 of 4
COMPSCI 711 Question 6 – Algorithms for Byzantine and Stopping Agreements
(a) Outline a proof that 3 participants cannot solve the Byzantine agreement in the possible presence of one fault. Use a proof by contradiction based on the hexagon thought experiment.
(b) Discuss why EIGByz can also solve the stopping agreement, but not necessarily with the same decision as EIGStop.
(c) Describe a minimal stopping agreement example, with N=4, F=1, L=2, in which EIGByz ends with decision v’, but EIGStop ends with a different decision v”, i.e. v’<>v”.
________________________________________
Page 4 of 4
(13 marks)