Consensus

date
Jun 20, 2021
slug
comp90020-cna-consensus
status
Published
tags
Programming
COMP90020
summary
type
Page
Year
2021
Lecture NotesFundamentalsMotivationModel DescriptionConsensus conditionsFailure ModelsComplexity measureSystem modelAlgorithmsComparisons of 3 Synchronous AlgorithmsAsynchronous Algorithms
 
 

Lecture Notes

Fundamentals

Motivation

  • Database transactions: commit or abort
  • Leader election
  • Replicated state machines: to simulate a server consistently
  • Membership / failure detection
  • Control systems with distributed components: agree on values of system states ...
  • Common to all above: attempt to coordinate with each other and agreement on the value of something

Model Description

  • , undirected graph
  • processes (called "nodes" here)
  • 每个node都有初始值 E.g.
  • Neighbouring nodes exchange msgs (over multiple rounds)
  • Each node set value of a decision variable

Consensus conditions

  • Termination: eventually each correct node sets its decision variable
  • Agreement: for all correct
  • Integrity/Validity: if for all correct , then for all correct
  • When there is no failures, conditions mentioned above should apply to all node (rather than just correct node).
    • consensus conditions (without failures) are easy to implement, 然而challenge是communication或者processes发生错误. 我们无法控制发生了crashed或者byzantine错误的node. 因此我们对consensus condition作出相应的修改 ( all nodes → all correct nodes)
  • 同时, integrity也有不同的分级
    • I-1: if for all correct node, then for all correct node (Byzantine agreement/Byzantine consensus)
    • I-2: 存在一个特殊的正确的node,其value是 , 那么所有正确的node的 (Byzantine broadcast/Byzantine general problem)
    • I-3: , 如果所有i的初始值都是0,那么所有correct node的决策值也会是0; 同样地, 如果所有i的初始值都是1, 那么所有correct node的决策值也是1
    • In general, we could require to be an arbitrary function of .

Failure Models

  • Link failure: msg无法到达目的地
  • Process failure:
    • Stopping failure: node crashes after some rounds
    • Byzantine failure: node can behave in arbitrary (adversarial) way

Complexity measure

  • Time: number rounds until all correct nodes decide
  • Communication: number of msgs, or number of bits

System model

  • Synchronous 可解决
  • Asynchronous 不可解决

Algorithms

Comparisons of 3 Synchronous Algorithms

Synchronous Algorithms
Name
Category
Number of rounds
Number of Messages
Number of bits
Floodset algorithm
Stopping Failures
Round , where is the number of crashed processes
, where is the number of processes
, as each message contains at most bits
Exponential Information Gathering (EIG)
Stopping Failures
(number of nodes in a EIG tree)
EIG for Byzantine failure (to agree on 1 bit)
Byzantine Failures
, requirement:

Asynchronous Algorithms

  • Paxos
    • provide safety: consensus is not violated
    • no guarantee on liveness (no guarantee that consensus can be reached within bounded time)
      • A simplified view of Paxos
       

© wongchihaul 2021 - 2024