The Byzantine Generals Problem Boon Thau Loo

Yüklə 468 b.
ölçüsü468 b.

The Byzantine Generals Problem

  • Boon Thau Loo

  • CS294-4


  • Motivation

  • Problem Definition

  • Impossibility?

  • Solutions (Oral and signed messages)

  • Practical Use?

  • Conclusions


  • Coping with failures in computer systems

  • Failed component sends conflicting information to different parts of system.

  • Agreement in the presence of faults.

  • P2P Networks?

    • Good nodes have to “agree to do the same thing”.
    • Faulty nodes generate corrupted and misleading messages.
    • Non-malicious: Software bugs, hardware failures, power failures
    • Malicious reasons: Machine compromised.

Problem Definition

  • Generals = Computer Components

  • The abstract problem…

    • Each division of Byzantine army is directed by its own general.
    • There are n Generals, some of which are traitors.
    • All armies are camped outside enemy castle, observing enemy.
    • Communicate with each other by messengers.
    • Requirements:
      • G1: All loyal generals decide upon the same plan of action
      • G2: A small number of traitors cannot cause the loyal generals to adopt a bad plan
    • Note: We do not have to identify the traitors.

Naïve solution

  • ith general sends v(i) to all other generals

  • To deal with two requirements:

    • All generals combine their information v(1), v(2), .., v(n) in the same way
    • Majority (v(1), v(2), …, v(n)), ignore minority traitors
  • Naïve solution does not work:

    • Traitors may send different values to different generals.
    • Loyal generals might get conflicting values from traitors
  • Requirement: Any two loyal generals must use the same value of v(i) to decide on same plan of action.

Reduction of General Problem

  • Insight: We can restrict ourselves to the problem of one general sending its order to others.

  • Byzantine Generals Problem (BGP):

    • A commanding general (commander) must send an order to his n-1 lieutenants.
  • Interactive Consistency Conditions:

    • IC1: All loyal lieutenants obey the same order.
    • IC2: If the commanding general is loyal, then every loyal lieutenant obeys the order he sends.
  • Note: If General is loyal, IC2 => IC1.

  • Original problem: each general sends his value v(i) by using the above solution, with other generals acting as lieutenants.

3-General Impossibly Example

  • 3 generals, 1 traitor among them.

  • Two messages: Attack or Retreat

  • Shaded – Traitor

  • L1 sees (A,R). Who is the traitor? C or L2?

  • Fig 1: L1 has to attack to satisfy IC2.

  • Fig 2: L1 attacks, L2 retreats. IC1 violated.

General Impossibility

  • In general, no solutions with fewer than 3m+1 generals can cope with m traitors.

  • Proof by contradiction.

    • Assume there is a solution for 3m Albanians with m traitors.
    • Reduce to 3-General problem.

Solution I – Oral Messages

  • If there are 3m+1 generals, solution allows up to m traitors.

  • Oral messages – the sending of content is entirely under the control of sender.

  • Assumptions on oral messages:

    • A1 – Each 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.
  • Assures:

    • Traitors cannot interfere with communication as third party.
    • Traitors cannot send fake messages
    • Traitors cannot interfere by being silent.
  • Default order to “retreat” for silent traitor.

Oral Messages (Cont)

  • Algorithm OM(0)

    • Commander send his value to every lieutenant.
    • Each lieutenant (L) use the value received from commander, or RETREAT if no value is received.
  • Algorithm OM(m), m>0

    • Commander sends his value to every Lieutenant (vi)
    • Each Lieutenant acts as commander for OM(m-1) and sends vi to the other n-2 lieutenants (or RETREAT)
    • For each i, and each j<>i, let vj be the value lieutenant i receives from lieutenant j in step (2) using OM(m-1). Lieutenant i uses the value majority (v1, …, vn-1).
    • Why j<>i? “Trust myself more than what others said I said.”

