COMPSCI 711
Page 1 of 4
THE UNIVERSITY OF AUCKLAND
SEMESTER TWO 2018
Campus: City

COMPUTER SCIENCE
Parallel and Distributed Computing
(Time Allowed: TWO hours)
NOTE: Attempt ALL questions.
COMPSCI 711
Page 2 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)

COMPSCI 711
Page 3 of 4
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.
(10 marks)
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: ,
COMPSCI 711
Page 4 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)