NDLI: Fair online load balancing

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

Tell me who I am: an interactive recommendation system

Towards automatic parallelization of tree reductions in dynamic programming

Smooth scheduling under variable rates or the analog-digital confinement game

Why Intel is designing multi-core processors

Efficient parallel algorithms for dead sensor diagnosis and multiple access channels

Modeling instruction placement on a spatial architecture

Tight bounds for the Min-Max boundary decomposition cost of weighted graphs

Compact routing with additive stretch using distance labelings

A distributed O(1)-approximation algorithm for the uniform facility location problem

The cache complexity of multithreaded cache oblivious algorithms

Distributed random digraph transformations for peer-to-peer networks

Chip-level integration: the new frontier for microprocessor architecture

Publish and perish: definition and analysis of an n-person publication impact game

A general approach for partitioning N-dimensional parallel nested loops with conditionals

On the price of heterogeneity in parallel systems

An empirical study to compare two parallel programming models

Conflict-free coloring for intervals: from offline to online

Translating between itanium and sparc memory consistency models

On space-stretch trade-offs: lower bounds

Semi-oblivious routing

Playing push vs pull: models and algorithms for disseminating dynamic data in networks

Fault-tolerant semifast implementations of atomic read/write registers

Towards a scalable and robust DHT

Energy implications of multiprocessor synchronization

The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions

Astronomical real-time streaming signal processing on a Blue Gene/L supercomputer

Reconfigurable resource scheduling

The FG programming environment: good and good for you

Packet-mode emulation of output-queued switches

Strip packing with precedence constraints and strip packing with release times

On space-stretch trade-offs: upper bounds

An implementation report for parallel triangular decompositions

A performance analysis of local synchronization

Fair online load balancing

Parallel depth first vs. work stealing schedulers on CMP architectures

Network design with weighted players

Exponential separation of quantum and classical online space complexity

Minimizing the stretch when scheduling flows of biological requests

Introducing the hydra parallel programming system

On the communication complexity of randomized broadcasting in random-like graphs

Power-aware scheduling for makespan and flow

Towards small world emergence

The cache-oblivious gaussian elimination paradigm: theoretical framework and experimental evaluation

Symmetric network computation

Deterministic load balancing and dictionaries in the parallel disk model

Minimizing peak energy on mesh-connected systems

An envolutionary path towards virtual shared memory with random access

Promoting cooperation in selfish grids

Fair online load balancing

Content Provider	ACM Digital Library
Author	Buchbinder, Niv Naor, Joseph Seffi
Abstract	We revisit from a fairness point of view the problem of online load balancing in the restricted assignment model and the 1-∞ model. We consider both a job-centric and a machine-centric view of fairness, as proposed by Goel et al. [11]. These notions are equivalent to the approximate notion of prefix competitiveness proposed by Kleinberg, Rabani and Tardos [14], as well as to the notion of approximate majorization, and they generalize the well studied notion of max-min fairness.We resolve a question posed by Goel,Meyerson and Plotkin [11] proving that the greedy strategy is globally O(logm)-fair, where m denotes the number of machines. This result improves upon the analysis of [11] who showed that the greedy strategy is globally O(log n)-fair, where n is the number of jobs. Typically, n > m, and therefore our improvement is significant. Our proof matches the known lower bound for the problem with respect to the measure of global fairness.The improved bound is obtained by analyzing, in a more accurate way, the more general restricted assignment model studied previously in [6]. We provide an alternative bound which is not worse than the bounds of [6], and it is strictly better in many cases. The bound we prove is, in fact, much more general and it bounds the load on any prefix of most loaded machines. As a corollary from this more general bound we get that the greedy algorithm results in an assignment that is globally O(logm)-balanced. The last result generalizes the previous result of [11] who proved that the greedy algorithm yields an assignment that is globally O(logm)-balanced for the 1-∞ model.
Starting Page	291
Ending Page	298
Page Count	8
File Format	PDF
ISBN	1595934529
DOI	10.1145/1148109.1148159
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2006-07-30
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Online algorithms Competitive analysis Greedy algorithm Scheduling Load balancing
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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