Restate Algorithm

  • OM(M):

    • Commander sends out command.
    • Each lieutenant acts as commander in OM(m-1). Sends out command to other lieutenants.
    • Use majority to compute value based on commands received by other lieutenants in OM(m-1)
  • Revisit Interactive Consistency goals:

    • IC1: All loyal lieutenants obey the same command.
    • IC2: If the commanding general is loyal, then every loyal lieutenant obeys the command he sends.

Example (n=4, m=1)

Example (n=4, m=1)

Expensive Communication

  • OM(m) invokes n-1 OM(m-1)

  • OM(m-1) invokes n-2 OM(m-2)

  • OM(m-2) invokes n-3 OM(m-3)

  • OM(m-k) will be called (n-1)…(n-k) times

  • O(nm) – Expensive!

Solution II: Signed messages

  • Previous algorithm allows a traitor to lie about the commander’s orders (command). We prevent that with signatures to simplify the problem.

  • By simplifying the problem, we can cope with any number of traitors as long as their maximum number (m) is known.

  • Additional Assumption A4:

    • A loyal general’s signature cannot be forged.
    • Anyone can verify authenticity of general’s signature.
  • Use a function choice(…) to obtain a single order

    • choice(V) = v if v if the only elem. in V
    • choice(V) = RETREAT if V is empty

Signed Messages (Cont)

  • Each lieutenant maintains a set V of properly signed orders received so far.

  • The commander sends a signed order to lieutenants

  • A lieutenant receives an order from someone (either from commander or other lieutenants),

    • Verifies authenticity and puts it in V.
    • If there are less than m distinct signatures on the order
      • Augments orders with signature
      • Relays messages to lieutenants who have not seen the order.
  • When lieutenant receives no new messages, and use choice(V) as the desired action.

  • If you want to protect against more traitors, increase m

Algorithm’s Intuition

  • All loyal lieutenants compute the same set of V eventually, thus choice(V) is the same (IC1)

  • If the commander is loyal, the algorithm works because all loyal lieutenants will have the properly signed orders by round 1 (IC2)

  • What if the commander is not loyal?

Missing Communication Paths

  • What if not all generals can reach all other generals directly?

  • P-regular graph – Each node has p regular neighbors.

  • 3m-regular graph has minimum of 3m+1 nodes

  • Paper shows algorithm for variant of oral message algorithm – OM(m,p). Essentially same algorithm except that each lieutenant forwards orders to neighbors.

  • Proofs that OM(m,3m) solves BGP for at most m traitors.

  • I.e. if the communication graph is 3m-regular, and there are at most m traitors, the problem can still be solved.

Practical use of BGP?

  • What does it take for majority voting to work?

    • Input synchronization (order from commander) of non-faulty (loyal) processors to produce same outputs (decisions). (IC1)
    • If input unit (commander) is non-faulty (loyal),all non-faulty processes use the value it provides as input (IC2)
  • A1 – Every message sent by non-faulty process is delivered correctly.

    • Failure of communication line cannot be distinguished from failure of nodes.
    • OK because we still are tolerating m failures.
  • A2 – A processor can determine origin of message

    • A4 makes this obsolete.

Practical Use of BGP (Cont..)

  • A3 – Absence of a message can be detected.

    • Timeouts or synchronized clocks
  • A4 – Unforgeable signatures. Anyone can verify authenticity of signature

    • Message signed by i = (M, Si(M))
    • If i is not faulty, no one can generate Si(M). Faulty processor used for generating signatures?
    • Given M and X, anyone can verify if X=Si(M)

Concluding thoughts

  • BGP solutions are expensive (communication overheads and signatures)

  • Use of redundancy and voting to achieve reliability. What if >1/3 nodes (processors) are faulty?

  • 3m+1 replicas for m failures. Is that expensive?

  • Tradeoffs between reliability and performance (E.g. Oceanstore’s primary and secondary replicas)

  • How would you determine m in a practical system?

Dostları ilə paylaş:

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur © 2019
rəhbərliyinə müraciət

    Ana səhifə