Distributed Computing: A Locality-Sensitive Approach
From MaRDI portal
Publication:4517129
DOI10.1137/1.9780898719772zbMath0959.68042OpenAlexW4205300528WikidataQ63378952 ScholiaQ63378952MaRDI QIDQ4517129
Publication date: 21 November 2000
Full work available at URL: https://doi.org/10.1137/1.9780898719772
vertex coloringdistributed computingdistributed algorithmsbroadcastconvergecastmessage routingtree constructionsynchronizersdistributed network modeldowncastslocal querieslocal resource findingupcasts
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed systems (68M14) Distributed algorithms (68W15)
Related Items (only showing first 100 items - show all)
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Fast Distributed Approximation for Max-Cut ⋮ Additive Spanners for Circle Graphs and Polygonal Graphs ⋮ Coloring and Covering Nowhere Dense Graphs ⋮ Local deal-agreement algorithms for load balancing in dynamic general graphs ⋮ Network Decomposition and Distributed Derandomization (Invited Paper) ⋮ Stateless Information Dissemination Algorithms ⋮ Distance Labeling Schemes for $$K_4$$-Free Bridged Graphs ⋮ Synchronous \(t\)-resilient consensus in arbitrary graphs ⋮ Communication costs in a geometric communication network ⋮ Improved deterministic leader election in diameter-two networks ⋮ Four shades of deterministic leader election in anonymous networks ⋮ Node and edge averaged complexities of local graph problems ⋮ Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts ⋮ Distributed computations in fully-defective networks ⋮ Communication complexity meets cellular automata: necessary conditions for intrinsic universality ⋮ Brief announcement: Distributed reconfiguration of spanning trees ⋮ Termination of amnesiac flooding ⋮ Distributed connected dominating sets in unit square and disk graphs ⋮ Lipschitz-free Spaces on Finite Metric Spaces ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs ⋮ Unnamed Item ⋮ Simple Neural-Like P Systems for Maximal Independent Set Selection ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ Making Asynchronous Distributed Computations Robust to Channel Noise ⋮ Sparse communication networks and efficient routing in the plane ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ Compact and localized distributed data structures ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ Distributed Testing of Graph Isomorphism in the CONGEST Model. ⋮ Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners ⋮ What Can be Computed in a Distributed System? ⋮ Transitive-Closure Spanners: A Survey ⋮ Distributed construction of purely additive spanners ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fast distributed algorithms for testing graph properties ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Short labeling schemes for topology recognition in wireless tree networks ⋮ How long it takes for an ordinary node with an ordinary ID to output? ⋮ On the Microscopic View of Time and Messages ⋮ On Routing with Guaranteed Delivery in Three-Dimensional Ad Hoc Wireless Networks ⋮ Simple and local independent set approximation ⋮ A distributed algorithm for finding Hamiltonian cycles in random graphs in \(O(\log n)\) time ⋮ Topology recognition and leader election in colored networks ⋮ Efficient distributed approximation algorithms via probabilistic tree embeddings ⋮ A distributed low tree-depth decomposition algorithm for bounded expansion classes ⋮ Close to linear space routing schemes ⋮ Packet efficient implementation of the Omega failure detector ⋮ Weak models of distributed computing, with connections to modal logic ⋮ Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes ⋮ Collective Additive Tree Spanners of Homogeneously Orderable Graphs ⋮ Distributed localization of wireless sensor network using communication wheel ⋮ The Greedy Spanner Is Existentially Optimal ⋮ Making local algorithms wait-free: the case of ring coloring ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ Beep-and-sleep: message and energy efficient set cover ⋮ Distributed Tree Rearrangements for Reachability and Robust Connectivity ⋮ A topological perspective on distributed network algorithms ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ Improving Inter-cluster Broadcasting in Ad Hoc Networks by Delayed Flooding ⋮ Beep-and-sleep: message and energy efficient set cover ⋮ Local embeddings of metric spaces ⋮ Distributed MST for constant diameter graphs ⋮ Distributed algorithms for ultrasparse spanners and linear size skeletons ⋮ Distributed algorithms for the Lovász local lemma and graph coloring ⋮ Equilibria of Games in Networks for Local Tasks ⋮ The Synergy of Finite State Machines ⋮ Distributed Approximate Maximum Matching in the CONGEST Model. ⋮ Distributed set cover approximation: Primal-dual with optimal locality ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set ⋮ Congested Clique Algorithms for Graph Spanners ⋮ Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths ⋮ Light Spanners ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ Almost global problems in the LOCAL model ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Distributed Spanner Approximation ⋮ SKIP + ⋮ On the Complexity of Universal Leader Election ⋮ Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective* ⋮ Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE ⋮ Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree ⋮ Unnamed Item ⋮ Distributed Lower Bounds for Ruling Sets ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time ⋮ Near-Optimal Distributed Maximum Flow ⋮ Introduction to local certification ⋮ Latency, capacity, and distributed minimum spanning trees
This page was built for publication: Distributed Computing: A Locality-Sensitive Approach
