There is a 1:1 correspondence between Interactive Consensus conditions and Error-Correcting Codes.

You have 27 coins, 1 of which is a different weight. Using a balance scale with 2 pans, how can you determine which coin is different in only 4 weighings?

Generalize this to N coins.

Asynchronous consensus is impossible (Fischer, Lynch, and Paterson 1983)

3 circumventions:

- weaken: approximate agreement, set agreement, randomized solutions
- strengthen synchrony: partially synchronous, failure detectors
**condition-based approach:**place restrictions on the input to processes

Assume a likely case:

- Fast termination in likely case
- Still safe in unlikely case

Number of symbols that differ:

\begin{align*}
[\ {\color{red}{0\ 1\ 0}}\ 0\ 1\ ] \\
[\ {\color{red}{1\ 0\ 1}}\ 0\ 1\ ] \\
\end{align*}

The above two words have a Hamming distance of 3.

Place every possible word in a binary hypercube:

\(\ell_1\) distance is the Hamming distance

Naively send message 3×

\begin{align*}
00000\quad 00111\quad 01110\quad 01001 \\
11100\quad 11011\quad 10010\quad 10101
\end{align*}

Hamming distance \( \geq 2 \).

8 code words \( \implies \) 3 bits of information sent

A code \(C\) is \( (f_v, f_c) \)-error/erasure decoding iff its minimal hamming distance is \( > 2f_v + f_c \)

The original, Hamming(7,4), had a minimal hamming distance of 3:

{conditions that allow IC to be solved despite \(f_c\) crashes and \(f_e\) value domain faults}

\(\wr\)

{ECCs capable of recovering from \(f_c\) erasures and \(f_e\) corruptions}

[ \( C \) \( \implies \) consensus despite \(f_c\) crashes ]

\( \Updownarrow \)

\(C\)’s Hamming distance is \(f_c+1\)

[ \( C \) \( \implies \) consensus despite \(f_b\) Byzantine faults ]

\( \Updownarrow \)

\(C\)’s Hamming distance is \(2f_b+1\)

Requirements that make an ECC valid ∼ conditions needed to solve IC

FLP \( \implies \) no perfect codes can tolerate erasure failures

agreement problem & conditions

\( \downarrow \)

algorithm to solve problem

Form a graph of input vectors, \( G_{f_c,f_v}^C\):

- Vertices are included iff they meet conditions
- Vertices are neighbors iff their Hamming distance \(\leq 2f_v + f_c\)

**Definition 3.1 & Theorem 3.4:** An agreement problem \( (C, f_c,f_v)\) can be solved iff \( \exists h : \) h is constant on every connected component of \( G_{f_c,f_v}^C \)

*See 2.1 and 3. \(d(a, b)\) is the Hamming distance between \( a \) and \( b \). \( C \) are the conditions: The set of assumed possible input vectors.*

Fischer, Michael J., Nancy A. Lynch, and Michael S. Paterson. 1983. “Impossibility of Distributed Consensus with One Faulty Process.” *Proceedings of the 2nd Acm Sigact-Sigmod Symposium on Principles of Database Systems - Pods ’83*. https://doi.org/10.1145/588058.588060.