Determining Majority in Networks With Local Interactions and Very Small Local Memory
The authors study here the problem of determining the majority type in an arbitrary connected network, each vertex of which has initially two possible types (states). The vertices may have a few additional possible states and can interact in pairs only if they share an edge. Any (population) protocol is required to stabilize in the initial majority, i.e. its output function must interpret the local state of each vertex so that each vertex outputs the initial majority type. They first provide a protocol with 4 states per vertex that always computes the initial majority value, under any fair scheduler.