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)

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)