HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Enabling Minimal Dominating Set in Highly Dynamic Distributed Systems

Swan Dubois 1 Mohamed Hamza Kaaouachi 1 Franck Petit 1
1 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : We address the problem of computing a Minimal Dominating Set in highly dynamic distributed systems. We assume weak connectivity, i.e., the network may be disconnected at each time instant and topological changes are unpredictable. We make only weak assumptions on the communication: every process is infinitely often able to communicate with other processes (not necessarily directly). Our contribution is threefold. First, we propose a new definition of minimal dominating set suitable for the context of time-varying graphs that seems more relevant than existing ones. Next, we provide a necessary and sufficient topological condition for the existence of a deterministic algorithm for minimal dominating set construction in our settings. Finally, we propose a new measure of time complexity in time-varying graph in order to to allow fair comparison between algorithms. Indeed, this measure takes account of communication delays attributable to dynamicity of the graph and not to the algorithms.
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

Contributor : Swan Dubois Connect in order to contact the contributor
Submitted on : Sunday, February 1, 2015 - 9:55:36 PM
Last modification on : Friday, January 21, 2022 - 3:21:41 AM
Long-term archiving on: : Wednesday, May 27, 2015 - 3:02:08 PM


Files produced by the author(s)



Swan Dubois, Mohamed Hamza Kaaouachi, Franck Petit. Enabling Minimal Dominating Set in Highly Dynamic Distributed Systems. 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'15), Aug 2015, Edmonton, AB, Canada. pp.51-66, ⟨10.1007/978-3-319-21741-3_4⟩. ⟨hal-01111610⟩



Record views


Files downloads