Message Boards

GROUPS:

Ryan Lau

[WSS21] The 3-colored distributed consensus problem

Ryan Lau

Posted 11 months ago

1354 Views

1 Reply

3 Total Likes

Follow this post

3-colored cellular automaton with the Maj7 rule

The 3-colored distributed consensus problem
by Ryan Lau
BSc Natural Sciences (Physics & Physical Chemistry), University College London (UCL)

Abstract: Consider a collection of cells with a certain fraction of 3 distinct colours. There is some rule, of which when applied to the system, will turn all the cells to the majority colour when that fraction of the colours exceeds a certain threshold, reaching global consensus. The system will also exhibit indeterminate states when there are equal weights of colors. A general majority rule has been hypothesised and studied using grid cellular automata in cases of 2 and 3 colors. Some other rules are suggested, but their analysis is left for future studies. This report concludes with some criticism and possible future works.

Introduction

The Idea

The problem of distributed consensus has been well studied in the 2 colored case [1]. However, the existing literature is insufficient in solving for the problem of the 3-colored case. In this report, we will study this problem specifically on grid cellular automata. It is expected that the studies which will be conducted on the 3-colored case will provide some insight on how cellular automata links to certain properties in physical systems.

The problem

In this report, we will discuss some of the rules which perform on 3 colors, red, yellow and blue in 1-dimension (1D). The rules will be analogous to the majority function, similar to the GKL rule which will be discussed in future sections. The cells cannot decide which cell color is the majority, hence there will be indeterminate states of red yellow and blue. It is expected that the rule will provide us a “triple point” behaviour, where the cells cannot determine which color is the majority. The idea is studied via hypothesizing a general majority rule, and applying it to 2-colored and 3-colored system, with comparisons of their behaviours being made. Some other rules will also be suggested, but will be analysed in future works.

The Majority Function

The main idea of the majority function or rule is that it returns the majority color of some neighbouring cells. The sections below will have some more concrete examples.

The GKL rule

The Gacs-Kurdyumov-Levin (GKL) rule, or the “radius 3” rule operating on size-7 neighborhoods [1] provides us with a 1D deterministic cellular automaton rule that would lead to global consensus. Consider an initial system, Sys1, with a random arrangement of red cells with fraction p = 0.6. The rest will be yellow cells. The GKL rule as described by the following in the Wolfram Language is given as:

{l3_, _, l1_, c_, r1_, _, r3_} :> If[If[c == 0, r1 + r3, l1 + l3] + c >= 2, 1, 0]

We then apply it to the initial system Sys1:

In[]:=

Labeled[BlockRandom[SeedRandom[567];ArrayPlot[CellularAutomaton[{FromDigits[Tuples[{1,0},7]/.{l3_,_,l1_,c_,r1_,_,r3_}:>If[If[c==0,r1+r3,l1+l3]+c>=2,1,0],2],2,3},RandomChoice[{.6,.4}->{1,0},300],60],ColorRules->{0->Hue[0.15,0.72,1],1->Hue[0.98,1,0.8200000000000001]},Frame->False,ImageSize->Large]],"Fig 1: GKL rule when p = 0.6"]

Out[]=

Fig 1: GKL rule when p = 0.6

We can also consider another initial system, Sys2, with p = 0.4, and applying the same rule on it:

In[]:=

Labeled[BlockRandom[SeedRandom[569];ArrayPlot[CellularAutomaton[{FromDigits[Tuples[{1,0},7]/.{l3_,_,l1_,c_,r1_,_,r3_}:>If[If[c==0,r1+r3,l1+l3]+c>=2,1,0],2],2,3},RandomChoice[{.4,.6}->{1,0},300],60],ColorRules->{0->Hue[0.15,0.72,1],1->Hue[0.98,1,0.8200000000000001]},Frame->False,ImageSize->Large]],"Fig 2: GKL rule when p = 0.4"]

Out[]=

Fig 2: GKL rule when p = 0.4

Both cases successfully reaches to a “global consensus”. The plot below shows how the colors of the grids change with time for different initial systems, or different values of p:

