## Overview ## Motivation ## Problem Definition ## Impossibility? ## Solutions (Oral and signed messages) ## Practical Use? ## Conclusions
## Motivation ## 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.
**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. ## 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)
## 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. ## 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.
## 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ş:** |