The Byzantine Generals Problem

byzantine.txt

Reliable systems must hanlde conflicting information.

The problem is slovable if and only if more than two-thirds loyal generals.

If messages unforgeable, the problem is solvable for any number of generals.

The algorithm must guarantee:
A. All royal generals decide upon the same plan of action.
B. A small number of traitors cannot cause the loyal generals to adpot a bad plan.

v(i): the information communicated by the ith general.

For condition A:
1. Every loyal general must obtain the same information v(1),...,v(n).
2. If the ith general is loyal, then the value that he sends must be used by every loyal general as the value of v(i).
1'. Any two loayl generals use the same value of v(i).

how a single general sends his value to the others.
-> Byzantine Generals Problem: A commanding general must send an order to his n-1 lieutenant generals such that:
IC1. All loyal lieutenants obey the same order.
IC2. If the commanding general is loyal, then every loyal lieutenant obeys the order he sends.

interactive consistency

no solution with fewer than 3m+1 generals can cope with m traitors.

reaching approximate agreement is just as hard as reaching exact agreement:
IC1'. All loayl lieutenants attack within 10 minutes of one another.
IC2'. If the commanding general is loyal, then every loyal lieutenant attacks within 10 minutes of the time given in the commander's order.

Oral messages:
A1. Every message that is sent is delivered correctly.
A2. The receiver of a message knows who sent it.
A3. The absence of a message can be detected.

let RETREAT be default order.

OM(m) sloves the Byzantine Generals Provlem for 3m+1 or more generals in the presence of at most m traitors.

1. The majority value among the v(i) if it exists, otherwise the value RETREAT;
2. The median of the v(i), assuming that they come from an ordered set.

OM(0)
1. The commander sends his value to every lieutenant.
2. Each lieutenant use the value he receives from the commander or uses the value RETREAT if he receives no value.

OM(m), m>0
1. The commander sends his value to every lieutenant.
2. For each i, let v(i) be the value Lieutenant i receives from the commander, or else be RETREAT if he receives no value. Lieutenant i acts as the commander in Algorithm OM(m-1) to send the value v(i) to each of the n-2 other lieutenants.
3. For each i, and each j != i, let v(j) be the value Lieutenant i received from Lieutenant j in step(2), or else RETREAT if he received no such value. Lieutenant i uses the value majority(v1, ..., vn-1).

LEMMA 1. For any m and k, Algorithm OM(m) satisfies IC2 if there are more than 2k+m generals and at most k traitors.

THEOREM 1. For any m, Algorithm OM(m) satisfies conditions IC1 and IC2 if there are more than 3m generals and at most m traitors.

A4: (a) A loyal general's signature cannot be forged, and any alteration of the content of his signed messages can be detected.
    (b) Anyone can verify the authenticity of a general's signature.
    
1. If the set V consists of the single element v, then choice(V) = v.
2. choice(O/) = RETREAT, where O/ is the empty set.

Algorithm SM(m).
Initially Vi = /0.
1) The commander signs and sends his value to every lieutenant.
2) For each i:
  A) If Lieutenant i receives a message of the form v:0 from the commander and he has not yet received any order, then
    i)  he lets Vi equal {v};
    ii) he sends the message v:0:i to every other lieutenant.
  B) If Lieutenant i receives a message of the form v:0:j(1):...j(k) and v is not in the set Vi, then
    i)  he adds v to Vi;
    ii) if k<m, then he sends the message v:0:j(1):...:j(k):i to every lieutenant other than j(1),...,j(k).
3) For each i: When Lieutenant i will receive no more messages, he obeys the order choice(Vi).

THEOREM 2. For any m, Algorithm SM(m) solves the Byzantine Generals Problem if there are at most m traitors.

Definition 1.
a) A set of nodes {i1,...,ip} is said to be a regular set of neighbors of a node i if
  i)  each i(j) is a neighbor if i, and
  ii) for any general k different from i, there exist paths r(j,k) from i(j) to k notpassing through i such taht any two different paths r(j,k) have no node in common other than k.
b) The graph G is asid to be p-regular if every node has a regular set of neighbors consisting of p distinct nodes.

OM(m, p)
0) Choose a regular set N of neighbors of the commander consisting of p lieutenants.
1) The commander sends his value to every lieutenant in N.
2) For each i in N, let v(i) be the value Lieutenant i receives from the commander, or else RETREAT if he receives no value. Lieutenant i sends v(i) to every other lieutenant k as follows:
  A) If m = 1, then by sending the value along the path r(i, k) whose existence is guaranteed by part (a)(ii) of Definition 1.
  B) If m > 1, then by acting as the commander in the algorithm OM(m - 1, p - 1), with the graph of generals obtained by removing the original commander from G.
3) For each k, and each i in N with i != k, let v(i) be the value Lieutenant k received from Lieutenant i in step (2), or RETREAT if he received no value. Lieutenant k uses the value majority(v(i1),...,v(ip), where N = {i(1),...,i(p)}.

LEMMA 2. For any m > 0 and any p >= 2k + m, OM(m,p) satisfies IC2 if at most k traitors.

THEOREM 3. For any m >0 and any p >= 3m, OM(m,p) solves the Byzantine Generals Problem if there are at most m traitors.

THEOREM 4. For any m and d, if ther are at most m traitors and the subgraph of loayl generals has diameter d, then SM(m+d-1) solves the Problem.

COROLLARY. If the graph of loyal generals is connected, then SM(n-2) solves the Problem for n generals.

1. All nonfaulty processors must use the same input value (so they produce the same output).
2. If the input unit is nonfaulty, then all nonfaulty processes use the value it provides as input (so they produce the correct output).