Consensus with Unknown Participants or Fundamental Self-Organization

We consider the problem of bootstrapping self-organized mobile ad hoc networks (MANET), i.e. reliably determining in a distributed and self- organized manner the services to be offered by each node when neither the identity nor the number of the nodes in the network is initially available. To this means we define a variant of the traditional consensus problem, by relaxing the requirement for the set of participating processes to be known by all at the beginning of the computation. This assumption captures the nature of self-organized networks, where there is no central authority that initializes each process with some context information. We consider asynchronous networks with reliable communication channels and no process crashes and provide necessary and sufficient conditions under which the problem admits a solution. These conditions are routing and mobility independent. Our results are relevant for agreement-related problems in general within self-organized networks.

Published in:
Proceedings of the 3rd International Conference on AD-HOC Networks & Wireless (ADHOC-NOW 2004), 135-148
Presented at:
Third International Conference on Ad hoc Networks and Wireless (ADHOC-NOW 2004), Vancouver, CA, 22-24 July 2004
Other identifiers:

Note: The status of this file is: Anyone

 Record created 2005-05-20, last modified 2020-10-25

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)