Solutions to homework 2

Notice:
Some (not all) of these solutions are copied from those of the students. In observance of Swedish customs their identity is not disclosed (Elitism is not politically correct).

Q1.

(3+4+4+4 pts)

1.

An easy example is a leaf $\pi p$, with p a traitor; p can send $(\pi,x)$ to i and $(\pi,\bar{x})$ to j, with i and j loyal. Then, $tree_i(\pi p) \neq tree_j(\pi p)$.The claim follows since, by definition, for a leaf $\ell$ $resolve_i(\ell)=tree_i(\ell)$ for all loyal i.

2a.

The traitors can generate a chain reaction as follows. In round 1, a traitor p sends $[\mbox{\sc Init}, (c,p,1)]$ to a loyal process q₁. This prompts q₁ to send $[\mbox{\sc Echo}, (c,p,1)]$ to all in round 2. Also in round 2, the f traitors send $[\mbox{\sc Echo}, (c,p,1)]$to a second victim q₂ which, having received a threshold of f+1 distinct echoes, by rule 3 of the protocol will send its own $[\mbox{\sc Echo}, (c,p,1)]$ to all. At round 3, a third loyal victim q₃ is selected; the traitors send to q₃ f distinct $[\mbox{\sc Echo}, (c,p,1)]$'s which, together with the echoes of q₁ and q₂, give a total of f+2 distinct echoes received. Again by rule 3, q₃ will send its $[\mbox{\sc Echo}, (c,p,1)]$ to all. By continuing in this fashion, the number of distinct echoes increases by 1 every round. Thus, it takes at least f+1 rounds to reach the threshold of 2f+1 distinct echoes needed by rule 4 to accept (f echoes are kindly provided by the traitors who, however, could make this last a bit longer, i.e. f more rounds). Since f>n/3 this is larger than any constant.

2b.

Yes. Two traitors p₁ and p₂ can do the following. p₁ sends an $[\mbox{\sc Init}, (c,p,r)]$ to a proper subset of loyalists of cardinality 2f. These will echo in round r+1. In round r+1, traitor p₂ also sends $[\mbox{\sc Echo}, (c,p,r)]$ to all to make a total of 2f+1 distinct echoes which, by rule 4, makes all loyalists accept.

2c.

The answer is f<n/3. A possible proof, hopefully to appear in a later edition of this sheet, mimics the impossibility proof for Byzantine Agreement.

Q2.

(10 pts)

(a)

One of the many possible solutions is as follows. Given a protocol running in T rounds in the perfectly synchronous model, we simulate it in our partially synchronous model in 2T rounds. Each round in the perfectly synchronous model is simulated with two rounds which we call a phase. Processes only send at even numbered rounds, i.e at the beginning of a phase. Set $\epsilon < 1/6T$ and $\delta < 1/3$. After 2T rounds the difference between the slowest and the fastest clock is < 2/3 and since message delivery time is greater than 2/3 and smaller than 4/3 it is never the case that a message sent at phase k is received at phase $l\neq k$.It turns out however that $\delta$ and $\varepsilon$ can be arbitrary. Consider the exponential protocol, given in the lecture, for the synchronous Byzantine agreement problem. This protocol can be adapted to this only partially synchronous setting in the following way. Suppose that processor p receives $(\pi,x)$ from p' at a given time (or possibly in the time elapsed since the last time the processor was awake). If p has not received any message from p' concerning $\pi$,then it stores x at $\pi p'$ and, if $\vert\pi\vert < f$,sends $(\pi p',x)$ to everybody. The turn-around time for one round of this protocol is $< 1+\delta + 1+\epsilon = T$ as each message takes $\leq 1+\delta$ to arrive at its destination, where it will be taken care of in at most $1+\epsilon$ time units. The loyal processors will hence have communicated the same information as in the fully synchronous case after $\leq (f+1) \cdot T$ time units, and we therefore let them freeze their data trees after $\lceil (f+1)T/(1-\epsilon)\rceil$ ticks of their local clocks -- this way also the processor with the fastest clock will have received all the information it needs from the loyal processors (since the failure are byzantine the algorithm is guaranteed to work regardless of the information sent by the traitors). The information is then processed in the same way as before.

We conclude that Byzantine agreement is possible in this partially synchronized setting for any $\delta$ and $\varepsilon$.This, of course, assumes FIFO channels.

(b)

One possible objection is that it is assumed that the clocks are initially perfectly synchronized- which appears problematic, to say the least.

Q3.

(10 pts)]
The answer to this problem is very sensitive to the assumptions made. The standard assumptions are as follows. First, the failure mode adopted is this: if a process crashes while sending messages, some processes might receive messages and others might not. We refer to this as nasty crashes. Second, we adopt the usual non triviality condition and we dub it weak non triviality: if all processes have initial value v then, the only admissible decision value is v.

