Improved bounds for distributed load balancing

DOI10.4230/LIPICS.DISC.2020.1MaRDI QIDQ6534998zbMATH OpenFDO

Authors Sepehr Assadi, Aaron Bernstein, Zachary Langley

Publication date 2 November 2023

Full work available at URL https://doi.org/10.4230/LIPICS.DISC.2020.1

zbMATH Keywords

matchingdistributed algorithmsload balancingsemi-matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25) Distributed algorithms (68W15)

Recommendations

• Distributed 2-approximation algorithm for the semi-matching problem
• Locally optimal load balancing
• On the distributed complexity of the semi-matching problem
• Parallel load balancing on constrained client-server topologies
• Localized Client-Server Load Balancing without Global Information

Cites work

• A data structure for dynamic trees
• A survey of game-theoretic approaches in wireless sensor networks
• All-norm approximation algorithms
• Approximation algorithms for minimum norm and ordered optimization problems
• Distributed 2-approximation algorithm for the semi-matching problem
• Distributed backup placement in networks
• Distributed backup placement in one round and its applications to maximum matching approximation and self-stabilization
• Faster algorithms for semi-matching problems
• Improved Distributed Approximate Matching
• Maintaining assignments online: matching, scheduling, and flows
• Online bipartite matching with amortized O(^2 n) replacements
• Parallel machine scheduling of machine-dependent jobs with unit-length.
• Scheduling independent tasks to reduce mean finishing time
• Self-stabilizing local k-placement of replicas with local minimum variance
• Selfish load balancing and atomic congestion games
• Semi-matchings for bipartite graphs and load balancing
• Simultaneously load balancing for every p-norm, with reassignments
• Technical Note—Minimizing Average Flow Time with Parallel Machines
• The price of anarchy for polynomial social cost

Cited in

(5)

• Load balancing: An exercise in constrained convergence
• Distributed Integer Balancing Under Weight Constraints in the Presence of Transmission Delays
• An Anytime Distributed Load-Balancing Algorithm Satisfying Capacity and Quantization Constraints
• Simultaneously approximating all _p-norms in correlation clustering
• Consistent load balancing via spread minimization

This page was built for publication: Improved bounds for distributed load balancing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6534998)