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 (only showing first 100 items - show all)
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
This page was built for publication: Complexity of network synchronization
