Smoothed analysis of balancing networks

DOI10.1007/978-3-642-02930-1_39zbMATH Open1223.68019arXiv1006.1443OpenAlexW2571496458MaRDI QIDQ5198673FDOQ5198673

Authors: Tobias Friedrich, Thomas Sauerwald, Dan Vilenchik 

Publication date: 9 August 2011

Published in: Automata, Languages and Programming, Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: In a balancing network each processor has an initial collection of unit-size jobs (tokens) and in each round, pairs of processors connected by balancers split their load as evenly as possible. An excess token (if any) is placed according to some predefined rule. As it turns out, this rule crucially affects the performance of the network. In this work we propose a model that studies this effect. We suggest a model bridging the uniformly-random assignment rule, and the arbitrary one (in the spirit of smoothed-analysis). We start with an arbitrary assignment of balancer directions and then flip each assignment with probability $alpha$ independently. For a large class of balancing networks our result implies that after $Oh(logn)$ rounds the discrepancy is $Oh((1/2-alpha)logn+loglogn)$ with high probability. This matches and generalizes known upper bounds for $alpha=0$ and $alpha=1/2$. We also show that a natural network matches the upper bound for any $alpha$.

Full work available at URL: https://arxiv.org/abs/1006.1443

Recommendations

• Smoothed analysis of balancing networks
• The impact of randomization in smoothing networks
• Near-perfect load balancing by randomized rounding
• Improved analysis of deterministic load-balancing schemes
• Improved analysis of deterministic load-balancing schemes

zbMATH Keywords

distributed computingload balancingsmoothed analysisaverage case analysisbalancing networks

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Mathematical problems of computer architecture (68M07) Network design and communication in computer systems (68M10) Distributed systems (68M14)

Cites Work

• Counting networks
• Smoothed analysis of algorithms
• On smoothed analysis in dense graphs and formulas
• How many random edges make a dense graph hamiltonian?
• The diameter of randomly perturbed digraphs and some applications
• Smoothed analysis of binary search trees
• Self-stabilizing smoothing and balancing networks
• Near-perfect load balancing by randomized rounding
• The periodic balanced sorting network
• Smoothed analysis of integer programming
• Randomized smoothing networks

Cited In (12)

• Smoothed Analysis on Connected Graphs
• Smoothed Analysis on Connected Graphs
• Smoothed analysis of balancing networks
• Scheduling networks with variable topology in the presence of noise and delays in measurements
• The impact of randomization in smoothing networks
• Smoothed analysis of dynamic networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Randomized smoothing networks
• Self-stabilizing smoothing and balancing networks
• Smoothed analysis of local search algorithms
• Approximate consensus in the dynamic stochastic network with incomplete information and measurement delays

This page was built for publication: Smoothed analysis of balancing networks

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