(Almost) Perfect Discrete Iterative Load Balancing Article Swipe

PDF

Petra Berenbrink , Robert Elsässer⋆ , Tom Friedetzky , Hamed Hosseinpour , Dominik Kaaser , Peter Kling , Thomas Sauerwald ·

YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2510.15473

We consider discrete, iterative load balancing via matchings on arbitrary graphs. Initially each node holds a certain number of tokens, defining the load of the node, and the objective is to redistribute the tokens such that eventually each node has approximately the same number of tokens. We present results for a general class of simple local balancing schemes where the tokens are balanced via matchings. In each round the process averages the tokens of any two matched nodes. If the sum of their tokens is odd, the node to receive the one excess token is selected at random. Our class covers three popular models: in the matching model a new matching is generated randomly in each round, in the balancing circuit model a fixed sequence of matchings is applied periodically, and in the asynchronous model the load is balanced over a randomly chosen edge. We measure the quality of a load vector by its discrepancy, defined as the difference between the maximum and minimum load across all nodes. As our main result we show that with high probability our discrete balancing scheme reaches a discrepancy of $3$ in a number of rounds which asymptotically matches the spectral bound for continuous load balancing with fractional load. This result improves and tightens a long line of previous works, by not only achieving a small constant discrepancy (instead of a non-explicit, large constant) but also holding for arbitrary instead of regular graphs. The result also demonstrates that in the general model we consider, discrete load balancing is no harder than continuous load balancing.

Related Topics

The Perfect Couple (Tv Series)

The Perfect Storm (Film)

List Of Major League Baseball Perfect Games

Perfect Number

Pitch Perfect 3

It's Almost Dry

Concepts

No concepts available.

Metadata

Type: preprint
Landing Page: http://arxiv.org/abs/2510.15473
PDF: https://arxiv.org/pdf/2510.15473
OA Status: green
OpenAlex ID: https://openalex.org/W4415881539

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4415881539

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2510.15473

Digital Object Identifier
Title: (Almost) Perfect Discrete Iterative Load Balancing

Work title
Type: preprint

OpenAlex work type
Publication year: 2025

Year of publication
Publication date: 2025-10-17

Full publication date if available
Authors: Petra Berenbrink, Robert Elsässer⋆, Tom Friedetzky, Hamed Hosseinpour, Dominik Kaaser, Peter Kling, Thomas Sauerwald

List of authors in order
Landing page: https://arxiv.org/abs/2510.15473

Publisher landing page
PDF URL: https://arxiv.org/pdf/2510.15473

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2510.15473

Direct OA link when available
Cited by: 0

Total citation count in OpenAlex

Full payload

