Characterizing topological assumptions of distributed algorithms in dynamic networks

DOI10.1007/978-3-642-11476-2_11MaRDI QIDQ3408165zbMATH OpenOpenAlexFDO

Authors S. Chaumette, Arnaud Casteigts, Afonso G. Ferreira

Publication date 24 February 2010

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.5529

zbMATH Keywords

distributed algorithmsdynamic networksevolving graphslocal interactionstopological assumptions

Mathematics Subject Classification ID

Network protocols (68M12) Distributed systems (68M14) Distributed algorithms (68W15)

Abstract: Besides the complexity in time or in number of messages, a common approach for analyzing distributed algorithms is to look at the assumptions they make on the underlying network. We investigate this question from the perspective of network dynamics. In particular, we ask how a given property on the evolution of the network can be rigorously proven as necessary or sufficient for a given algorithm. The main contribution of this paper is to propose the combination of two existing tools in this direction: local computations by means of graph relabelings, and evolving graphs. Such a combination makes it possible to express fine-grained properties on the network dynamics, then examine what impact those properties have on the execution at a precise, intertwined, level. We illustrate the use of this framework through the analysis of three simple algorithms, then discuss general implications of this work, which include (i) the possibility to compare distributed algorithms on the basis of their topological requirements, (ii) a formal hierarchy of dynamic networks based on these requirements, and (iii) the potential for mechanization induced by our framework, which we believe opens a door towards automated analysis and decision support in dynamic networks.

Recommendations

• Time to change: on distributed computing in dynamic networks (keynote)
• Special issue on algorithmic theory of dynamic networks and its applications -- preface
• A topological perspective on distributed network algorithms
• Distributed computation in dynamic networks
• A connectivity model for agreement in dynamic systems

Cites work

• Computation in networks of passively mobile finite-state sensors
• scientific article; zbMATH DE number 2016070 (Why is no real title available?)
• Local computations in graphs: the case of cellular edge local computations
• The computational power of population protocols

Cited in

(12)

• Computing parameters of sequence-based dynamic graphs
• The complexity of data aggregation in static and dynamic wireless sensor networks
• Special issue on algorithmic theory of dynamic networks and its applications -- preface
• On the expressivity of time-varying graphs
• Efficiently testing T-interval connectivity in dynamic graphs
• scientific article; zbMATH DE number 4058842 (Why is no real title available?)
• An Introduction to the Topological Theory of Distributed Computing with Safe-consensus
• The complexity of data aggregation in static and dynamic wireless sensor networks
• Time to change: on distributed computing in dynamic networks (keynote)
• Distributed Computation and Reconfiguration in Actively Dynamic Networks
• Threshold-based network structural dynamics
• On the treewidth of dynamic graphs

This page was built for publication: Characterizing topological assumptions of distributed algorithms in dynamic networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3408165)