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.
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.
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).
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)
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.
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:
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.