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