Complexity of network synchronization
From MaRDI portal
Publication:3765248
DOI10.1145/4221.4227zbMath0628.68045OpenAlexW2092534058MaRDI QIDQ3765248
Publication date: 1985
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/4221.4227
synchronizationdistributed algorithmscommunication complexityasynchronous networksynchronous network
Related Items
A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs, Optimizing concurrency under Scheduling by Edge Reversal, On specifications and proofs of timed circuits, Expected linear round synchronization: the missing link for linear Byzantine SMR, Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions, Unnamed Item, A Near-Optimal Deterministic Distributed Synchronizer, Distributed shortest-path protocols for time-dependent networks, A self-stabilizing algorithm for the maximum flow problem, An efficient distributed algorithm for constructing small dominating sets, Hundreds of impossibility results for distributed computing, Improved Guarantees for Vertex Sparsification in Planar Graphs, Making local algorithms wait-free: the case of ring coloring, Covering Metric Spaces by Few Trees, Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs, Distance-Preserving Graph Contractions, On approximating tree spanners that are breadth first search trees, Tentative and definite distributed computations: An optimistic approach to network synchronization, Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling, Spanners of de Bruijn and Kautz graphs, The bit complexity of the predecessor problem, Graph spanners in the streaming model: An experimental study, Small stretch \((\alpha ,\beta )\)-spanners in the streaming model, Neighborhood graphs and distributed Δ+1-coloring, Causing communication closure: safe program composition with reliable non-FIFO channels, Testing the diameter of graphs, Generating sparse spanners for weighted graphs, Low-diameter graph decomposition is in NC, Gathering a Euclidean closed chain of robots in linear time, An improved algorithm for finding the median distributively, Highly concurrent logically synchronous multicast, A faster distributed protocol for constructing a minimum spanning tree, Parallel \((\Delta +1)\)-coloring of constant-degree graphs, The use of a synchronizer yields the maximum computation rate in distributed networks, Efficient distributed algorithms for single-source shortest paths and related problems on plane networks, Restrictions of minimum spanner problems, Dual coordinate step methods for linear network flow problems, Distributed minimum dominating set approximations in restricted families of graphs, Covering metric spaces by few trees, Efficiency of semisynchronous versus asynchronous networks, Distributed approximation of capacitated dominating sets, On the performance of a retransmission-based synchronizer, Symmetry breaking depending on the chromatic number or the neighborhood growth, Distributed strong diameter network decomposition, The local detection paradigm and its applications to self-stabilization, Unison, canon, and sluggish clocks in networks controlled by a synchronizer, Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs, Tree spanners of bounded degree graphs, Approximation of minimum weight spanners for sparse graphs, Repeated uncoordinated information dissemination by flooding, The Iterated Restricted Immediate Snapshot Model, Fast leader election in anonymous rings with bounded expected delay, An efficient distributed algorithm for maximum matching in general graphs, Fault-containing self-stabilizing distributed protocols, Toward more localized local algorithms: removing assumptions concerning global knowledge, Blocking versus nonblocking interprocess communication: A note on the effect on concurrency, Sublinear fully distributed partition with applications, Self-stabilizing Byzantine asynchronous unison, Local Maps: New Insights into Mobile Agent Algorithms, Making Asynchronous Distributed Computations Robust to Channel Noise, Fast deterministic distributed algorithms for sparse spanners, On the complexity of distributed stable matching with small messages, Distributed discovery of large near-cliques, Distributed approximation of \(k\)-service assignment, Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs, The causal ordering abstraction and a simple way to implement it, Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model, Anonymous wireless rings, Distributed backup placement in networks, Gracefully degrading consensus and \(k\)-set agreement in directed dynamic networks, New transience bounds for max-plus linear systems, Upper and lower bounds for the synchronizer performance in systems with probabilistic message loss, On sparse spanners of weighted graphs, Combinatorial network abstraction by trees and distances, A linear time algorithm to construct a tree 4-spanner on trapezoid graphs, Sparse covers for planar graphs and graphs that exclude a fixed minor, An optimal parallel algorithm to construct a tree 3-spanner on interval graphs, A lower bound on the period length of a distributed scheduler, Streaming algorithm for graph spanners-single pass and constant processing time per edge, Efficient decentralized algorithms for the distributed trigger counting problem, Coupling coefficients of a distributed execution, Making asynchronous distributed computations robust to noise, Space efficient and time optimal distributed BFS tree construction, A fault-containing self-stabilizing \((3-\frac 2{\varDelta+1})\)-approximation algorithm for vertex cover in anonymous networks, Formalization and correctness of the PALS architectural pattern for distributed real-time systems, A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs, Unnamed Item, Unnamed Item, Unnamed Item, Graph spanners: a tutorial review, The power of multimedia: Combining point-to-point and multi-access networks, Approximating Shortest Paths in Graphs, Fast fault-tolerant parallel communication and on-line maintenance for hypercubes using information dispersal, Message lower bounds via efficient network synchronization, On the memory overhead of distributed snapshots, Constructing Light Spanners Deterministically in Near-Linear Time, The Synergy of Finite State Machines, Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set, On the use of random numbers in asynchronous simulation via rollback, Message Lower Bounds via Efficient Network Synchronization, Constructing light spanners deterministically in near-linear time, Simple and efficient network decomposition and synchronization, Narrowing power vs efficiency in synchronous set agreement: relationship, algorithms and lower bound, Rapid convergence of a local load balancing algorithm for asynchronous rings, Mixed-integer programming approaches for the tree \(t^*\)-spanner problem, Distance-Preserving Graph Contractions, Light spanners for high dimensional norms via stochastic decompositions, Gathering a Euclidean closed chain of robots in linear time and improved algorithms for chain-formation, The Steiner problem in distributed computing systems, Making Byzantine consensus live, An optimal distributed algorithm for recognizing mesh-connected networks, Some aspects of parallel and distributed iterative algorithms - a survey, Maintaining bipartite matchings in the presence of failures, Low diameter graph decompositions, Graph theoretical issues in computer networks, Upper and lower bounds for stochastic marked graphs
