Abridge WIKI contents for an arbitrary sequence that I studied.

Byzantine Fault Tolerance is able to abbreviate to BFT.

Prelim.

It doesn’t matter if the below is perceived or not.

BFT is a fault-tolerant distributed system, which is able to keep tolerable from vaudeville failures in which there are two types; a crash failure or a Byzantine failure associated with Byzantine Generals’ Problem. The level of toleration and the cognizance of the failures are both indecisive, which means they should be determined by use cases.
Byzantine Generals’ Problem, which is recognized as the failure in BFT, is a generalized version of Two Generals’ Problem.
Byzantine Generals’ Problem is unsolvable that is no definite, specific solution or algorithm. There is only a tolerant method such as BFT.

Byzantine Generals’ Problem

This article is able to guide to more detailed, precise elucidation. The below is recapitulated version of details.

Assumption
- There is 5 generals to conquer a defensive city; for example, A, B, C, D, and E.
- There is a possibility a few of them is a traitor.
- They have to communicate a certain message that is described an offense time to attack simultaneously, they would be defeated when they attack separately.
Scenario
- General A start to send the message “Attack 9:00 am tomorrow.” to B, B would relay to C, C to D, D to E, and E to A. The method of communication is able to be diverse and various.
- when general C is a traitor, C could fabricate the message to rewrite the time. D and E would relay the wrong message until A. The A could know there is more than one traitor.
Problem
- Who is the traitor(s)?
- How to send a new message to abort the attack in this situation? The traitor could concoct this message again.
- How to reach a consensus?

Problems could be various depending a scenario.

Paxos

The below is abridged this article, Paxos Made Simple.

It is an algorithm to implement a fault-tolerant distributed system.
The core algorithm, synod, is a consensus algorithm.
It cannot handle the corrupted message, which is considered in BFT.

Consensus algorithm

Processes propose values. –> one single value is chosen. –> processes learn the chosen value.
3 classes of agents; proposers, acceptors, and learners
non-Byzantine model
- Agents
  - operate at arbitrary speed
  - fail by stopping/restart
  - How if all agents fail after a value is chosen?
    - save the chosen value
    - redo a process
    - ignore the chosen value
- Messages
  - be delivered as an arbitrary length, duplicated, and lost
  - be not corrupted
Choosing value, C(v)
- 1 acceptor
  - A proposer proposes to an acceptor –> C(v) –> processes learn
  - How if a acceptor fails during ‘C(v)’ ?
- i acceptors (i > 1)
  - A proposer proposes to i of acceptors –> C(v) –> processes learn
  - Choose a only single value that is accepted by the majority of acceptors, which is accepted by a generalization of a majority, among proposed values by proposers.
- A proposal (P) consists of a proposal number (n) and a value (v), P (n, v)
  - When an acceptor A accepted P(a, v), the A can accept P(b, v) with (b > a).
- Proposer for issuing proposals
  1. A proposer chooses a new proposal number n and asks a prepare request to acceptors: Prepare(n)
  2. If responses from a majority of the acceptors are received, issue a proposal P(n, v) in which v is the value of the highest-numbered proposal among the responses or any value if no proposal.
  3. A proposer requests to accept the proposal P(n, v): Accept(P(n, v))
- Acceptor to respond to requests of a proposer
  - An acceptor can always respond to a Prepare(n) request.
  - If an acceptor has responded to a Prepare(n) request before, the acceptor can always respond to a Accept(P(n, v)) request.
  - An acceptor can respond to a Accept(P(n, v)), even though the acceptor accepted a proposal P(n’, v) with n < n’, if it has not responded a Prepare(n) request before.
  - An acceptor must remember the highest-numbered accepted proposal and the number of the highest-numbered Prepare(n) request to be prepared for failures.
- Algorithms
  1. A proposer’s request to a majority of the acceptors: Prepare(n)
  2. An acceptor’s response to Prepare(n):
    - if n > n’ (previous Prepare(n’)),
    - with a promise not to accept any proposals P(n”, v) with n > n”,
    - with the highest-numbered accepted proposal, if any.
  3. The proposer’s request: Accept(P(n, v))
    - v is the value of the highest-numbered proposal among responses,
    - or v is any value if no proposals among responses.
  4. An acceptor’s response to Accept(P(n, v)), and accepts:
    - if not responded to a previous Prepare(n’) with n < n’.
Learning a chosen value, L(v)
- A leaner must know an accepted proposal by a majority of acceptors.
- Simple way
  - Each learner requests to all acceptors: n-request
  - Each acceptor responds to all learners: n-response
- non-Byzantine failures
  - An acceptor –> a learner –> another learner –> …
  - How if a learner fails?
  - What if Byzantine failures?
- General way
  - A group of learners

BFT

Early solution

Encryption
- Prevent to fabricate the message.
- using public-key cryptography
  - Encrypt by private key.
  - Decrypt by public key. = cannot encrypt again.
- using Cyclic Redundancy Check (CRC)
  - Supplement a unique check-value in the message.
  - If the message is changed, the check-value would indicate the fault.
Atomic broadcast
- If a hardware transmits the message at once, a different message could not be sent to each participants.
- Further details in here.

Practical BFT (PBFT)

The below is condensed the article, Practical ByzantineFault Tolerance and Proactive Recovery. Compare with PAXOS algorithm upper.

PBFT is a replication algorithm.
BFS
- BFS is BFT distributed file system, which is the real system to be made of the BFT library.

Tag: Byzantine General’s Problem

Byzantine Fault Tolerance (BFT)