Question: Define a wave algorithm. What are the main distinctions between centralized and decentralized wave algorithms?

Question 1

1. Define a wave algorithm. What are the main distinctions between centralized and decentralized wave algorithms? [10 marks]
2. Describe a wave algorithm when distributed processes are arranged as a tree structure where the edges are bidirectional communication links. [16 marks]
3. The figure below shows the connectivity between six distributed processes P₁, P₂,…, P₆. The exact delay a message will experience over each (bidirectional) link is shown. For example, a message sent over the link between P₁ and P₂ will take 2 units of time to be received by the destination.

Suppose that each process starts executing the algorithm described in b) at the same time t. Describing the actions taken by the processes during the execution, determine the timing instance when each process decides and terminates the execution. You may assume that a process takes zero time to execute the instructions of the algorithm and that no process fails.   [24 marks]

Question 2

1. Presented below are the four steps of a protocol P which a player A uses to send a digital item M to another player B and to obtain a non-repudiation of receipt (NRR) from B. Notations used here have their conventional meaning: Sig_A(F) is the unique and verifiable signature of A for F; and, H() is an one-way and collision-resistant hash function.
   1. A ® B: M_A1 = {H(M), Sig_A(H(M))};
   2. B ® A: Sig_B(H(M));
   3. A ® B: M_A2 = {M, Sig_A(M)};
   4. B ® A: Sig_B(M_A2);

Show why P cannot be a fair-exchange protocol.                         [10 marks]

1. Suppose that P is modified as shown below, where TTP stands for Trusted Third Party:
   1. A ® B: M_A1 = {H(M), Sig_A(H(M))};
   2. B ® A: Sig_B(H(M));
   3. A ® TTP: M_A2 = {M, Sig_A(M)};
   4. TTP ® A: Sig_TTP(M_A2);
   5. TTP ® B: {M_A2, Sig_TTP(M_A2)};

Examine whether or not the modified version of P above is a fair-exchange protocol and justify your answer. If it is a fair-exchange protocol, what constitutes A’s non-repudiation of receipt (NRR)? On the other hand, if the modified version is not a fair-exchange protocol, suggest some ways to fix the flaw(s) identified.   [20 marks]

1. Suppose that the coordinator decides on commit during an execution of the 2-phase commit protocol and crashes after disseminating its decision to all except one server. Let that server also crash soon after the coordinator’s crash.
   1. Describe the actions which the server would carry out after it recovers. [8 marks]
   2. Given that the coordinator and the server have become prone to frequent crashes, are there situations in which the server will not be able to decide even if every node crash is subsequently followed by node recovery? Explain your answer. [12 marks]