Coordination

Consensus

In the Byzantine setting the focus is often on detectable agreement.

constant expected number of rounds compared for the randomized (adaptive adversary)
Assumptions:
- adaptive full information adversary
- failure models: Byzantine / crash faults
States: $\sum_{a = 1}^{n^{3}} ∣ a, \dots, a ⟩$
Byzantine needs verifiable (can agree that secret can be recovered) secret sharing for random numbers

Assumptions:
- adaptive full information adversary
- failure models: Byzantine / crash faults
requires fewer Bell pairs by using some kind of gossip protocol

NB The arity of entanglement is still $O (n)$

NB Apparently, for DBA no one needs to maintain quantum state, hence the size and decoherence time of quantum memory are irrelevant.

Correctness all honest players commonly accept or reject the protocol. If all accept, then the protocol achieves broadcast
Completeness if no player is corrupted, all accept
Fairness if any honest player rejects, then the adversary gets no information about the sender's input

Detectable Precomputation:

Correctness: all honest players commonly accept or reject the protocol. If all accept, then strong broadcast will be achievable
Completeness if no player is corrupted, all accept
Independence any honest player's input value need not be known

for weak agreement (or detectable broadcast), where a single faulty player may force everyone to abort
States: $∣ A ⟩ = ∣0, 1, 2 ⟩ + ∣1, 2, 0 ⟩ + ∣2, 0, 1 ⟩ - ∣0, 2, 1 ⟩ - ∣1, 0, 2 ⟩ - ∣2, 1, 0 ⟩$ (Aharonov tri-partite qutrit states)
N = 3, f = 1

Explicitly says that the key is to construct secret and correlated lists

Based on the list $l_{A}$ , $l_{B}$ , and $l_{C}$ that are correlated and are produced from 4-qubit entangled states
States: $∣ Ψ^{(4)} ⟩_{abcd} = 2∣0011 ⟩ - ∣0101 ⟩ - ∣0110 ⟩ - ∣1001 ⟩ - ∣1010 ⟩ + 2∣1100 ⟩$
N = 3, f = 1

a lot of pairwise interaction among the lieutenants and the general
States: $∣000 ⟩ \pm ∣111 ⟩$ , $∣010 ⟩ \pm ∣101 ⟩$ , $∣011 ⟩ \pm ∣100 ⟩$ (GHZ-like)
N > f + 1

trusted quantum source
States: $\sum_{j} ∣ j ⟩ \otimes ∣ j + i_{1} mod d ⟩ \otimes ...∣ j + i_{n} mod d ⟩$ (multi-partite qudits)
N > f + 1
gives counterexamples for two other works (not listed here) to be incorrect

These are to a large degree also based on correlated lists):

Beating the fault-tolerance bound for byzantine agreement
- The algorithm is from the same paper
- All the quantum part is done in a lab using "four-intensity decoy-state BB84 key generation process"
Noise-Aware Detectable Byzantine Agreement for Consensus-based Distributed Quantum Computing
- focus is on the epr algorithm (TODO: double check)
- filter batches of EPR-pairs testing fidelity and dropping those with the fidelity below the threshold
- noise-mitigation techniques

Quantum Distributed Consensus: not quite a "consensus" as the outcome is _always random