TY - GEN
T1 - Integration
T2 - Military Communications Conference 2006, MILCOM 2006
AU - Olariu, Stephan
AU - Nickerson, Jeffrey
PY - 2006
Y1 - 2006
N2 - In a centrally controlled system consensus is often reached by decree: the central entity in charge of the system dictates the "consensus" to the rank-and-file. The situation is vastly different in a truly decentralized distributed system where the various entities in the system must agree on a common view the consensus. Consensus is, in this regard, an exercise in integration, for it is the local, often parochial, views of the various participants that are being integrated in the process. We study the consensus problem in an eminently decentralized distributed system populated by anonymous participants communicating by radio. Our main contribution is to show that consensus can be reached in four deterministic communication steps in systems whose underlying graph has diameter two, even if the topology of the network is completely unknown to the participants. This result is relevant to all situations where a consensus must be reached by anonymous participants (who perhaps do not wish to reveal their identities) provided that the underlying graph has low diameter.
AB - In a centrally controlled system consensus is often reached by decree: the central entity in charge of the system dictates the "consensus" to the rank-and-file. The situation is vastly different in a truly decentralized distributed system where the various entities in the system must agree on a common view the consensus. Consensus is, in this regard, an exercise in integration, for it is the local, often parochial, views of the various participants that are being integrated in the process. We study the consensus problem in an eminently decentralized distributed system populated by anonymous participants communicating by radio. Our main contribution is to show that consensus can be reached in four deterministic communication steps in systems whose underlying graph has diameter two, even if the topology of the network is completely unknown to the participants. This result is relevant to all situations where a consensus must be reached by anonymous participants (who perhaps do not wish to reveal their identities) provided that the underlying graph has low diameter.
UR - http://www.scopus.com/inward/record.url?scp=35148849671&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35148849671&partnerID=8YFLogxK
U2 - 10.1109/MILCOM.2006.302483
DO - 10.1109/MILCOM.2006.302483
M3 - Conference contribution
AN - SCOPUS:35148849671
SN - 1424406188
SN - 9781424406180
T3 - Proceedings - IEEE Military Communications Conference MILCOM
BT - Military Communications Conference 2006, MILCOM 2006
Y2 - 23 October 2006 through 25 October 2006
ER -