Distributed Selfish Load Balancing

DOI10.1137/060660345MaRDI QIDQ3519392zbMATH OpenOpenAlexFDO

Authors Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul W. Goldberg, Zengjian Hu, Russell Martin

Publication date 14 August 2008

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0506098, http://dro.dur.ac.uk/649/1/649.pdf

zbMATH Keywords

convergenceequilibriumload balancingreallocation

Mathematics Subject Classification ID

Distributed systems (68M14) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25) Applications of game theory (91A80)

Abstract: Suppose that a set of $m$ tasks are to be shared as equally as possible amongst a set of $n$ resources. A game-theoretic mechanism to find a suitable allocation is to associate each task with a ``selfish agent, and require each agent to select a resource, with the cost of a resource being the number of agents to select it. Agents would then be expected to migrate from overloaded to underloaded resources, until the allocation becomes balanced. Recent work has studied the question of how this can take place within a distributed setting in which agents migrate selfishly without any centralized control. In this paper we discuss a natural protocol for the agents which combines the following desirable features: It can be implemented in a strongly distributed setting, uses no central control, and has good convergence properties. For $mggn$, the system becomes approximately balanced (an $epsilon$-Nash equilibrium) in expected time $O(loglogm)$. We show using a martingale technique that the process converges to a perfectly balanced allocation in expected time $O(loglogm+n^4)$. We also give a lower bound of $Omega(maxloglogm,n)$ for the convergence time.

Recommendations

• Distributed selfish load balancing on networks
• Distributed selfish load balancing on networks
• Distributed selfish load balancing with weights and speeds
• Selfish load balancing
• Convergence to Equilibria in Distributed, Selfish Reallocation Processes with Weighted Tasks

Cited in

(25)

• Promoting cooperation in selfish computational grids
• Distributed balanced color assignment on arbitrary networks
• Noncooperative load balancing in distributed systems
• Parallel load balancing on constrained client-server topologies
• Concurrent imitation dynamics in congestion games
• Tight bounds for parallel randomized load balancing
• Distributed selfish load balancing with weights and speeds
• Selfish Traffic Allocation for Server Farms
• Distributed load balancing algorithms for heterogeneous players in asynchronous networks
• Performance of global load balancing by local adjustment
• Selfish load balancing
• Selfish Load Balancing Under Partial Knowledge
• Convergence to Equilibria in Distributed, Selfish Reallocation Processes with Weighted Tasks
• Decentralized list scheduling
• Reducing price of anarchy of selfish task allocation with more selfishness
• Distributed selfish load balancing on networks
• Self-Learning Threshold-Based Load Balancing
• Load balancing without regret in the bulletin board model
• Distributed selfish load balancing on networks
• Convergence to approximate Nash equilibria in congestion games
• Game-theoretic static load balancing for distributed systems
• Distributed algorithms for QoS load balancing
• Load balancing without regret in the bulletin board model
• A game-theoretic framework for distributed load balancing: static and dynamic game models
• Selfish load balancing and atomic congestion games

This page was built for publication: Distributed Selfish Load Balancing

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