There are many algorithms that can be considered in this case. We look at the voter model.

Voter Model

Voter Model

The voter model happens in rounds (or time-steps, denoted by $t$). At each round $t$, each agent $v$ selects one of its neighbours $u$ uniformly at random. Then $v$ adopts $u$‘s colours for the next round.

Link to original

We assume they all change at the same time at the end of round $t$.

Notation

• Time variable $t\in T$ represents rounds, $T$ is set of non-negative integers.
• We have an undirected connected graph $G=(V,E)$. Edge $(v,u)$ indicates $v$ sees $u$ and $u$ sees $v$. Number of neighbours of $v$ is denoted by $\text{deg}(v)$.
• We have a set of colours or opinions $X$.
• For each time $t\in T$, current state of process is described by a function $S_t:V\to X$.
• We are interested in consensus states: When, for a given $t$, we have $S_t(v)=b$ for all $v\in V$, we say $S_t=\text{blue}$. Same for red, we have $S_t=\text{red}$.

We seek to answer the following questions:

• Is consensus stable? i.e. once reached, will it be maintained indefinitely?
• Can the process get stuck and never reach consensus?
• Imagine you have the power to flip colour of agent before any decisions in a given round, which is the best choice / which agent is most influential?
• Given an initial configuration $S_0$, what is the probability that the game ends in blue or red consensus?

What counts for an opinion's advantage?

The sum of degrees of nodes with a given colour.

Theorem Let $G=(V,E)$ be a graph that does not allow deadlocks in a voter model process (i.e. a consensus is reached with probability $1$).

Given an initial configuration $S_0=s$, the probability of blue winning is given by: $Pr(S_{\text{end}}=\text{blue}\mid S_0=s)={\sum }_{v\in V,s(v)=b}\frac{\text{deg}(v)}{2|E|}$ and the same for red.

Application Given our example graph from before:

$$\begin{array}{rlrl}Pr(S_{\text{end}}=\text{blue}|S_0=s)& =\frac{4+3+2}{14}& & \approx 64\%\\ Pr(S_{\text{end}}=\text{red}|S_0=s)& =\frac{2+3}{14}& & \approx 36\%\end{array}$$

Additional follow-up questions

• Can we analyse the expected time it will take to converge to consensus?
• What if the graph is directed with weighted edges? (weight of the edge $(v,u)$ is taken as the probability $v$ copied colours of $u$)
• What if there is some bias towards a colour?

Consensus in Blockchain

Details of Bitcoin Blockchain not examined.