Complexity of network synchronization
From MaRDI portal
Publication:3765248
DOI10.1145/4221.4227zbMATH Open0628.68045OpenAlexW2092534058MaRDI QIDQ3765248FDOQ3765248
Authors: Baruch Awerbuch 
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
Recommendations
distributed algorithmssynchronizationasynchronous networkcommunication complexitysynchronous network
Cited In (only showing first 100 items - show all)
- Efficiency of Synchronous Versus Asynchronous Distributed Systems
- On the performance of a retransmission-based synchronizer
- Symmetry breaking depending on the chromatic number or the neighborhood growth
- Some aspects of parallel and distributed iterative algorithms - a survey
- Graph spanners: a tutorial review
- The local detection paradigm and its applications to self-stabilization
- A lower bound on the period length of a distributed scheduler
- Testing the diameter of graphs
- Fast deterministic distributed algorithms for sparse spanners
- Efficiency of semisynchronous versus asynchronous networks
- An efficient distributed algorithm for maximum matching in general graphs
- Efficient decentralized algorithms for the distributed trigger counting problem
- Small stretch \((\alpha ,\beta )\)-spanners in the streaming model
- On approximating tree spanners that are breadth first search trees
- New transience bounds for max-plus linear systems
- Distributed backup placement in networks
- Generating sparse spanners for weighted graphs
- Parallel \((\Delta +1)\)-coloring of constant-degree graphs
- 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
- Upper and lower bounds for stochastic marked graphs
- Hundreds of impossibility results for distributed computing
- A faster distributed protocol for constructing a minimum spanning tree
- Formalization and correctness of the PALS architectural pattern for distributed real-time systems
- Dual coordinate step methods for linear network flow problems
- A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
- The synchronization problem in protocol testing and its complexity
- Distributed shortest-path protocols for time-dependent networks
- Spanners of de Bruijn and Kautz graphs
- The bit complexity of the predecessor problem
- On specifications and proofs of timed circuits
- Tentative and definite distributed computations: An optimistic approach to network synchronization
- The power of multimedia: Combining point-to-point and multi-access networks
- Combinatorial network abstraction by trees and distances
- An optimal parallel algorithm to construct a tree 3-spanner on interval graphs
- Graph spanners in the streaming model: An experimental study
- Simple and efficient network decomposition and synchronization
- Fault-containing self-stabilizing distributed protocols
- Tree spanners of bounded degree graphs
- Fundamental Limits on Synchronizing Clocks Over Networks
- On sparse spanners of weighted graphs
- Self-stabilizing Byzantine asynchronous unison
- An improved algorithm for finding the median distributively
- Sublinear fully distributed partition with applications
- Low diameter graph decompositions
- The causal ordering abstraction and a simple way to implement it
- Title not available (Why is that?)
- The Steiner problem in distributed computing systems
- Streaming algorithm for graph spanners-single pass and constant processing time per edge
- Restrictions of minimum spanner problems
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- Approximation of minimum weight spanners for sparse graphs
- Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling
- Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
- The Iterated Restricted Immediate Snapshot Model
- Narrowing power vs efficiency in synchronous set agreement: relationship, algorithms and lower bound
- An efficient distributed algorithm for constructing small dominating sets
- Blocking versus nonblocking interprocess communication: A note on the effect on concurrency
- Title not available (Why is that?)
- Distributed minimum dominating set approximations in restricted families of graphs
- Approximating Shortest Paths in Graphs
- Distributed approximation of capacitated dominating sets
- Anonymous wireless rings
- Distributed discovery of large near-cliques
- On the complexity of distributed stable matching with small messages
- A linear time algorithm to construct a tree 4-spanner on trapezoid 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
- Gathering a Euclidean closed chain of robots in linear time and improved algorithms for chain-formation
- On the minimal time required for execution of distributed concurrent processes in synchronous modes
- Making Byzantine consensus live
- The Synergy of Finite State Machines
- A new synchronizer design
- Constructing Light Spanners Deterministically in Near-Linear Time
- Gathering a Euclidean closed chain of robots in linear time
- Algorithms and Computation
- Gracefully degrading consensus and \(k\)-set agreement in directed dynamic networks
- Making Byzantine consensus live
- Title not available (Why is that?)
- Distance-Preserving Graph Contractions
- Distance-Preserving Graph Contractions
- Distributed approximation of \(k\)-service assignment
- Making local algorithms wait-free: the case of ring coloring
- Covering Metric Spaces by Few Trees
- Title not available (Why is that?)
- Foundations of aggregation and synchronization in distributed systems
- Liveness and latency of Byzantine state-machine replication
- Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions
- Making asynchronous distributed computations robust to noise
- Improved guarantees for vertex sparsification in planar graphs
- Message lower bounds via efficient network synchronization
- Low-diameter graph decomposition is in NC
- Unison, canon, and sluggish clocks in networks controlled by a synchronizer
- Upper and lower bounds for the synchronizer performance in systems with probabilistic message loss
- Coupling coefficients of a distributed execution
- Message Lower Bounds via Efficient Network Synchronization
- Rapid convergence of a local load balancing algorithm for asynchronous rings
- A self-stabilizing algorithm for the maximum flow problem
- Derandomizing distributed algorithms with small messages: spanners and dominating set
- Highly concurrent logically synchronous multicast
This page was built for publication: Complexity of network synchronization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3765248)