In contrast to these, we could have nice crashes, which assumes that broadcasts are atomic and is defined as: a process never crashes in the midst of sending messages, i.e. either everybody receives the message or nobody at all. We could also have strong non triviality which states that: if all non faulty processes have initial value v, then the only admissible decision value is v. As we shall see, this is a much stronger requirement because a process may die after having sent the last message and before making a decision and a crash cannot be detected after the last message was sent.

Since the exercise left these interpretations open, solutions adopting them were quite welcome.

Under the assumptions of nasty crashes and weak non triviality we now give an f-resilient protocol running in f+1 rounds that works for any $f \le n$.

CONSENSUS ALGORITHM FOR PROCESS P_I.
$S_i := \{x_i\}$ (Comment: recall x_i is input value; S_i is a set);
for k = 1 to f+1 do;

send S_i to all;
collect $S_1 \ldots S_n$;
$S_i := \cup_j S_j$;

endfor
decide on the minimum of S_i

In other words, processes repeatedly send all values observed so far to everybody and select the minimum at the end. Weak non triviality and limited bureaucracy are obvious. For agreement it is enough to show that if a process p decides v then all processes who decide also decide on v. This follows if we prove that the sets S_i are the same.

Claim 13965

If $v \in S_p$ then $v \in S_q$ for all non faulty p and q.

Proof. Let r be the first round in which v was added to S_p. If $s \le f$ then p itself sends this value to all at round f+1. Otherwise, r=f+1 and let p_f+1 be the process who sent q the value v at round f+1. If p_f+1 sent the value earlier we are done. Otherwise, since p_f+1 is sending v only at round f+1 and not before, there must be another process p_f who sent this value to p_f+1 at round f. If p_f is non-faulty we are done. Otherwise, there must have been a prior sender p_f-1, and so on. How long can this go on? Since there are f+1 rounds sooner or later we must find in this chain a non-faulty process p_i whose v reached all aother non-faulty processes. $\Box$can be shown that f+1 rounds are also necessary.

Some people opted for nice crashes and weak non triviality and gave a different protocol, which takes only 2 rounds but assumes f<n/2.

TWO ROUND CONSENSUS FOR PROCESS P
round 1: send x_p to everybody;
round 2: set d_p to 1 if and only if at least f+1 distinct 1's are received.

Limited bureaucracy is immediate. For agreement and strong non triviality observe that if all non faulty processes have the same value this defines a majority value > f. Moreover, observe that if p decides 1 it means that it received f+1 distinct 1's. Since crashes are nice, these 1's were also received by all other non faulty processes which therefore decide 1 as well.

But strong non triviality needs the assumption f<n/2. To prove this we exploit the fact that processes might die between the time their last message was sent and the time they decide. Take for example n=2 and two processes p and q with initial values 0 and 1 respectively. If q dies just before making a decision then strong non triviality implies that the only admissible decision value, for any protocol, is 1. But if p dies instead, by symmetry the only admissible decision value, for any protocol, is 0- a contradiction. The example generalizes to n>2.

Finally, here is a solution under the strongest assumptions of strong non triviality and nasty crashes. (This scenario is considerably more difficult to handle than the previous ones). We divide processes into two sets L and T which contain processes that live long and prosper, and processes that terminate prematurely, respectively; let $n=\vert T\cup L\vert$. Now, assume |L|>|T|, and consider the following protocol.

1.

Initially, let $m \leftarrow n$ (m is an estimate of the number of processes that are alive).

2.

Transmit x_p to everyone.

3.

If less than m messages are received, transmit ``Alert: Condition red'' to everyone.

4.

For |T| rounds, echo any received ``Alert: Condition red'' messages that are received.

5.

If no ``Alert: Condition red'' message was received (and m assessments were received, but that is actually implied since this process didn't receive an ``Alert: Condition red'' message from itself), decide according to the majority of the messages received.

Otherwise, decrease m by one and repeat the protocol from 2.

The number of rounds used is obviously O(|T|²).

The protocol is correct for the following reason: First we observe that if everyone computes the majority of the assessments of all $p \in L$, and of some subset of T, then the protocol decides correctly providing the same subset of T is used for all processes to decide. (Agreement follows since they compute majority of the same data, and non-triviality since if x_p=0, $\forall p\in L$, then the majority is always since |L|>|T|. The case x_p=1 is analogous.)

We notice that m is always greater than or equal to the actual number of live processes, since it is decreased by one only after it happened that not all processes received m messages. So, when deciding, a process knows the assessment of everyone else still alive, and it has not received an ``Alert: Condition red'' message. We have to check that everyone else still alive will also make a decision the same round. (As long as processes are alive, they will have the same value of m, since m is decreased by one for each repetition of 2-5 until the protocol stops.)

The only way that some processes may decide, while others still run the protocol, is that the processes that still run the protocol receive the ``Alert: Condition red'' message in the last round of 4. But this message must have originated from someone at the first round of 4, and since at most |T| processes may die, this is not possible.