Quantum Byzantine Agreement - Introduction

Introduction

The Byzantine Agreement protocol is a protocol in distributed computing. It takes its name from a problem formulated by Lamport, Shostak and Pease in 1982, which itself is a reference to a historical problem. The Byzantine army was divided into divisions with each division being led by a General with the following properties:

  • Each General is either loyal or a traitor to the Byzantine state.
  • All Generals communicate by sending and receiving messages.
  • There are only two commands: attack and retreat.
  • All loyal Generals should agree on the same plan of action: attack or retreat.
  • A small linear fraction of bad Generals should not cause the protocol to fail (less than a fraction).

(See for the proof of the impossibility result). The problem usually is equivalently restated in the form of a commanding General and loyal Lieutenants with the General being either loyal or a traitor and the same for the Lieutenants with the following properties.

  • All loyal Lieutenants carry out the same order.
  • If the commanding General is loyal, all loyal Lieutenants obey the order that he sends.
  • A strictly less than fraction including the commanding General are traitors.

Read more about this topic:  Quantum Byzantine Agreement

Famous quotes containing the word introduction:

    “For the introduction of a new kind of music must be shunned as imperiling the whole state; since styles of music are never disturbed without affecting the most important political institutions.”
    —Plato (c. 427–347 B.C.)

    “We used chamber-pots a good deal.... My mother ... loved to repeat: “When did the queen reign over China?” This whimsical and harmless scatological pun was my first introduction to the wonderful world of verbal transformations, and also a first perception that a joke need not be funny to give pleasure.”
    —Angela Carter (1940–1992)

    “For better or worse, stepparenting is self-conscious parenting. You’re damned if you do, and damned if you don’t.”
    —Anonymous Parent. Making It as a Stepparent, by Claire Berman, introduction (1980, repr. 1986)