Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Enabling Minimal Dominating Set in Highly Dynamic Distributed Systems
verfasst von : Swan Dubois, Mohamed-Hamza Kaaouachi, Franck Petit
Erschienen in: Stabilization, Safety, and Security of Distributed Systems
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 allow fair comparison between algorithms. Indeed, this measure takes account of communication delays attributable to dynamicity of the graph and not to the algorithms.