- Node $i$ keeps a set $W_i \in \mathcal{D}$, firstly containing its own value $v_i$
- At each round, each node broadcasts $W_i$ to everyone; add received elements to $W_i$
- After k round
- If $|W_i|=1$ then decide on the unique value
- Else decide on a default value $v_0\in\mathcal{D}$ (or, decide on the smallest value)
- Complexity
-
Number of rounds
- depends on the number of crashed processes $f$
- needs round $k=f+1$
-
total number of msgs:$O((f+1)n^2)$, $n$ is the number of processes
-
total number of bits:$O((f+1)n^3b)$, as each msg contains at most $nb$ bits
-
Exist improved algorithms to reduce complexity (see Lynch)
-