Abstract
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.
The work presented in this paper was supported by the National Competence Center in Research on Mobile Information and Communication Systems (NCCR-MICS), a center supported by the Swiss National Science Foundation under grant 5005-67322.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Fischer, M.J., Lynch, N.A., Paterson, M.: Impossibility of distributed consensus with one faulty process. JACM 32, 374–382 (1985)
Lynch, N.: Distributed Algorithms. Morgan Kaufmann, San Francisco (1996)
Dwork, C., Lynch, N., Stockmeyer, L.: Consensus in the presence of partial synchrony. J. ACM 35, 288–323 (1988)
Chandra, T.D., Toueg, S.: Unreliable failure detectors for reliable distributed systems. Journal of the ACM 43, 225–267 (1996)
Bar-Joseph, Z., Keidar, I., Lynch, N.: Early-delivery dynamic atomic broadcast. In: Malkhi, D. (ed.) DISC 2002. LNCS, vol. 2508, pp. 1–16. Springer, Heidelberg (2002)
Fischer, M.J.: The consensus problem in unreliable distributed systems (a brief survey). In: Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, pp. 127–140. Springer, Heidelberg (1983)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cavin, D., Sasson, Y., Schiper, A. (2004). Consensus with Unknown Participants or Fundamental Self-Organization. In: Nikolaidis, I., Barbeau, M., Kranakis, E. (eds) Ad-Hoc, Mobile, and Wireless Networks. ADHOC-NOW 2004. Lecture Notes in Computer Science, vol 3158. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-28634-9_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-28634-9_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22543-0
Online ISBN: 978-3-540-28634-9
eBook Packages: Springer Book Archive