Distributed computation in dynamic networks
From MaRDI portal
Publication:2875179
DOI10.1145/1806689.1806760zbMath1293.68305MaRDI QIDQ2875179
Rotem Oshman, Fabian Kuhn, Nancy A. Lynch
Publication date: 13 August 2014
Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1721.1/62565
68M10: Network design and communication in computer systems
68R10: Graph theory (including graph drawing) in computer science
68M14: Distributed systems
05C40: Connectivity
68W15: Distributed algorithms
Related Items
Gathering in dynamic rings, Near-optimal communication-time tradeoff in fault-tolerant computation of aggregate functions, A topological perspective on distributed network algorithms, Asynchronous Byzantine reliable broadcast with a message adversary, Expansion and flooding in dynamic random networks with node churn, Search on a Line by Byzantine Robots, Blockchain in dynamic networks, Unnamed Item, Unnamed Item, Unnamed Item, Polynomial anonymous dynamic distributed computing without a unique leader, Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations, Beyond Rings: Gathering in 1-Interval Connected Graphs, On Verifying and Maintaining Connectivity of Interval Temporal Networks, Distributed Graph Algorithms and their Complexity: An Introduction, What Can be Computed in a Distributed System?, Enabling Minimal Dominating Set in Highly Dynamic Distributed Systems, Linear Search with Terrain-Dependent Speeds, Unnamed Item, Order optimal information spreading using algebraic gossip, Information spreading in dynamic graphs, Structuring unreliable radio networks, Temporal graph classes: a view through temporal separators, Smoothed analysis of dynamic networks, Byzantine agreement with homonyms, Distributed deterministic edge coloring using bounded neighborhood independence, Compact policy routing, Self-stabilizing robots in highly dynamic environments, An Introduction to Temporal Graphs: An Algorithmic Perspective*, Leader Election in Sparse Dynamic Networks with Churn, Traveling salesman problems in temporal graphs, Upper and lower bounds for deterministic broadcast in powerline communication networks, The computational power of simple protocols for self-awareness on graphs, Efficient routing in carrier-based mobile networks, A simple characterization of asynchronous computations, Fast and compact self-stabilizing verification, computation, and fault detection of an MST, Connectivity preserving network transformers, Meeting the deadline: on the complexity of fault-tolerant continuous gossip, Exploration of the \(T\)-interval-connected dynamic graphs: the case of the ring, On the treewidth of dynamic graphs, Bounded-contention coding for the additive network model, Causality, influence, and computation in possibly disconnected synchronous dynamic networks, Compact routing messages in self-healing trees, On linear-time data dissemination in dynamic rooted trees, Temporal network optimization subject to connectivity constraints, Gracefully degrading consensus and \(k\)-set agreement in directed dynamic networks, A faster exact-counting protocol for anonymous dynamic networks, Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony, Computing parameters of sequence-based dynamic graphs, Consensus in rooted dynamic networks with short-lived stability, Search on a line with faulty robots, Exploration of dynamic cactuses with sub-logarithmic overhead, How many cooks spoil the soup?, Synthesis in presence of dynamic links, Synchronization modulo \(P\) in dynamic networks, Distributed computation and reconfiguration in actively dynamic networks, Simple and fast approximate counting and leader election in populations, Some lower bounds in dynamic networks with oblivious adversaries, Distributed exploration of dynamic rings, On the radius of nonsplit graphs and information dissemination in dynamic networks, Exploration of carrier-based time-varying networks: the power of waiting, Exploration of dynamic networks: tight bounds on the number of agents, Polynomial anonymous dynamic distributed computing without a unique leader, The cost of global broadcast in dynamic radio networks, Group search of the plane with faulty robots, The firing squad problem revisited, Distributed computation in dynamic networks via random walks, A characterization of oblivious message adversaries for which consensus is solvable, On the expressivity of time-varying graphs, Distributed agreement in dynamic peer-to-peer networks, The complexity of optimal design of temporally connected graphs, Counting in one-hop beeping networks, How Many Cooks Spoil the Soup?, Xheal, Exploration of the T-Interval-Connected Dynamic Graphs: The Case of the Ring, A Characterization of Dynamic Networks Where Consensus Is Solvable, 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, Efficiently Testing $$T$$-Interval Connectivity in Dynamic Graphs, The Complexity of Data Aggregation in Directed Networks, Approximate Consensus in Highly Dynamic Networks: The Role of Averaging Algorithms, An Introduction to Temporal Graphs: An Algorithmic Perspective, The Firing Squad Problem Revisited.
