Homework 2

Q1.

CONSISTENT BROADCAST AND BYZANTINE AGREEMENT.
Note: Consistent Broadcast was incorrectly termed ``Atomic Broadcast'' in class.

1.

Recall the analysis for the exponential algorithm explained in class to attain Byzantine Agreement; show that not all tree nodes need be common.

2.

Consider the protocol given in class to implement Consistent Broadcasts. (a) Show that there is no upper bound on the time until a non-faulty process accepts a message. That is, for any t, produce an execution of the protocol in which some non-faulty process accepts the message at a round $r' \geq r+t$. (b) Suppose a faulty process p sends a message m at round r to some processes but not all of them; can such a message be accepted within 2 rounds? (c) What is the maximum number of faults that can be tolerated by a Consistent Broadcast protocol?

Q2.

REALISTIC BYZANTINE AGREEMENT? Perfect synchrony is in practice unattainable. To obviate the problem consider this more realistic model of partial synchrony. Each process p has its own clock- a function $C_p: N \rightarrow R^+$.Initially the clocks are perfectly synchronized- C_p(0)=C_q(0) for all p and q- but as time goes by they can drift apart. The maximum drift per unit of time, however, is bounded by $\epsilon$,i.e. $\vert C_p(n) + 1 - C_p(n+1)\vert \leq \epsilon$ for all p and n.

Assume moreover that messages are guaranteed to be delivered within $1 \pm \delta$.

(a) Do there exist $\epsilon$ and $\delta$ such that Byzantine Agreement is attainable? Give a protocol, with proof of correctness, or show that none exists. (b) Are the assumptions realistic?

Q3.

IS TREASON WORSE THAN DEATH? Consider a situation where n generals are seeking agreement in spite of unreliable behaviour (i.e. faults) of some of them. The type of agreement they seek is the same we saw in the Byzantine case. That is, each general g has an initial ``assessment'' of the situation $x_g \in \{0,1\}$and is to decide on a value $d_g \in \{0,1\}$ subject to the conditions of Non Triviality, Agreement and Limited Bureaucracy. Suppose however that the type of anomalous behaviour to be tolerated is the sudden demise of some of them (perhaps as a result of treacherous murder or poisoning) rather than treason. In more technical terms, the type of fault we want to consider is the so called crash failure: a process either works correctly or it stops functioning forever.

As before the system is synchronous.

Recall that a protocol is f-resilient if it can tolerate up to f failures. i.e. it works correctly as long as the number of faults is less than or equal to f.

(a) Give an f-resilient protocol or show that none exist.
(b) How large can f be as a fraction of n?