The Byzantine Generals Problem

Byzantine Generals Problem and its Applications

Byzantine General Problem

	The Classic Problem Each division of Byzantine army are directed its own general Generals, some of which are traitors, communicate each other by messengers Requirements: All loyal generals decide upon the same plan of action A small number of traitors cannot cause the loyal generals to adopt a bad plan
	The problem can be restated as: All loyal generals receive the same information upon which they will somehow get to the same decision The information sent by a loyal general should be used by all the other loyal generals
	The above problem can be reduced into a series of one commanding general and multiple lieutenants problem - Byzantine Generals Problem : All loyal lieutenants obey the same order If the commanding general is loyal, then every loyal lieutenant obeys the order she sends

Reliability by Majority Voting

	One way to achieve reliability is to have multiple replica of system (or component) and take the majority voting among them
	In order for the majority voting to yield a reliable system, the following two conditions should be satisfied: All non-faulty components must use the same input value If the input unit is non-faulty, then all non-faulty components use the value it provides as input

Impossibility Results

No solution exists if less than or equal to 2/3 generals are loyal

A Solution with Oral Messages - No Signature

Oral Message Requirements and their Implications

	A1 - Every message that is sent is delivered correctly The failure of communication medium connecting two components is indistinguishable from component failure Line failure just adds one more traitor component
	A2 - The receiver of a message knows who sent it No switched network is allowed The later requirement -- A4 nullifies this constraint
	A3 - The absence of a message can be detected Timeout mechanism is needed

Solution

	If less than 1/3 generals are traitors, this problem can be solved
	Algorithm - recursive Lieutenants recursively forward orders to all the other lieutenants Commander's order = majority (v(c), v(1), v(2), ..., v(n)) v(i) = majority (v(i), v(i)(2), v(i)(3), ..., v(i)(n)), 1<= i <= n v(i)(j) = majority (v(i)(j), v(i)(j)(3), v(i)(j)(4), ...) ...

A Solution with Signed Messages

Additional Requirements and their Implications

	A4: A loyal general's signature cannot be forged Anyone can verify the authenticity of a general's signature
	Implication Digital signature is required

Solution

	If at least two generals are loyal, this problem can be solved
	Algorithm - recursive Lieutenants recursively augment orders with their signature and forward them to all the other lieutenants Each lieutenant maintains a set of orders she has received, i.e., the possible sets are: { attack }, { wait }, or { attack, wait } Lieutenant takes action according to the value of the set { attack, wait } means the commander is a traitor

Missing Communication Paths

	Network topology or policy could keep a general sending/receiving messages to/from another general
	This constraint makes Byzantine problem more general

Oral Message

	If the communication graph is 3m-regular and less than or equal to m generals are traitors, this problem can be solved k regular set of neighbors of a node p the set of all neighbors of p, whose size is k for any node not in the set, there exists a disjoint path, not passing through the node p, from a node in the set k regular graph - every node has k regular set of neighbors
	Algorithm - extension of oral message Lieutenants recursively forward orders to all its k regular neighbors Commander's order = majority (v(c), v(1), v(2), ..., v(n)) v(i) = majority (v(i), v(i)(2), v(i)(3), ..., v(i)(n)), 1<= i <= n v(i)(j) = majority (v(i)(j), v(i)(j)(3), v(i)(j)(4), ...) ...

Signed Message

If the subgraph of loyal generals is connected, this problem can be solved