Show simple item record

dc.contributor.authorCai, Leranen
dc.contributor.authorSauerwald, Thomasen
dc.contributor.editorChatzigiannakis, Ien
dc.contributor.editorKuhn, Fen
dc.contributor.editorMuscholl, Aen
dc.contributor.editorIndyk, Pen
dc.date.accessioned2017-05-19T08:45:37Z
dc.date.available2017-05-19T08:45:37Z
dc.date.issued2017-07-14en
dc.identifier.issn1868-8969
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/264307
dc.description.abstractIterative load balancing algorithms for indivisible tokens have been studied intensively in the past. Complementing previous worst-case analyses, we study an average-case scenario where the load inputs are drawn from a fixed probability distribution. For cycles, tori, hypercubes and expanders, we obtain almost matching upper and lower bounds on the discrepancy, the difference between the maximum and the minimum load. Our bounds hold for a variety of probability distributions including the uniform and binomial distribution but also distributions with unbounded range such as the Poisson and geometric distribution. For graphs with slow convergence like cycles and tori, our results demonstrate a substantial difference between the convergence in the worst- and average-case. An important ingredient in our analysis is a new upper bound on the t-step transition probability of a general Markov chain, which is derived by invoking the evolving set process.
dc.publisherLeibniz International Proceedings in Informatics
dc.rightsAttribution 4.0 Internationalen
dc.rightsAttribution 4.0 Internationalen
dc.rightsAttribution 4.0 Internationalen
dc.rightsAttribution 4.0 Internationalen
dc.rightsAttribution 4.0 Internationalen
dc.rightsAttribution 4.0 Internationalen
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/en
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/en
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/en
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/en
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/en
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/en
dc.subjectrandom walksen
dc.subjectrandomized algorithmsen
dc.subjectparallel computingen
dc.titleRandomized Load Balancing on Networks with Stochastic Inputsen
dc.typeConference Object
prism.publicationDate2017en
dc.identifier.doi10.17863/CAM.9751
dcterms.dateAccepted2017-04-14en
rioxxterms.versionAM
rioxxterms.licenseref.urihttp://creativecommons.org/licenses/by/4.0/en
rioxxterms.licenseref.startdate2017-07-14en
rioxxterms.typeConference Paper/Proceeding/Abstracten
pubs.funder-project-idECH2020 EUROPEAN RESEARCH COUNCIL (ERC) (679660)
pubs.conference-name44th International Colloquium on Automata, Language and Programming (ICALP 2017)en
pubs.conference-start-date2017-07-10en


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Attribution 4.0 International
Except where otherwise noted, this item's licence is described as Attribution 4.0 International