Call/WhatsApp/Text: +1(838)201-9170

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

04 Oct 2022,8:30 PM


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 P1, P2,…, P6. The exact delay a message will experience over each (bidirectional) link is shown. For example, a message sent over the link between P1 and P2 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: SigA(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: MA1 = {H(M), SigA(H(M))};
    2. B ® A: SigB(H(M));
    3. A ® B: MA2 = {M, SigA(M)};
    4. B ® A: SigB(MA2);


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: MA1 = {H(M), SigA(H(M))};
    2. B ® A: SigB(H(M));
    3. A ® TTP: MA2 = {M, SigA(M)};
    4. TTP ® A: SigTTP(MA2);
    5. TTP ® B: {MA2, SigTTP(MA2)};

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]


Expert answer


A wave algorithm is an algorithm used to propagate information through a network of nodes. Wave algorithms can be centralized or decentralized. Centralized wave algorithms require a central node to initiate and coordinate the propagation of information, while decentralized wave algorithms allow each node to independently propagate information.


The main distinction between centralized and decentralized wave algorithms is that centralized algorithms are more efficient in terms of message passing, but they are vulnerable to single points of failure. Decentralized algorithms are less efficient, but they are more robust against failures.

Stuck Looking For A Model Original Answer To This Or Any Other

Related Questions

What Clients Say About Us

WhatsApp us