NEWCASTLE UNIVERSITY
SEMESTER 1 2019/2020
DISTRIBUTED ALGORITHMS
[CSC8103]
SPECIMEN ANSWERS
[Turn Over]
[CSC8103] Question 1.
a) Define a wave algorithm. How is a wave algorithm classified to be centralised or decentralised? Propose a simple centralised wave algorithm for a small system of five processes in which each process is directly connected to every other process. [16 marks]
Hint: Every process has four neighbours.
To define a wave algorithm, assume a special internal event decide
which a process can execute
Definition: A wave algorithm satisfies
Termination: Number of events in each computation is finite
Decision: At least one process decides in each computation
Dependence: Each decide event is causally preceded by an event in each process: "decide, "p, $ep : ep £ decide.
Note: e1 £ e2 if e1 is the same as e2 or e1 causally precedes e2. [Nature: bookwork; 6 marks]
A wave algorithm is centralised, if there must be exactly one initiator in each computation.
If the algorithm can be spontaneously started by an arbitrary subset of processes, it is called decentralised.
[Nature: bookwork; 4 marks]
Page 2 of 9
A centralised wave algorithm
p broadcasts m; decides after every process has acknowledged m to p.
Correctness Reasoning (only for external examiner/checker):
Termination and Decision:
any m or ack eventually reaches the destination(s)
so, p eventually decides
Dependence:
decidep £ ackq(m) for all q in the system.
[Nature: Application; 6 marks]
b) Using the principles of wave extinction, obtain an election algorithm from the wave algorithm you proposed in (a) [14 marks]
Applying extinction
Background (Not expected of students)
Extinction extinguishes all but one of the multiple concurrent waves initiated by different initiators.
Tag each wave with the id of the initiator
Ensure that only one wave - that of the smallest process id - survives and all other concurrent waves are extinguished.
When the wave of the smallest id runs to decision, the decider (usually the initiator itself) announces the initiator of the wave as the leader.
The wave a process p is active is denoted as cawp (the currently active wave); cawp is initially udef (undefined) which is assumed to be larger than any process-id.
[CSC8103]
Page 3 of 9
[CSC8103] Application
p initiates a wave only if p < cawp; when it initiates, it sets cawp = p. When p receives a wave initiated by q:
–cawp < q: ignore the wave (extinction) –cawp = q: treat message as per A
–cawp > q: join the execution of A for q’s wave, after setting variables of A to their initial values and cawp = q.
[Nature: Application; 14 marks] Arguments (here only for checker/external):
Assume that p, q, r simultaneously initiate a wave to get elected as a leader. Say, p < q < r. Each sends mx, x Î {p, q, r}, to all others in the
system. Only p receives ack from everyone else; r will not receive an ack from p and q, and q will not receive an from p. So all waves except p’s will be quashed.
Page 4 of 9
Question 2.
a) What is meant by a fair exchange? [5 marks] Specimen Answer (Nature: Definition + Application)
An exchange is fair only if, at the end of the exchange, either: both the players obtain what they want (normal termination), or neither player gains any additional information (exceptional termination).
[5 marks]
a) 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. Show why P cannot be a fair-
[CSC8103]
exchange protocol.
1. A → B: MA1 = {H(M), SigA(H(M))}; 2. B → A: SigB(MA1);
3. A → B: MA2 = {M, SigA(M)};
4. B → A: SigB(MA2);
The protocol is not fair for the following reason.
[10 marks]
A fair exchange protocol must ensure that no party gains any advantage over the other at any stage of the protocol execution. This is necessary to satisfy the requirements of exceptional termination. After A has executed step3, B has an advantage over A. B may receive MA2, and thereby M, and claim that it did not receive because A never sent it. A cannot prove to a third party that it indeed sent MA2 and that it is B who is misbehaving. Consequently, A does not receive SigB(MA2) while B has gained M. So, the exchange is not fair by definition.
[10 marks]
c) 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)}; Page 5 of 9
[CSC8103]
Assess whether or not the modified P above is a fair-exchange protocol and justify your answer. [20 marks]
Specimen Answer (Nature: Application)
The modified protocol version is correct. Arguments to this effect earn full marks.
NRR for A is 2-fold: SigB(H(M)) from B and SigTTP(MA2) from TTP. The former assures that B has acknowledged willingness to receive M and the latter that TTP has been entrusted to pass on M to B. SigTTP(MA2) from TTP alone cannot form NRR, as B may refuse to receive M by not executing step 2, in that case A must not execute Step 3; if SigTTP(MA2) from TTP alone had been the NRR, A can execute step 3 without B executing step 2 and prove to a third party that B indeed had received M.
For SigTTP(MA2) from TTP alone to be NRR, Step 3 needs to be: A → TTP: MA2 = {M, SigA(M), SigB(H(M))};
[20 marks]
Note to the Examiner: Marks will not be severely reduced if a student takes an incorrect assessment; full marks would still be awarded for fixing any “incorrect“ flaw identified.
Page 6 of 9
Question 3
a) What is meant by blocking during an execution of a commit protocol. [5 marks]
Specimen Answer (Nature: Book Work + Application)
Blocking: It is a situation where no functioning process can decide until
the one or more crashed process recovers. [5 marks]
b) State the rules of by which a newly elected coordinator in the 3-phase commit protocol must determine the state with which it should commence its coordinating activities. [15 marks]
Specimen Answer (Nature: Book Work)
The rules: [5 X 3 marks]
Let the newly elected coordinator be s
1. s collects states of at least a majority of processes
2. s determines a state as per what it had collected, and informs
all processes to change to that state. The rules are:
a. if there is an abort then determine abort
b. if there is a commit then determine commit
c. if there is a pre-commit and a majority of processes are either in pre-commit or wait state, then determine pre- commit
d. if a majority of processes are either in pre-abort or wait state, then determine pre-abort
e. if none of the above applies, then wait to get states from more processes.
c) Construct an execution of the 3-phase commit protocol in which (i) the system has four servers and a coordinator, (ii) no server crashes and all of them initially vote to commit, (iii) the coordinator crashes while sending commit decision to servers, and (iv) at least one server decides by executing the recovery part. [15 marks]
Servers and the coordinator execute the normal part. By (ii), coordinator is sent Yes votes and by (iii) the coordinator must
[CSC8103]
Page 7 of 9
[CSC8103]
• •
receive all these votes (otherwise, it must decide on abort) and announce pre-commit; servers receive pre-commit and send acknowledgement back to the coordinator. From this point onwards, the commit decision is only final decision possible.
[5 marks]
Condition (iv) however allows many scenarios to be possible from this point onwards. One such (the simplest) scenario is given below. Here, the coordinator receives a majority of acks for its pre- commit, decides on commit and announces its decision to all but one server, and crashes. The unfortunate server decides by executing the recovery part.
(Different scenarios are possible by altering the point when the coordinator crashes after it has made its commit decision.)
Let us consider a system of 5 processes {c, p, q, r, s} where c is the initial coordinator; majority, maj >= 3. We will represent the scenario using some notations
a process is represented by a 2-tuple {status, state}
• status can be crashed (X) or working (P) or working and acting as the coordinator (Ç)
• state can be one of w, pa, a, pc, c. For a crashed process, the state shown is what is in its stable store. (Please note: c is a process-id, Ç is used for coordinator status, c for the commit state.)
Note: These notations are discussed in the lectures and are known to the students who are not expected to state them here.
The server p, which did not receive the commit message from the coordinator executes the recovery part by electing itself as the new coordinator with the support of itself, q and r.
Page 8 of 9
[CSC8103]
No. c p q r s Remarks 1 {X, {Ç, {P, {P, {P, electorate
c} pc} c} c} c} = {p, q, r}
2
{P, pc}
{P, c}
{P, c}
{P, c}
{P, c}
Server p decides on commit by rule 2b
[10 marks]
END
Page 9 of 9
