Flooding time in edge-Markovian dynamic graphs

DOI10.1145/1400751.1400781zbMath1301.05308OpenAlexW2013558775MaRDI QIDQ2934348

Francesco Pasquale, Claudio Macci, Angelo Monti, Riccardo Silvestri, Andrea E. F. Clementi

Publication date: 12 December 2014

Published in: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1400751.1400781

zbMATH Keywords

Markov processesrandom graphsflooding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Network design and communication in computer systems (68M10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (51)

Temporal network epidemiology ⋮ Continuous-time independent edge-Markovian random graph process ⋮ Traveling salesman problems in temporal graphs ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective ⋮ Coordinated consensus in dynamic networks ⋮ Error-free multi-valued consensus with byzantine failures ⋮ Distributed graph coloring in a few rounds ⋮ MIS on trees ⋮ Toward more localized local algorithms ⋮ The complexity of robust atomic storage ⋮ Resilience of mutual exclusion algorithms to transient memory faults ⋮ The impact of memory models on software reliability in multiprocessors ⋮ A complexity separation between the cache-coherent and distributed shared memory models ⋮ From bounded to unbounded concurrency objects and back ⋮ The space complexity of long-lived and one-shot timestamp implementations ⋮ Locally checkable proofs ⋮ Fault-tolerant spanners ⋮ Adaptively secure broadcast, revisited ⋮ Scalable rational secret sharing ⋮ Analyzing consistency properties for fun and profit ⋮ Transforming worst-case optimal solutions for simultaneous tasks into all-case optimal solutions ⋮ Optimal-time adaptive strong renaming, with applications to counting ⋮ The round complexity of distributed sorting ⋮ A tight unconditional lower bound on distributed randomwalk computation ⋮ Minimum congestion mapping in a cloud ⋮ Conflict on a communication channel ⋮ Stability of a peer-to-peer communication system ⋮ Tight bounds on information dissemination in sparse mobile networks ⋮ Time-efficient randomized multiple-message broadcast in radio networks ⋮ Faster information dissemination in dynamic networks via network coding ⋮ Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony ⋮ Causality, influence, and computation in possibly disconnected synchronous dynamic networks ⋮ Sharp Thresholds in Random Simple Temporal Graphs ⋮ Order optimal information spreading using algebraic gossip ⋮ Information Spreading in Dynamic Networks: An Analytical Approach ⋮ Evaluating the impact of selfish behaviors on epidemic forwarding in mobile social networks ⋮ Temporal network optimization subject to connectivity constraints ⋮ Fast and compact self-stabilizing verification, computation, and fault detection of an MST ⋮ Upper and lower bounds for the synchronizer performance in systems with probabilistic message loss ⋮ Structuring unreliable radio networks ⋮ Byzantine agreement with homonyms ⋮ Distributed deterministic edge coloring using bounded neighborhood independence ⋮ Compact policy routing ⋮ Cover time in edge-uniform stochastically-evolving graphs ⋮ Discovery Through Gossip ⋮ Parsimonious flooding in geometric random-walks ⋮ Parsimonious Flooding in Geometric Random-Walks ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective^* ⋮ Xheal ⋮ Distributed community detection in dynamic graphs ⋮ Distributed Community Detection in Dynamic Graphs

This page was built for publication: Flooding time in edge-Markovian dynamic graphs