NDLI: Tight bounds for parallel randomized load balancing: extended abstract

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

The power of simple tabulation hashing

Quantum one-way communication can be exponentially stronger than classical communication

Cover times, blanket times, and majorizing measures

The equivalence of the random oracle model and the ideal cipher model, revisited

On optimal single-item auctions

Towards coding for maximum errors in interactive communication

Rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm

Moser and tardos meet Lovász

Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs

An algorithm for the graph crossing number problem

The computational complexity of linear optics

Distributed verification and hardness of distributed approximation

An LLL-reduction algorithm with quasi-linear time complexity: extended abstract

Contraction decomposition in h-minor-free graphs and algorithmic applications

On the complexity of powering in finite fields

Mechanisms for (mis)allocating scientific credit

Don't rush into a union: take time to find your roots

Online bipartite matching with unknown distributions

K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance

Schaefer's theorem for graphs

Constant round non-malleable protocols using one way functions

Fast moment estimation in data streams in optimal space

Submodular function maximization via the multilinear relaxation and contention resolution schemes

Tight bounds for parallel randomized load balancing: extended abstract

Strong direct product theorems for quantum communication and query complexity

A general framework for graph sparsification

Separating succinct non-interactive arguments from all falsifiable assumptions

Optimal auctions with correlated bidders are easy

High-rate codes with sublinear-time decoding

Exact algorithms for solving stochastic games: extended abstract

A full derandomization of schöning's k-SAT algorithm

Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

Improved algorithms for min cut and max flow in undirected planar graphs

A quasipolynomial-time algorithm for the quantum separability problem

Linearizable implementations do not suffice for randomized distributed computation

NP-hardness of approximately solving linear equations over reals

A simpler algorithm and shorter proof for the graph minor decomposition

Almost settling the hardness of noncommutative determinant

Inner product spaces for MinSum coordination mechanisms

A unified framework for approximating and clustering data

Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs

Breaking the $k^{2}$ barrier for explicit RIP matrices

Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP

Constant-round non-malleable commitments from any one-way function

Subspace embeddings for the $L_{1}-norm$ with applications

Learning submodular functions

Social networks spread rumors in sublogarithmic time

An optimal lower bound on the communication complexity of gap-hamming-distance

Breaking $o(n^{1/2})-approximation$ algorithms for the edge-disjoint paths problem with congestion two

Limits of provable security from standard assumptions

An impossibility result for truthful combinatorial auctions with submodular valuations

From affine to two-source extractors via approximate duality

Dueling algorithms

Pseudorandom generators for combinatorial shapes

Analyzing network coding gossip made easy

Directed spanners via flow-based linear programs

Parallel repetition of entangled games

The topology of wireless communication

Black-box identity testing of depth-4 multilinear circuits

Multicut is FPT

Geometric complexity theory and tensor rank

Mechanism design with uncertain inputs: (to err is human, to forgive divine)

Approximate polytope membership queries

Almost tight bounds for reordering buffer management

Deterministic construction of a high dimensional $l_{p}$ section in $l_{1}^{n}$ for any p<2

Every property of hyperfinite graphs is testable

Secure computation with information leaking to an adversary

Near-optimal distortion bounds for embedding doubling spaces into $L_{1}$

Privately releasing conjunctions and the statistical query barrier

From convex optimization to randomized mechanisms: toward optimal combinatorial auctions

Correlation testing for affine invariant properties on $F_{p}^{n}$ in the high error regime

Pareto optimal solutions for smoothed analysts

Pseudorandom generators for group products: extended abstract

Optimal path search in small worlds: dimension matters

Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter

Fixed-parameter tractability of multicut parameterized by the size of the cutset

Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes

Santa Claus schedules jobs on unrelated machines

Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs

How to leak on key updates

From low-distortion norm embeddings to explicit uncertainty relations and efficient information locking

Privacy-preserving statistical estimation with optimal convergence rates

Finding topological subgraphs is fixed-parameter tractable

Near-optimal private approximation protocols via a black box transformation

Tight bounds for parallel randomized load balancing: extended abstract

Content Provider	ACM Digital Library
Author	Lenzen, Christoph Wattenhofer, Roger
Abstract	We explore the fundamental limits of distributed balls-into-bins algorithms, i.e., algorithms where balls act in parallel, as separate agents. This problem was introduced by Adler et al., who showed that non-adaptive and symmetric algorithms cannot reliably perform better than a maximum bin load of Theta(log log n / log log log n) within the same number of rounds. We present an adaptive symmetric algorithm that achieves a bin load of two in log* n+O(1) communication rounds using O(n) messages in total. Moreover, larger bin loads can be traded in for smaller time complexities. We prove a matching lower bound of (1-o(1))log* n on the time complexity of symmetric algorithms that guarantee small bin loads at an asymptotically optimal message complexity of O(n). The essential preconditions of the proof are (i) a limit of O(n) on the total number of messages sent by the algorithm and (ii) anonymity of bins, i.e., the port numberings of balls are not globally consistent. In order to show that our technique yields indeed tight bounds, we provide for each assumption an algorithm violating it, in turn achieving a constant maximum bin load in constant time. As an application, we consider the following problem. Given a fully connected graph of n nodes, where each node needs to send and receive up to n messages, and in each round each node may send one message over each link, deliver all messages as quickly as possible to their destinations. We give a simple and robust algorithm of time complexity O(log* n) for this task and provide a generalization to the case where all nodes initially hold arbitrary sets of messages. Completing the picture, we give a less practical, but asymptotically optimal algorithm terminating within O(1) rounds. All these bounds hold with high probability.
Starting Page	11
Ending Page	20
Page Count	10
File Format	PDF MP4
ISBN	9781450306911
DOI	10.1145/1993636.1993639
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-06-06
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Asymptotic bounds Randomized allocation Load balancing
Content Type	Audio 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