The Problem ofDistributed Consensus

May17, 2021

In preparation for a conference entitled “Distributed Consensus with Cellular Automata &Related Systems” that we’re organizing with NKN (=“New Kind of Network”) I decided to explore the problem of distributedconsensus using methods from A New Kind of Science (yes, NKN “rhymes”with NKS) as well as from the Wolfram Physics Project.

A Simple Example

‍

&#10005

BlockRandom[SeedRandom[77];

Module[{pts =

    RandomPointConfiguration[HardcorePointProcess[0.09, 2, 2],

      Rectangle[{0, 0}, {40, 40}]]["Points"], clrs},

 clrs = Table[

    RandomChoice[{.65, .35} -> {Hue[0.15, 0.72, 1], Hue[

      0.98, 1,  0.8200000000000001]}], Length[pts]];

  Graphics[{EdgeForm[Gray],

    Table[Style[Disk[pts[[n]]], clrs[[n]]], {n,

      Range[Length[pts]]}]}]]]

Considera collection of “nodes”, each one of two possible colors. We want to determinethe majority or “consensus” color of the nodes, i.e. which color is the morecommon among the nodes.

Oneobvious method to find this “majority” color is just sequentially to visit eachnode, and tally up all the colors. But it’s potentially much more efficient ifwe can use a distributed algorithm, where we’re running computations inparallel across the various nodes.

Onepossible algorithm works as follows. First connect each node to some number ofneighbors. For now, we’ll just pick the neighbors according to the spatiallayout of the nodes:

&#10005

ConsensusState[points_, colors_, nn_ : 5] :=

NearestNeighborGraph[points, nn,  DirectedEdges -> True,

  DistanceFunction -> EuclideanDistance,

 VertexStyle  -> MapThread[Rule, {points, colors}],

 VertexSize  -> 0.75, EdgeStyle -> \!\(\*

TagBox[

StyleBox["Gray",

ShowSpecialCharacters->False,

ShowStringCharacters->True,

NumberMarks->True],

FullForm]\)];

BlockRandom[SeedRandom[77];

Module[{pts =

   RandomPointConfiguration[HardcorePointProcess[0.09,  2, 2],

      Rectangle[{0, 0}, {40, 40}]]["Points"], clrs},

 clrs =

  Table[

    RandomChoice[{.65, .35} -> {Hue[0.15, 0.72, 1], Hue[

      0.98, 1,  0.8200000000000001]}], Length[pts]];

 ConsensusState[pts,  clrs]]]

Thealgorithm works in a sequence of steps, at each step updating the color of eachnode to be whatever the “majority color” of its neighbors is. In the caseshown, this procedure converges after a few steps to make all nodes have the “majoritycolor” (which here is yellow)—or in effect “agree” on what the majority coloris:

&#10005

ConsensusState[points_, colors_, nn_:5] :=  NearestNeighborGraph[points,nn,DirectedEdges->True,  DistanceFunction->EuclideanDistance,VertexStyle -> MapThread[Rule,  {points, colors}], VertexSize -> 0.75, EdgeStyle -> Gray]

NodeDependencies[points_, nn_:5]:= Table[n->  Flatten[Map[Position[points,  #]&,VertexOutComponent[NearestNeighborGraph[points,nn, DirectedEdges  -> True, DistanceFunction->EuclideanDistance], points[[n]], {1}]]], {n,  Range[Length[points]]}]

SynchronousStepNewColors[dependencies_, colors_]:=

Flatten[Map[With[{neighbors = Sort[Counts[Part[colors,  Last[#]]], Greater]},

If[DuplicateFreeQ[Values[neighbors]],

First[Keys[neighbors]],

colors[[First[#]]]]]&, dependencies]]

GraphicsGrid[Partition[BlockRandom[SeedRandom[77];Module[{pts  = RandomPointConfiguration[HardcorePointProcess[0.09, 2, 2], Rectangle[{0,  0}, {40, 40}]]["Points"],clrslist, highlights},

clrslist=NestList[SynchronousStepNewColors[NodeDependencies[pts],  #]&, Table[RandomChoice[{.65,.35}->{Yellow,Red}], Length[pts]], 7];

MapIndexed[With[{colors = #}, Graph[ConsensusState[pts,  colors],ImageSize->150]] &,clrslist]

]],4],ImageSize-> 600]

Thisis a simple example of a distributed consensus algorithm in action. Thechallenge we’ll discuss here is to find the most efficient and robust suchalgorithms.

The Background

Inany decentralized system with computers, people, databases, measuring devicesor anything else one can end up with different values or results at different“nodes”. But for all sorts of reasons one often wants to agree on a single“consensus” value, that one can for example use to “make a decision and go onto the next step”.

Blockchainsare one example of systems that need this kind of consensus to “finish eachblock”. Traditional blockchains achieve consensus through what amounts to acentralized mechanism (even though there are multiple “decentralized” copies ofthe blockchain that is produced).

Butthere are now starting to be distributed analogs of blockchains that needdistributed consensus algorithms. And the main inspiration for the algorithmsbeing developed are cellular automata (and to a lesser extentspin systems in statistical mechanics).

Oneissue is to make the algorithm as efficient as possible. Another is to make itas robust as possible, for example with respect to random noise—or maliciouserrors—introduced at or between nodes.

Theamount of random noise can be thought of as something like a temperature. Andat least in certain cases there can be a “phase transition” so that below acertain “temperature” there can be zero effect on the consensus output—implyingrobustness to a certain level of noise.

Someof what happens can be studied using methods from standard equilibriumstatistical physics. But in most cases one has to take account of the timedependence or evolution of the system, leading to something like aprobabilistic cellular automaton (closely related to directed percolation,dynamic spin systems, etc.).

AsI’ll discuss below, in the early days of computing,there was great interest in synthesizing reliable systems out of unreliablecomponents. And by the 1960s there was study first of neural nets and then ofcellular automata with probabilistic elements. And some surprising results wereobtained that showed that cellular automata could be set up that would berobust with respect to a certain nonzero level of noise.

Onefeature of cellular automata is that their elements are all assumed to bearranged in a definite array, and to be updated in parallel “at the same time”in a sequence of steps. For many practical applications, however, one insteadwants elements that are connected in some kind of graph (that may even bedynamic), and that are in general updated asynchronously, in no particularorder.

Thesimple example we gave above is a graph cellular automaton: the connectionsbetween elements are defined by a graph, but the updates are all donesynchronously at each step. In the past, it’s been difficult to analyze themore general setup where there is no rigid notion of either space or time. Butthis is exactly the setup in our new PhysicsProject, and so there’s now the potential to use its formalism andresults (as well as intuition imported from physics) to make further progress.

‍