NOTE:
COMPSCI 711 THE UNIVERSITY OF AUCKLAND
SEMESTER TWO 2018 Campus: City
COMPUTER SCIENCE Parallel and Distributed Computing
(Time Allowed: TWO hours)
Attempt ALL questions.
Page 1 of 4
Question 1
(a) Total order and causal order are two properties that multicast messages can satisfy.
I. Explain the meaning of these two properties.
II. Use an example to show why total order is important for some applications.
(b) Assume that a discussion forum has been replicated on multiple sites. Each user connects to one of the sites to read/submit messages. A submitted message needs to be multicast to all the sites. It is required that a message, say m, can only be made available to a user if all the messages that m casually depends on have been made available to the user.
I. Outline a multicast algorithm that satisfies the above requirements.
II. You should briefly describe the basic principles of your algorithm and how your algorithm works.
(14 marks)
Question 2
Page-level caching and value-based caching are two caching techniques that can be used to reduce the response time for dynamically generated pages.
(a) Describe how each of the techniques works.
(b) Compare and contrast the two techniques in terms of their effectiveness in reducing the response time, the complexity of implementing the techniques, the simplicity of adopting the techniques from clients¡¯ and web site developers¡¯ point of view, and their demand on system resources. You must provide sufficient justifications for your answer.
(8 marks)
Question 3
Paxos is a consensus protocol that has been used by many cloud computing platforms.
(a) Paxos uses version numbers to help the acceptors to decide whether they should respond to a received prepare request message. Use an example to explain why version numbers are important.
(b) According to the FLP impossibility theory, Paxos cannot guarantee termination. Describe a scenario in which Paxos does not terminate.
(c) Assume that a membership service that implements virtual synchrony is available and no process crash while the group membership changes. Explain how the implementation of the Paxos protocol can use the membership service to ensure the termination of the consensus protocol.
(8 marks)
Page 2 of 4
COMPSCI 711
Question 4
(a) Discuss the typical definition of the normalised time complexity for asynchronous
distributed algorithms, and its specifics in the FIFO scenario.
(b) Discuss the exponential message complexity of the asynchronous Bellman-Ford algorithm. Base your discussion on a sample diagram as used in the lectures (see also the figure below).
(c) Based on (b), discuss why this algorithm has an exponential time complexity, in the FIFO scenario.
(d) Discuss why the arguments used in (c) fail, in the NON-FIFO scenario.
COMPSCI 711
Question 5
(a) Demonstrate your understanding of the Byzantine problem by describing one scenario where the EIG algorithm fails to reach agreement for three nodes, N=3, with one failure, F=1, even if the EIG tree is expanded to two levels.
(b) Which of the three correctness conditions (termination, agreement and validity) will be violated in this case and why?
Hint: Consider the case when process P1 is faulty, process P2 is non-faulty and starts with v2=1, process P3 is non-faulty and starts with v3=1 and the default (tie-breaking) value is v0=0. To support your arguments, you can use EIG diagrams such as the one given below.
(10 marks)
1: ,
¦Ë: , 2: ,
3: ,
1.2: ,
1.3: , 2.1: ,
2.3: , 3.1: ,
3.2: ,
(10 marks)
Page 3 of 4
Question 6
Contrast synchronous 2PC and synchronous 3PC by designing a sample scenario with N=4 where 2PC blocks while 3PC succeeds in the maximum possible number of rounds. How many 3PC rounds are maximum possible? Justify your answer. Your scenario can be based on commented diagrams as used in the lectures.
(10 marks)
Page 4 of 4
COMPSCI 711