id	https://openalex.org/W4415881539
doi	https://doi.org/10.48550/arxiv.2510.15473
ids.doi	https://doi.org/10.48550/arxiv.2510.15473
ids.openalex	https://openalex.org/W4415881539
fwci
type	preprint
title	(Almost) Perfect Discrete Iterative Load Balancing
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
is_xpac	False
apc_list
apc_paid
language
locations[0].id	pmh:oai:arXiv.org:2510.15473
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2510.15473
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2510.15473
locations[1].id	doi:10.48550/arxiv.2510.15473
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license	cc-by
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id	https://openalex.org/licenses/cc-by
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2510.15473
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5072910141
authorships[0].author.orcid	https://orcid.org/0000-0002-6930-3259
authorships[0].author.display_name	Petra Berenbrink
authorships[0].author_position	first
authorships[0].raw_author_name	Berenbrink, Petra
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5061445188
authorships[1].author.orcid
authorships[1].author.display_name	Robert Elsässer⋆
authorships[1].author_position	middle
authorships[1].raw_author_name	Elsässer, Robert
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5011308108
authorships[2].author.orcid	https://orcid.org/0000-0002-1299-5514
authorships[2].author.display_name	Tom Friedetzky
authorships[2].author_position	middle
authorships[2].raw_author_name	Friedetzky, Tom
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5090699776
authorships[3].author.orcid
authorships[3].author.display_name	Hamed Hosseinpour
authorships[3].author_position	middle
authorships[3].raw_author_name	Hosseinpour, Hamed
authorships[3].is_corresponding	False
authorships[4].author.id	https://openalex.org/A5085356058
authorships[4].author.orcid	https://orcid.org/0000-0002-2083-7145
authorships[4].author.display_name	Dominik Kaaser
authorships[4].author_position	middle
authorships[4].raw_author_name	Kaaser, Dominik
authorships[4].is_corresponding	False
authorships[5].author.id	https://openalex.org/A5007675663
authorships[5].author.orcid	https://orcid.org/0000-0003-0000-8689
authorships[5].author.display_name	Peter Kling
authorships[5].author_position	middle
authorships[5].raw_author_name	Kling, Peter
authorships[5].is_corresponding	False
authorships[6].author.id	https://openalex.org/A5017390373
authorships[6].author.orcid	https://orcid.org/0000-0002-0882-283X
authorships[6].author.display_name	Thomas Sauerwald
authorships[6].author_position	last
authorships[6].raw_author_name	Sauerwald, Thomas
authorships[6].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2510.15473
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-21T00:00:00
display_name	(Almost) Perfect Discrete Iterative Load Balancing
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2510.15473
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2510.15473
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2510.15473
primary_location.id	pmh:oai:arXiv.org:2510.15473
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2510.15473
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2510.15473
publication_date	2025-10-17
publication_year	2025
referenced_works_count	0
abstract_inverted_index.a	15, 50, 108, 122, 140, 149, 183, 188, 210, 220, 226
abstract_inverted_index.As	168
abstract_inverted_index.If	78
abstract_inverted_index.In	65
abstract_inverted_index.We	0, 46, 144
abstract_inverted_index.as	156
abstract_inverted_index.at	96
abstract_inverted_index.by	152, 216
abstract_inverted_index.in	104, 114, 117, 131, 187, 244
abstract_inverted_index.is	29, 84, 94, 111, 127, 137, 253
abstract_inverted_index.no	254
abstract_inverted_index.of	18, 23, 44, 53, 73, 81, 125, 148, 185, 190, 213, 225, 236
abstract_inverted_index.on	8
abstract_inverted_index.to	30, 88
abstract_inverted_index.we	172, 248
abstract_inverted_index.$3$	186
abstract_inverted_index.Our	98
abstract_inverted_index.The	239
abstract_inverted_index.all	166
abstract_inverted_index.and	26, 130, 162, 208
abstract_inverted_index.any	74
abstract_inverted_index.are	61
abstract_inverted_index.but	230
abstract_inverted_index.for	49, 198, 233
abstract_inverted_index.has	39
abstract_inverted_index.its	153
abstract_inverted_index.new	109
abstract_inverted_index.not	217
abstract_inverted_index.one	91
abstract_inverted_index.our	169, 178
abstract_inverted_index.sum	80
abstract_inverted_index.the	21, 24, 27, 32, 41, 59, 68, 71, 79, 86, 90, 105, 118, 132, 135, 146, 157, 160, 195, 245
abstract_inverted_index.two	75
abstract_inverted_index.via	6, 63
abstract_inverted_index.This	205
abstract_inverted_index.also	231, 241
abstract_inverted_index.each	12, 37, 66, 115
abstract_inverted_index.high	176
abstract_inverted_index.line	212
abstract_inverted_index.load	4, 22, 136, 150, 164, 200, 251, 258
abstract_inverted_index.long	211
abstract_inverted_index.main	170
abstract_inverted_index.node	13, 38, 87
abstract_inverted_index.odd,	85
abstract_inverted_index.only	218
abstract_inverted_index.over	139
abstract_inverted_index.same	42
abstract_inverted_index.show	173
abstract_inverted_index.such	34
abstract_inverted_index.than	256
abstract_inverted_index.that	35, 174, 243
abstract_inverted_index.with	175, 202
abstract_inverted_index.bound	197
abstract_inverted_index.class	52, 99
abstract_inverted_index.edge.	143
abstract_inverted_index.fixed	123
abstract_inverted_index.holds	14
abstract_inverted_index.large	228
abstract_inverted_index.load.	204
abstract_inverted_index.local	55
abstract_inverted_index.model	107, 121, 134, 247
abstract_inverted_index.node,	25
abstract_inverted_index.round	67
abstract_inverted_index.small	221
abstract_inverted_index.their	82
abstract_inverted_index.three	101
abstract_inverted_index.token	93
abstract_inverted_index.where	58
abstract_inverted_index.which	192
abstract_inverted_index.across	165
abstract_inverted_index.chosen	142
abstract_inverted_index.covers	100
abstract_inverted_index.excess	92
abstract_inverted_index.harder	255
abstract_inverted_index.nodes.	77, 167
abstract_inverted_index.number	17, 43, 189
abstract_inverted_index.result	171, 206, 240
abstract_inverted_index.round,	116
abstract_inverted_index.rounds	191
abstract_inverted_index.scheme	181
abstract_inverted_index.simple	54
abstract_inverted_index.tokens	33, 60, 72, 83
abstract_inverted_index.vector	151
abstract_inverted_index.works,	215
abstract_inverted_index.applied	128
abstract_inverted_index.between	159
abstract_inverted_index.certain	16
abstract_inverted_index.circuit	120
abstract_inverted_index.defined	155
abstract_inverted_index.general	51, 246
abstract_inverted_index.graphs.	10, 238
abstract_inverted_index.holding	232
abstract_inverted_index.instead	235
abstract_inverted_index.matched	76
abstract_inverted_index.matches	194
abstract_inverted_index.maximum	161
abstract_inverted_index.measure	145
abstract_inverted_index.minimum	163
abstract_inverted_index.models:	103
abstract_inverted_index.popular	102
abstract_inverted_index.present	47
abstract_inverted_index.process	69
abstract_inverted_index.quality	147
abstract_inverted_index.random.	97
abstract_inverted_index.reaches	182
abstract_inverted_index.receive	89
abstract_inverted_index.regular	237
abstract_inverted_index.results	48
abstract_inverted_index.schemes	57
abstract_inverted_index.tokens,	19
abstract_inverted_index.tokens.	45
abstract_inverted_index.(instead	224
abstract_inverted_index.averages	70
abstract_inverted_index.balanced	62, 138
abstract_inverted_index.consider	1
abstract_inverted_index.constant	222
abstract_inverted_index.defining	20
abstract_inverted_index.discrete	179, 250
abstract_inverted_index.improves	207
abstract_inverted_index.matching	106, 110
abstract_inverted_index.previous	214
abstract_inverted_index.randomly	113, 141
abstract_inverted_index.selected	95
abstract_inverted_index.sequence	124
abstract_inverted_index.spectral	196
abstract_inverted_index.tightens	209
abstract_inverted_index.Initially	11
abstract_inverted_index.achieving	219
abstract_inverted_index.arbitrary	9, 234
abstract_inverted_index.balancing	5, 56, 119, 180, 201, 252
abstract_inverted_index.consider,	249
abstract_inverted_index.constant)	229
abstract_inverted_index.discrete,	2
abstract_inverted_index.generated	112
abstract_inverted_index.iterative	3
abstract_inverted_index.matchings	7, 126
abstract_inverted_index.objective	28
abstract_inverted_index.balancing.	259
abstract_inverted_index.continuous	199, 257
abstract_inverted_index.difference	158
abstract_inverted_index.eventually	36
abstract_inverted_index.fractional	203
abstract_inverted_index.matchings.	64
abstract_inverted_index.discrepancy	184, 223
abstract_inverted_index.probability	177
abstract_inverted_index.asynchronous	133
abstract_inverted_index.demonstrates	242
abstract_inverted_index.discrepancy,	154
abstract_inverted_index.redistribute	31
abstract_inverted_index.approximately	40
abstract_inverted_index.non-explicit,	227
abstract_inverted_index.periodically,	129
abstract_inverted_index.asymptotically	193
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	7
citation_normalized_percentile