Abstract
Besides the complexity in time or in number of messages, a common approach for analyzing distributed algorithms is to look at their assumptions on the underlying network. This paper focuses on the study of such assumptions in dynamic networks, where the connectivity is expected to change, predictably or not, during the execution. Our main contribution is a theoretical framework dedicated to such analysis. By combining several existing components (local computations, graph relabellings, and evolving graphs), this framework allows to express detailed properties on the network dynamics and to prove that a given property is necessary, or sufficient, for the success of an algorithm. Consequences of this work include (i) the possibility to compare distributed algorithms on the basis of their topological requirements, (ii) the elaboration of a formal classification of dynamic networks with respect to these properties, and (iii) the possibility to check automatically whether a network trace belongs to one of the classes, and consequently to know which algorithm should run on it.
Partially supported by A.N.R. grant No ANR-05-SSIA-0002-01.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distributed Computing 18(4), 235–253 (2006)
Angluin, D., Aspnes, J., Eisenstat, D., Ruppert, E.: The computational power of population protocols. Distributed Computing 20(4), 279–304 (2007)
Bhadra, S., Ferreira, A.: Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In: Pierre, S., Barbeau, M., Kranakis, E. (eds.) ADHOC-NOW 2003. LNCS, vol. 2865, pp. 259–270. Springer, Heidelberg (2003)
Bettstetter, C., Resta, G., Santi, P.: The node distribution of the random waypoint mobility model for wireless ad hoc networks. IEEE Transactions on Mobile Computing 2(3), 257–269 (2003)
Chalopin, J., Métivier, Y., Zielonka, W.: Local computations in graphs: The case of cellular edge local computations. Fundamenta Informaticae 74(1), 85–114 (2006)
Ferreira, A.: Building a reference combinatorial model for MANETs. IEEE Network 18(5), 24–29 (2004); A preliminary version appeared as On models and algorithms for dynamic communication networks: The case for evolving graphs, Algotel 2002, Meze, FR
Godard, E., Métivier, Y., Mosbah, M., Sellami, A.: Termination detection of distributed algorithms by graph relabelling systems. In: Corradini, A., Ehrig, H., Kreowski, H.-J., Rozenberg, G. (eds.) ICGT 2002. LNCS, vol. 2505, pp. 106–119. Springer, Heidelberg (2002)
Litovsky, I., Métivier, Y., Sopena, E.: Graph relabelling systems and distributed algorithms. In: World Scientific (ed.) Handbook of graph grammars and computing by graph transformation, vol. III, pp. 1–56. World Scientific, Singapore (1999)
Lynch, N.: A hundred impossibility proofs for distributed computing. In: PODC 1989: Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, pp. 1–28. ACM, New York (1989)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Casteigts, A., Chaumette, S., Ferreira, A. (2010). Characterizing Topological Assumptions of Distributed Algorithms in Dynamic Networks. In: Kutten, S., Žerovnik, J. (eds) Structural Information and Communication Complexity. SIROCCO 2009. Lecture Notes in Computer Science, vol 5869. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11476-2_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-11476-2_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11475-5
Online ISBN: 978-3-642-11476-2
eBook Packages: Computer ScienceComputer Science (R0)