Paper Info
Title
Low memory distributed protocols for 2-coloring
Abstract
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 RingGuess 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 RINGGUESS and GRAPHCOALESCING that run in time proportional to diameter is open.
Year
DOI
Venue
2010
10.1007/978-3-642-16023-3_26
SSS
Keywords
Field
DocType
simple protocol,general bipartite graph,natural human strategy,simple protocols ringguess,low memory,broadcast communication strategy,human subject,protocols ringelect,simple communication protocol,optimal time,human subject experiment,communication protocol,bipartite graph
Leader election,Consensus,Graph,Polynomial,Random walk,Computer science,Bipartite graph,Theoretical computer science,Broadcast communication network,Communications protocol
Conference
Volume
ISSN
ISBN
6366
0302-9743
3-642-16022-0
Citations 
PageRank 
References 
0
0.34
8
Authors
4
Name
Order
Citations
PageRank
Amos Israeli11085113.39
Mathew D. McCubbins2123.22
Ramamohan Paturi3126092.20
Andrea Vattani417111.45