NDLI: Selfish load balancing and atomic congestion games

Please wait, while we are loading the content...

On delivery times in packet networks under adversarial traffic

Object location in realistic networks

Fighting against two adversaries: page migration in dynamic networks

Packet-mode policies for input-queued switches

Balanced graph partitioning

Scheduling against an adversarial network

Sharing the cost of multicast transmissions in wireless networks

A scalable lock-free stack algorithm

Effectively sharing a cache among threads

Improved combination of online algorithms for acceptance and rejection

Online algorithms for network design

Dynamic analysis of the arrow distributed protocol

Adaptive channel queue routing on k-ary n-cubes

Simple efficient load balancing algorithms for peer-to-peer systems

Online hierarchical cooperative caching

Parallelism versus memory allocation in pipelined router forwarding engines

Bi-criteria algorithm for scheduling jobs on cluster platforms

On achieving optimized capacity utilization in application overlay networks with multiple competing sessions

Selfish load balancing and atomic congestion games

DCAS is not a silver bullet for nonblocking algorithm design

Cache-oblivious shortest paths in graphs using buffer heap

Time complexity of practical parallel steiner point insertion algorithms

Expansion properties of (secure) wireless networks

Optimal early stopping uniform consensus in synchronous systems with process omission failures

Compact name-independent routing with minimum stretch

Consistent and compact data management in distributed storage systems

New results on web caching with request reordering

Lower bounds for graph embeddings and combinatorial preconditioners

On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs

Pagoda: a dynamic overlay network for routing, data management, and multicasting

How to route and tax selfish unsplittable traffic

Efficient orchestration of sub-word parallelism in media processors

Online algorithms for prefetching and caching on parallel disks

The inherent queuing delay of parallel packet switches

The effect of faults on network expansion

Writing-all deterministically and optimally using a non-trivial number of asynchronous processors

Geometric generalizations of the power of two choices

An NC algorithm for finding a maximal acyclic set in a graph

Efficient search in unstructured peer-to-peer networks

The potential in energy efficiency of a speculative chip-multiprocessor

Selfish load balancing and atomic congestion games

Content Provider	ACM Digital Library
Author	Suri, Subhash Zhou, Yunhong Tóth, Csaba D.
Abstract	We revisit a classical load balancing problem in the modern context of decentralized systems and self-interested clients. In particular, there is a set of clients, each of whom must choose a server from a permissible set. Each client selfishly wants to minimize its own latency (job completion time). A server's latency is inversely proportional to its speed, but it grows linearly with or, more generally, as the pth power of the number of clients matched to it. This interaction is naturally modeled as an atomic congestion game, which we call selfish load balancing. We analyze the Nash equilibria of this game and prove nearly tight bounds on the price of anarchy (worst-case ratio between a Nash solution and the social optimum). In particular, for linear latency functions, we show that if the server speeds are relatively bounded and the number of clients is large compared to the number of servers, then every Nash assignment approaches social optimum. Without any assumptions on the number of clients, servers, and server speeds, the price of anarchy is at most 2.5. If all servers have the same speed, then the price of anarchy further improves to 1 + 2/√3 ≈ 2.15. We also exhibit a lower bound of 2.01. Our proof techniques can also be adapted for the coordinated load balancing problem under L2 norm, where it slightly improves the best previously known upper bound on the competitive ratio of a simple greedy scheme.
Starting Page	188
Ending Page	195
Page Count	8
File Format	PDF
ISBN	1581138407
DOI	10.1145/1007912.1007941
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2004-06-27
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Congestion game Greedy algorithm Nash equilibrium Load balancing Price of anarchy
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Selfish load balancing and atomic congestion games (2007).

Selfish load balancing and atomic congestion games (2004)

On the performance of approximate equilibria in congestion games

An approximation algorithm and price of anarchy for the binary-preference capacitated selfish replication game

The effect of collusion in congestion games

Graphical congestion games with linear latencies

Exact Price of Anarchy for Polynomial Congestion Games

Fast convergence to nearly optimal solutions in potential games

Symmetry in Network Congestion Games: Pure Equilibria and Anarchy Cost (2005)

Selfish load balancing and atomic congestion games

Similar Documents

Selfish load balancing and atomic congestion games (2007).

Selfish load balancing and atomic congestion games (2004)

On the performance of approximate equilibria in congestion games

An approximation algorithm and price of anarchy for the binary-preference capacitated selfish replication game

The effect of collusion in congestion games

Graphical congestion games with linear latencies

Exact Price of Anarchy for Polynomial Congestion Games

Fast convergence to nearly optimal solutions in potential games

Symmetry in Network Congestion Games: Pure Equilibria and Anarchy Cost (2005)

Selfish load balancing and atomic congestion games