Causality, influence, and computation in possibly disconnected synchronous dynamic networks

DOI10.1016/j.jpdc.2013.07.007zbMath1327.68046OpenAlexW1983815693WikidataQ57607983 ScholiaQ57607983MaRDI QIDQ897391

Othon Michail, Ioannis Chatzigiannakis, Paul G. Spirakis

Publication date: 18 December 2015

Published in: Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.759.6667

zbMATH Keywords

countingmobile computingterminationinformation disseminationoptimal protocoldynamic graphadversarial scheduletemporal connectivityworst-case dynamicity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Distributed systems (68M14) Network protocols (68M12)

Related Items

Traveling salesman problems in temporal graphs, A Glimpse at Paul G. Spirakis, An Introduction to Temporal Graphs: An Algorithmic Perspective, Beyond Rings: Gathering in 1-Interval Connected Graphs, On Verifying and Maintaining Connectivity of Interval Temporal Networks, The complexity of optimal design of temporally connected graphs, The computational power of simple protocols for self-awareness on graphs, Non-strict Temporal Exploration, Temporal network optimization subject to connectivity constraints, A faster exact-counting protocol for anonymous dynamic networks, Connectivity preserving network transformers, Exploration of the \(T\)-interval-connected dynamic graphs: the case of the ring, An Introduction to Temporal Graphs: An Algorithmic Perspective^*, On the expressivity of time-varying graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mediated population protocols
• Passively mobile communicating machines that use restricted space
• The computational power of population protocols
• Computation in networks of passively mobile finite-state sensors
• Distributed computation in dynamic networks
• Flooding time in edge-Markovian dynamic graphs
• Coordinated consensus in dynamic networks
• The Mathematical Coloring Book
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• Time, clocks, and the ordering of events in a distributed system
• Parsimonious flooding in dynamic graphs
• Temporal Network Optimization Subject to Connectivity Constraints
• Analyzing network coding gossip made easy
• On the Complexity of Information Spreading in Dynamic Networks
• Connectivity and inference problems for temporal networks