2010 | OriginalPaper | Chapter
Low Memory Distributed Protocols for 2-Coloring
Authors : Amos Israeli, Mathew D. McCubbins, Ramamohan Paturi, Andrea Vattani
Published in: Stabilization, Safety, and Security of Distributed Systems
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper we present new distributed protocols to color even rings and general bipartite graphs. Our motivation is to provide algorithmic explanation for human subject experiments that show human subjects can achieve distributed coordination in the form of 2-coloring over networks with a simple communication protocol. All our protocols use low (often constant) memory and reach a solution in feasible (polynomial rounds) and sometimes optimal time. All the protocols also have short message length and use a broadcast communication strategy. Our contributions include two simple protocols
RingElect
and
GraphCoalescing
for rings and general bipartite graphs, which can be viewed as candidates for natural human strategies. We present two other protocols
RingElect
and
GraphElect
which are optimal or nearly optimal in terms of the number of rounds (proportional to the diameter of the graph) but require somewhat more complex strategies. The question of finding simple protocols in the style of
RingElect
and
GraphCoalescing
that run in time proportional to diameter is open.