NDLI: A simple approach for adapting continuous load balancing processes to discrete settings

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

Faster randomized consensus with an oblivious adversary

Random walks which prefer unvisited edges.: exploring high girth even degree expanders in linear time.

The cost of fault tolerance in multi-party communication complexity

Brief announcement: what can be computed without communication?

Wait-freedom with advice

Distributed selfish load balancing with weights and speeds

Distributed maximal matching: greedy is optimal

Aggregation in dynamic networks

Brief announcement: achieving reliability in master-worker computing via evolutionary dynamics

Asynchronous failure detectors

A simple approach for adapting continuous load balancing processes to discrete settings

On the (limited) power of non-equivocation

Brief announcement: network formation games can give rise to realistic networks

Distributed algorithms for scheduling on line and tree networks

Faster than optimal snapshots (for a while): preliminary version

On the liveness of transactional memory

Information spreading in dynamic graphs

The communication complexity of distributed task allocation

Brief announcement: distributed algorithms for throughput performance in wireless networks

Universal constructions that ensure disjoint-access parallelism and wait-freedom

Making evildoers pay: resource-competitive broadcast in sensor networks

Lower bounds for local approximation

Distributed connectivity of wireless networks

Brief announcement: breaking the O(nm) bit barrier, secure multiparty computation with a static adversary

Simulations and reductions for colorless tasks

Dynamic packet scheduling in wireless networks

On the price of equivocation in byzantine agreement

Brief announcement: network-destabilizing attacks

Optimal distributed all pairs shortest paths and applications

Strongly linearizable implementations: possibilities and impossibilities

On the time and space complexity of randomized test-and-set

Coalescing random walks and voting on graphs

Collaborative search on the plane without communication

Brief announcement: distributed cryptography using trinc

Generalized lattice agreement

Distributed public key schemes secure against continual leakage

Weak models of distributed computing, with connections to modal logic

Leader election in shared spectrum radio networks

Brief announcement: maintaining large dense subgraphs on dynamic networks

A closer look at fault tolerance

Competitive and fair throughput for co-existing networks under adversarial interference

Byzantine broadcast in point-to-point networks using local linear coding

Brief announcement: tolerating permanent and transient value faults

Iterative approximate byzantine consensus in arbitrary directed graphs

Brief announcement: reconfigurable state machine replication from non-reconfigurable building blocks

Brief announcement: decentralized network supercomputing in the presence of malicious and crash-prone workers

Brief announcement: efficient causality tracking in distributed storage systems with dotted version vectors

Brief announcement: all-to-all gradecast using coding with byzantine failures

Brief announcement: order-preserving renaming in synchronous message passing systems with byzantine faults

Brief announcement: increasing the power of the iterated immediate snapshot model with failure detectors

Brief announcement: there are plenty of tasks weaker than perfect renaming and stronger than set agreement

Brief announcement: an obstacle to scalability in wireless networks

Brief announcement: delay or deliver dilemma in organization networks

Brief announcement: waiting in dynamic networks

Brief announcement: on the resilience of routing tables

Brief announcement: live streaming with utilities, quality and cost

Brief announcement: optimal amortized secret sharing with cheater identification

Brief announcement: a tight RMR lower bound for randomized mutual exclusion

Brief announcement: a calculus of policy-based routing systems

Brief announcement: efficient optimally resilient statistical AVSS and its applications

Brief announcement: From sequential to concurrent: correctness and relative efficiency

A simple approach for adapting continuous load balancing processes to discrete settings

Content Provider	ACM Digital Library
Author	Akbari, Hoda Berenbrink, Petra Sauerwald, Thomas
Abstract	We introduce a general method that converts a wide class of continuous neighborhood load balancing algorithms into a discrete version. Assume that initially the tasks are arbitrarily distributed among the nodes of a graph. In every round every node is allowed to communicate and exchange load with an arbitrary subset of its neighbors. The goal is to balance the load as evenly as possible. Continuous load balancing algorithms that are allowed to split tasks arbitrarily can balance the load perfectly, so that every node has exactly the same load. Discrete load balancing algorithms are not allowed to split tasks and therefore cannot balance the load perfectly. In this paper we consider the problem in a very general setting, where the tasks can have arbitrary weights and the nodes can have different speeds. Given a neighborhood load balancing algorithm that balances the load perfectly in t rounds, we convert the algorithm into a discrete version. This new algorithm is deterministic and balances the load in t rounds so that the difference between the average and the maximum load is at most $2d•w_{max},$ where d is the maximum degree of the network and $w_{max}$ is the maximum weight of any task. Compared to the previous methods that work for general graphs [12], our method achieves asymptotically lower discrepancies (e.g. O(1) vs. O(log n) for constant-degree expanders and O(r) vs. $O(n^{1/r})$ for r-dimensional tori) in the same number of rounds. For the case of uniform weights we present a randomized version of our algorithm balancing the load so that the difference between the minimum and the maximum load is at most O√dlog n) if the initial load on every node is large enough.
Starting Page	271
Ending Page	280
Page Count	10
File Format	PDF
ISBN	9781450314503
DOI	10.1145/2332432.2332486
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-07-16
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Randomized Load balancing Discrete diffusion
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