In[]:=

data=ParallelTable[If[p==.5,Nothing,MeanAround/@Transpose[Table[Mean/@CellularAutomaton[{FromDigits[Tuples[{1,0},7]/.{l3_,_,l1_,c_,r1_,_,r3_}:>If[If[c==0,r1+r3,l1+l3]+c>=2,1,0],2],2,3},RandomChoice[{p,1-p}->{1,0},5000],200],200]]],{p,.3,.7,.05}];Labeled[ListLinePlot[MapThread[Callout[#1,Row[{Style["p",Italic],"=",#2},ImageSize->Large]]&,{data,Cases[Range[.3,.7,.05],Except[0.5]]}]],"Fig 3: Plot of color tendencies against the number of steps for different values of p"]

Out[]=

Fig 1: GKL rule when p = 0.6

The y-axis shows the color tendencies (0 for yellow, 1 for red), and the x-axis shows the number of steps performed. The plot above shows properties which are similar to a phase transition [2]. For p < 0.5, the cells will be all yellow; for p > 0.5, the cells will be all red. However at p = 0.5, the cellular automaton is “indecisive”, hence generating the following nested pattern:

In[]:=

Labeled[BlockRandom[SeedRandom[24425];ArrayPlot[CellularAutomaton[{FromDigits[Tuples[{1,0},7]/.{l3_,_,l1_,c_,r1_,_,r3_}:>If[If[c==0,r1+r3,l1+l3]+c>=2,1,0],2],2,3},RandomChoice[{.5,.5}->{1,0},1000],500],ColorRules->{0->Hue[0.15,0.72,1],1->Hue[0.98,1,0.8200000000000001]},Frame->False,ImageSizeLarge]],"Fig 4: GKL rule when p = 0.5"]

Out[]=

Fig 4: GKL rule when p = 0.5

The image above shows us a “critical phenomenon” [3], much like the critical point we see in properties of matter, where the matter itself is indistinguishably in a gas and liquid state at some definite temperature and pressure.

Rule 184

There are certain rules which gives us similar behaviour as discussed. For example, the rule 184 [4] when p = 0.5, with nested patterns of red and yellow stripes moving left and right :

In[]:=

Labeled[BlockRandom[SeedRandom[567];ArrayPlot[CellularAutomaton[184,RandomChoice[{1,0},400],180],ColorRules->{0->Hue[0.15,0.72,1],1->Hue[0.98,1,0.8200000000000001]},Frame->False,ImageSizeLarge]],"Fig 5: Rule 184 when p = 0.5"]

Out[]=

Fig 5: Rule 184 when p = 0.5

The Rules for the 3-Colored Problem

Method

For this particular problem, there are too many rules which one might investigate. Conducting an exhaustive search will be practically unfeasible as it is computationally too expensive. Better heuristics should be developed to perform such searches. Therefore, we will first construct an analog of the GKL via trial and error, together with some random searches within a rules, using the CellularAutomaton function. We will expect the system to have some phase transition properties for different weights of the 3 colors.

Translation from 2-colored to 3-colored rules

One cannot apply a 2-colored rule to a 3-colored rule in cellular automata. As given in the documentation [5], the 1D general RuleNumber, n, is specified by the following:

2r+1

(

)

where k is the number of colors, and r the number of nearest neighbours. In our case there will be

2r+1

rules that are applicable to 3 colors, with varying r.

Analog of the Majority Rule

The main goal of the majority rule is to let it decide on which color has the highest fraction after a certain number of steps. Here we can hypothesise a general majority rule as the following:

neighbors:{l3_,b3_,l1_,c_,r1_,b1_,r3_}:>First @ Commonest[neighbors]

Let us name the rule above Maj7. It operates on size-7 neighborhoods, and has a similar form as the GKL rule above. The overall rule number is given by the following:

FromDigits[Tuples[{1,0},7]/. neighbors:{l3_,b3_,l1_,c_,r1_,b1_,r3_}:>First @ Commonest[neighbors],k]

The k here indicates the number of colors in the system again. Let us see what it does on a two colored system, and have a plot to analyse what it gives us when p > 0.5 or p < 0.5:

In[]:=

Manipulate[ArrayPlot[CellularAutomaton[{FromDigits[Tuples[{1,0},7]/.neighbors:{l3_,b3_,l1_,c_,r1_,b1_,r3_}:>First@Commonest[neighbors],2],2,3},SeedRandom[seed];Normal[SparseArray[Thread[RandomSample[Range[400],Round[d400]]->1],400]],50,400],ImageSize->{500,369},PlotRange->{{0,w},{0,w}},PlotLabel->Text[Style["Fraction of red cell: "<>ToString[d],"Output",Bold]],ColorRules{0->Yellow,1->Red}],{{seed,1234,"Initial seeds "},1000,1500,1},{{d,0.5,"Fraction of red cell "},0.002,1},Delimiter,{{w,150,"zoom"},20,250,1}]

Out[]=

Initial seeds

Fraction of red cell

zoom

In[]:=

data2D=ParallelTable[If[p==.5,Nothing,Mean/@Transpose[Table[Mean/@CellularAutomaton[{FromDigits[Tuples[{1,0},7]/.neighbors:{l3_,b3_,l1_,c_,r1_,b1_,r3_}:>First@Commonest[neighbors],2],2,3},RandomChoice[{p,1-p}->{1,0},100],20],100]]],{p,.3,.7,.05}];Labeled[ListLinePlot[MapThread[Callout[#1,Row[{Style["p",Italic],"=",#2},ImageSize->Large]]&,{data2D,Cases[Range[.3,.7,.05],Except[0.5]]}],PlotRange{0,1}],"Fig 6: Plot of color tendencies against steps of the Maj7 rule with different values of p "]

Out[]=

Fig 6: Plot of color tendencies against steps of the Maj7 rule with different values of p

As we can see from Fig 6, there is a change of behaviour at p = 0.5, which are very similar to Fig 3. The difference is that the Maj7 rule does not help the system reach global consensus, only local consensus, unlike the GKL rule. We can then conclude the hypothesised rule does give some “phase transition” property when crossing
p = 0.5 .
From now onwards, let us label 0 as Yellow, 1 as Red and 2 as Blue for consistency throughout the code and notebook. Let us then look at what the Maj7 rule does with 3 colors:

In[]:=

Manipulate[{r,y,b}={rVal,yVal,bVal}//If[Total[#]>1,#/Total@#,#]&;{rVal,yVal,bVal}={r,y,b};ArrayPlot[CellularAutomaton[{FromDigits[Tuples[{2,1,0},7]/.neighbors:{l3_,b3_,l1_,c_,r1_,b1_,r3_}:>First@Commonest[neighbors],3],3,3},SeedRandom[seed];RandomChoice[{bVal,rVal,yVal}->{2,1,0},500],t],ImageSize->{500,369},PlotRange->{{0,w},{0,w}},PlotLabel->Column[{Text[Style["Fraction of red cells: "<>ToString[rVal],"Output",Bold]],Text[Style["Fraction of yellow cells: "<>ToString[yVal],"Output",Bold]],Text[Style["Fraction of blue cells: "<>ToString[bVal],"Output",Bold]]}],ColorRules{0->Yellow,1->Red,2->Blue}],{{seed,1200,"Initial seeds "},1000,1500,1},Delimiter,{{rVal,.333,"Fraction of red"},0,1,Appearance->"Open"},{{yVal,.333,"Fraction of yellow"},0,1,Appearance->"Open"},{{bVal,.333,"Fraction of blue"},0,1,Appearance->"Open"},{{t,60,"evolution steps"},0,600,1,Appearance->"Labeled"},Delimiter,{{w,150,"zoom"},100,400,1}]

Out[]=

Initial seeds

Fraction of red

0.53052

Fraction of yellow

0.178909

Fraction of blue

0.290571

evolution steps

zoom

In[]:=

Plotting a line graph like Fig 6 is not so easy for the 3-colored case. As there are 3 colors, which the weights have to add up to one, and the three colors have to be plot against the number of steps, one would need to plot a 4D graph to fully describe the system. To simplify the problem, the blue color is chosen to be fixed to have fractions of 0.3 and 0.5, and we then vary colors yellow and red, and use ListLinePlot3D to plot a 3D analog of Fig 6 to see whether the rule also gives us some phase transition properties:

In[]:=

yelldata3Dbluefix[b_:0.5]:=Table[With[{maxSteps=Length[row[[2]]],colorProp=row[[1]]},Transpose[{Range[maxSteps],ConstantArray[colorProp,maxSteps],row[[2]]}]],{row,ParallelTable[With[{r=1-b-y},If[r==(1-b)/2&&y==(1-b)/2&&r+b+y>1,Nothing,{y,Mean/@Transpose[Table[Mean/@CellularAutomaton[{FromDigits[Tuples[{2,1,0},7]/.neighbors:{l3_,b3_,l1_,c_,r1_,b1_,r3_}:>First@Commonest[neighbors],3],3,3},RandomChoice[Chop/@{b,r,y}->{2,1,0},200],20],30]]}]],{y,0.1,1-b,0.05}]}]ClearAll[y]reddata3Dbluefix[b_:0.5]:=Table[With[{maxSteps=Length[row[[2]]],colorProp=row[[1]]},Transpose[{Range[maxSteps],ConstantArray[colorProp,maxSteps],row[[2]]}]],{row,ParallelTable[With[{y=1-b-r},If[r==(1-b)/2&&y==(1-b)/2&&r+b+y>1,Nothing,{r,Mean/@Transpose[Table[Mean/@CellularAutomaton[{FromDigits[Tuples[{2,1,0},7]/.neighbors:{l3_,b3_,l1_,c_,r1_,b1_,r3_}:>First@Commonest[neighbors],3],3,3},RandomChoice[Chop/@{b,r,y}->{2,1,0},200],20],30]]}]],{r,0.1,1-b,0.05}]}]thirdblue=Labeled[ListPlot3D[{Flatten[yelldata3Dbluefix[0.3],1],Flatten[reddata3Dbluefix[0.3],1]},PlotStyle{Yellow,Red},ImageSizeLarge,Ticks->{Range[1,22,2],Range[0.7,0.1,-0.1],Range[0.2,1.4,0.2]},AxesLabel{"Steps","Color Proportion","Color Tendency"},LabelStyle->Directive[Black,Bold],PlotLabelStyle["Fraction of blue cells: 0.3",Bold]],"Fig 8a: Plot of color tendency against steps for different color proportions when fraction of blue cells = 0.3"]halfblue=Labeled[ListPlot3D[{Flatten[yelldata3Dbluefix[0.5],1],Flatten[reddata3Dbluefix[0.5],1]},PlotStyle{Yellow,Red},ImageSizeLarge,Ticks->{Range[1,22,2],Range[0.7,0.1,-0.1],Range[0.2,1.4,0.2]},AxesLabel{"Steps","Color Proportion","Color Tendency"},LabelStyle->Directive[Black,Bold],PlotLabelStyle["Fraction of blue cells: 0.5",Bold]],"Fig 8b: Plot of color tendency against steps for different color proportions when fraction of blue cells = 0.5"]

Out[]=

Fig 8a: Plot of color tendency against steps for different color proportions when fraction of blue cells = 0.3

Out[]=

Fig 8b: Plot of color tendency against steps for different color proportions when fraction of blue cells = 0.5

Conveniently, the red and yellow surfaces represents the colors red and yellow. The color tendency label is same as the color rules discussed before. Let us take Fig 8a for example. In the regime of low proportion of red colored cells or high proportion of yellow colored cells, the red colored cells will gradually turn into yellow colored cells, indicated by the decreasing color tendency towards the color yellow; The yellow colored cells will remain yellow, indicated by the unchanging gradient. The same applies to the opposite regime discussed. There exists a special point when two surfaces cross over each other (Color Proportion = 0.3 for Fig 8a ; Color Proportion = 0.5 for Fig 8b), which is when red and yellow have the same fraction. The crossing over in Fig 8a shows that the system cannot determine its majority color, shown by the unchanging gradient of the surface, as the 3 colors all are in equal weights. The crossing over in Fig 8b is different. While red and yellow have the same fraction, the majority color is blue, thus both red and yellow tends towards 0.5 after some steps. The rule therefore can determine the majority color successfully, but cannot reach global consensus. Although we can see the behaviours of the states, it is quite hard to interpret whether there are phase transition properties from above. To solve this problem future works, a plot can be made with fixing a step, but with varying weights of the 3 colors to get a bigger picture of the system and the majority rule itself.

I would also like to share some trial rules which gave some other interesting results:

In[]:=

Manipulate[{r,y,b}={rVal,yVal,bVal}//If[Total[#]>1,#/Total@#,#]&;{rVal,yVal,bVal}={r,y,b};ArrayPlot[CellularAutomaton[{FromDigits[Tuples[{2,1,0},7]/.neighbors:{l3_,b3_,l1_,c_,r1_,b1_,r3_}:>First@Commonest[neighbors],3],3,{{-8},{-5},{-4},{1},{2},{4},{6}}},SeedRandom[seed];RandomChoice[{bVal,rVal,yVal}->{2,1,0},500],t],ImageSize->{500,369},PlotRange->{{0,w},{0,w}},PlotLabel->Column[{Text[Style["Fraction of red cells: "<>ToString[rVal],"Output",Bold]],Text[Style["Fraction of yellow cells: "<>ToString[yVal],"Output",Bold]],Text[Style["Fraction of blue cells: "<>ToString[bVal],"Output",Bold]]}],ColorRules{0->Yellow,1->Red,2->Blue}],{{seed,1200,"Initial seeds "},1000,1500,1},Delimiter,{{rVal,.333,"Fraction of red"},0,1,Appearance->"Open"},{{yVal,.333,"Fraction of yellow"},0,1,Appearance->"Open"},{{bVal,.333,"Fraction of blue"},0,1,Appearance->"Open"},{{t,60,"evolution steps"},0,600,1,Appearance->"Labeled"},Delimiter,{{w,150,"zoom"},100,400,1}]

Out[]=

Initial seeds

Fraction of red

0.333

Fraction of yellow

0.333

Fraction of blue

0.333

evolution steps

zoom

In[]:=

Manipulate[{r,y,b}={rVal,yVal,bVal}//If[Total[#]>1,#/Total@#,#]&;{rVal,yVal,bVal}={r,y,b};ArrayPlot[CellularAutomaton[{FromDigits[Tuples[{2,1,0},7]/.neighbors:{l3_,b3_,l1_,c_,r1_,b1_,r3_}:>First@Commonest[neighbors],3],3,{{-10},{-9},{-2},{1},{4},{6},{10}}},SeedRandom[seed];RandomChoice[{bVal,rVal,yVal}->{2,1,0},500],t],ImageSize->{500,369},PlotRange->{{0,w},{0,w}},PlotLabel->Column[{Text[Style["Fraction of red cells: "<>ToString[rVal],"Output",Bold]],Text[Style["Fraction of yellow cells: "<>ToString[yVal],"Output",Bold]],Text[Style["Fraction of blue cells: "<>ToString[bVal],"Output",Bold]]}],ColorRules{0->Yellow,1->Red,2->Blue}],{{seed,1200,"Initial seeds "},1000,1500,1},Delimiter,{{rVal,.333,"Fraction of red"},0,1,Appearance->"Open"},{{yVal,.333,"Fraction of yellow"},0,1,Appearance->"Open"},{{bVal,.333,"Fraction of blue"},0,1,Appearance->"Open"},{{t,60,"evolution steps"},0,600,1,Appearance->"Labeled"},Delimiter,{{w,150,"zoom"},100,400,1}]

Out[]=

Initial seeds

Fraction of red

0.333

Fraction of yellow