Tight & Simple Load Balancing Article Swipe

View

Petra Berenbrink , Tom Friedetzky , Dominik Kaaser , Peter Kling ·

YOU? · · 2019 · Open Access · · DOI: https://doi.org/10.1109/ipdps.2019.00080

We consider the following load balancing process for m tokens distributed arbitrarily among n nodes connected by a complete graph. In each time step a pair of nodes is selected uniformly at random. Let ℓ 1 and ℓ 2 be their respective number of tokens. The two nodes exchange tokens such that they have [(ℓ 1 +ℓ 2 )/ 2 ] and [(ℓ 1 +ℓ 2 )/ 2 ] tokens, respectively. We provide a simple analysis showing that this process reaches almost perfect balance within O(n log n + n log Δ) steps with high probability, where Δ is the maximal initial load difference between any two nodes. This bound is asymptotically tight.

Related Topics

Concepts

Computer science Combinatorics Algorithm Discrete mathematics Mathematics

Metadata

Type: article
Language: en
Landing Page: https://doi.org/10.1109/ipdps.2019.00080
OA Status: gold
Cited By: 10
References: 20
Related Works: 10
OpenAlex ID: https://openalex.org/W2971543661

All OpenAlex metadata

Raw OpenAlex JSON

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

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.1109/ipdps.2019.00080

Digital Object Identifier
Title: Tight & Simple Load Balancing

Work title
Type: article

OpenAlex work type
Language: en

Primary language
Publication year: 2019

Year of publication
Publication date: 2019-05-01

Full publication date if available
Authors: Petra Berenbrink, Tom Friedetzky, Dominik Kaaser, Peter Kling

List of authors in order
Landing page: https://doi.org/10.1109/ipdps.2019.00080

Publisher landing page
Open access: Yes

Whether a free full text is available
OA status: gold

Open access status per OpenAlex
OA URL: https://durham-repository.worktribe.com/output/1142413

Direct OA link when available
Concepts: Computer science, Combinatorics, Algorithm, Discrete mathematics, Mathematics

Top concepts (fields/topics) attached by OpenAlex
Cited by: 10

Total citation count in OpenAlex
Citations by year (recent): 2022: 1, 2021: 2, 2020: 5, 2019: 2

Per-year citation counts (last 5 years)
References (count): 20

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W2971543661
doi	https://doi.org/10.1109/ipdps.2019.00080
ids.doi	https://doi.org/10.1109/ipdps.2019.00080
ids.mag	2971543661
ids.openalex	https://openalex.org/W2971543661
fwci	1.94164719
type	article
title	Tight & Simple Load Balancing
biblio.issue
biblio.volume
biblio.last_page	726
biblio.first_page	718
topics[0].id	https://openalex.org/T10772
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9991000294685364
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1705
topics[0].subfield.display_name	Computer Networks and Communications
topics[0].display_name	Distributed systems and fault tolerance
topics[1].id	https://openalex.org/T10246
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9990000128746033
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1705
topics[1].subfield.display_name	Computer Networks and Communications
topics[1].display_name	Mobile Ad Hoc Networks
topics[2].id	https://openalex.org/T10720
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.996999979019165
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1703
topics[2].subfield.display_name	Computational Theory and Mathematics
topics[2].display_name	Complexity and Algorithms in Graphs
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C41008148
concepts[0].level	0
concepts[0].score	0.5041161775588989
concepts[0].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[0].display_name	Computer science
concepts[1].id	https://openalex.org/C114614502
concepts[1].level	1
concepts[1].score	0.4588592052459717
concepts[1].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[1].display_name	Combinatorics
concepts[2].id	https://openalex.org/C11413529
concepts[2].level	1
concepts[2].score	0.3707999289035797
concepts[2].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[2].display_name	Algorithm
concepts[3].id	https://openalex.org/C118615104
concepts[3].level	1
concepts[3].score	0.36055853962898254
concepts[3].wikidata	https://www.wikidata.org/wiki/Q121416
concepts[3].display_name	Discrete mathematics
concepts[4].id	https://openalex.org/C33923547
concepts[4].level	0
concepts[4].score	0.2440982460975647
concepts[4].wikidata	https://www.wikidata.org/wiki/Q395
concepts[4].display_name	Mathematics
keywords[0].id	https://openalex.org/keywords/computer-science
keywords[0].score	0.5041161775588989
keywords[0].display_name	Computer science
keywords[1].id	https://openalex.org/keywords/combinatorics
keywords[1].score	0.4588592052459717
keywords[1].display_name	Combinatorics
keywords[2].id	https://openalex.org/keywords/algorithm
keywords[2].score	0.3707999289035797
keywords[2].display_name	Algorithm
keywords[3].id	https://openalex.org/keywords/discrete-mathematics
keywords[3].score	0.36055853962898254
keywords[3].display_name	Discrete mathematics
keywords[4].id	https://openalex.org/keywords/mathematics
keywords[4].score	0.2440982460975647
keywords[4].display_name	Mathematics
language	en
locations[0].id	doi:10.1109/ipdps.2019.00080
locations[0].is_oa	False
locations[0].source
locations[0].license
locations[0].pdf_url
locations[0].version	publishedVersion
locations[0].raw_type	proceedings-article
locations[0].license_id
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
locations[0].landing_page_url	https://doi.org/10.1109/ipdps.2019.00080
locations[1].id	pmh:oai:dro.dur.ac.uk.OAI2:27810
locations[1].is_oa	False
locations[1].source.id	https://openalex.org/S4306400188
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	False
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	Durham Research Online (Durham University)
locations[1].source.host_organization	https://openalex.org/I190082696
locations[1].source.host_organization_name	Durham University
locations[1].source.host_organization_lineage	https://openalex.org/I190082696
locations[1].license
locations[1].pdf_url
locations[1].version	acceptedVersion
locations[1].raw_type	Book chapter
locations[1].license_id
locations[1].is_accepted	True
locations[1].is_published	False
locations[1].raw_source_name	(2019). 33rd IEEE International Parallel & Distributed Processing Symposium ; proceedings. : IEEE, pp. 718-726
locations[1].landing_page_url	http://dro.dur.ac.uk/27810/
locations[2].id	pmh:oai:durham-repository.worktribe.com:1142413
locations[2].is_oa	True
locations[2].source
locations[2].license	cc-by
locations[2].pdf_url
locations[2].version	submittedVersion
locations[2].raw_type	acceptedVersion
locations[2].license_id	https://openalex.org/licenses/cc-by
locations[2].is_accepted	False
locations[2].is_published	False
locations[2].raw_source_name
locations[2].landing_page_url	https://durham-repository.worktribe.com/output/1142413
indexed_in	crossref
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].countries	DE
authorships[0].affiliations[0].institution_ids	https://openalex.org/I159176309
authorships[0].affiliations[0].raw_affiliation_string	Universität Hamburg, Hamburg, Germany
authorships[0].institutions[0].id	https://openalex.org/I159176309
authorships[0].institutions[0].ror	https://ror.org/00g30e956
authorships[0].institutions[0].type	education
authorships[0].institutions[0].lineage	https://openalex.org/I159176309
authorships[0].institutions[0].country_code	DE
authorships[0].institutions[0].display_name	Universität Hamburg
authorships[0].author_position	first
authorships[0].raw_author_name	Petra Berenbrink
authorships[0].is_corresponding	False
authorships[0].raw_affiliation_strings	Universität Hamburg, Hamburg, Germany
authorships[1].author.id	https://openalex.org/A5011308108
authorships[1].author.orcid	https://orcid.org/0000-0002-1299-5514
authorships[1].author.display_name	Tom Friedetzky
authorships[1].countries	GB
authorships[1].affiliations[0].institution_ids	https://openalex.org/I190082696
authorships[1].affiliations[0].raw_affiliation_string	Durham University, Durham, U.K.
authorships[1].institutions[0].id	https://openalex.org/I190082696
authorships[1].institutions[0].ror	https://ror.org/01v29qb04
authorships[1].institutions[0].type	education
authorships[1].institutions[0].lineage	https://openalex.org/I190082696
authorships[1].institutions[0].country_code	GB
authorships[1].institutions[0].display_name	Durham University
authorships[1].author_position	middle
authorships[1].raw_author_name	Tom Friedetzky
authorships[1].is_corresponding	False
authorships[1].raw_affiliation_strings	Durham University, Durham, U.K.
authorships[2].author.id	https://openalex.org/A5085356058
authorships[2].author.orcid	https://orcid.org/0000-0002-2083-7145
authorships[2].author.display_name	Dominik Kaaser
authorships[2].countries	DE
authorships[2].affiliations[0].institution_ids	https://openalex.org/I159176309
authorships[2].affiliations[0].raw_affiliation_string	Universität Hamburg, Hamburg, Germany
authorships[2].institutions[0].id	https://openalex.org/I159176309
authorships[2].institutions[0].ror	https://ror.org/00g30e956
authorships[2].institutions[0].type	education
authorships[2].institutions[0].lineage	https://openalex.org/I159176309
authorships[2].institutions[0].country_code	DE
authorships[2].institutions[0].display_name	Universität Hamburg
authorships[2].author_position	middle
authorships[2].raw_author_name	Dominik Kaaser
authorships[2].is_corresponding	False
authorships[2].raw_affiliation_strings	Universität Hamburg, Hamburg, Germany
authorships[3].author.id	https://openalex.org/A5007675663
authorships[3].author.orcid	https://orcid.org/0000-0003-0000-8689
authorships[3].author.display_name	Peter Kling
authorships[3].countries	DE
authorships[3].affiliations[0].institution_ids	https://openalex.org/I159176309
authorships[3].affiliations[0].raw_affiliation_string	Universität Hamburg, Hamburg, Germany
authorships[3].institutions[0].id	https://openalex.org/I159176309
authorships[3].institutions[0].ror	https://ror.org/00g30e956
authorships[3].institutions[0].type	education
authorships[3].institutions[0].lineage	https://openalex.org/I159176309
authorships[3].institutions[0].country_code	DE
authorships[3].institutions[0].display_name	Universität Hamburg
authorships[3].author_position	last
authorships[3].raw_author_name	Peter Kling
authorships[3].is_corresponding	False
authorships[3].raw_affiliation_strings	Universität Hamburg, Hamburg, Germany
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://durham-repository.worktribe.com/output/1142413
open_access.oa_status	gold
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Tight & Simple Load Balancing
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T03:46:38.306776
primary_topic.id	https://openalex.org/T10772
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9991000294685364
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1705
primary_topic.subfield.display_name	Computer Networks and Communications
primary_topic.display_name	Distributed systems and fault tolerance
related_works	https://openalex.org/W4391375266, https://openalex.org/W2748952813, https://openalex.org/W2051487156, https://openalex.org/W2073681303, https://openalex.org/W2390279801, https://openalex.org/W2358668433, https://openalex.org/W4396701345, https://openalex.org/W2376932109, https://openalex.org/W2001405890, https://openalex.org/W4396696052
cited_by_count	10
counts_by_year[0].year	2022
counts_by_year[0].cited_by_count	1
counts_by_year[1].year	2021
counts_by_year[1].cited_by_count	2
counts_by_year[2].year	2020
counts_by_year[2].cited_by_count	5
counts_by_year[3].year	2019
counts_by_year[3].cited_by_count	2
locations_count	3
best_oa_location.id	pmh:oai:durham-repository.worktribe.com:1142413
best_oa_location.is_oa	True
best_oa_location.source
best_oa_location.license	cc-by
best_oa_location.pdf_url
best_oa_location.version	submittedVersion
best_oa_location.raw_type	acceptedVersion
best_oa_location.license_id	https://openalex.org/licenses/cc-by
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	https://durham-repository.worktribe.com/output/1142413
primary_location.id	doi:10.1109/ipdps.2019.00080
primary_location.is_oa	False
primary_location.source
primary_location.license
primary_location.pdf_url
primary_location.version	publishedVersion
primary_location.raw_type	proceedings-article
primary_location.license_id
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
primary_location.landing_page_url	https://doi.org/10.1109/ipdps.2019.00080
publication_date	2019-05-01
publication_year	2019
referenced_works	https://openalex.org/W2136388527, https://openalex.org/W6639110016, https://openalex.org/W2110100895, https://openalex.org/W2899702797, https://openalex.org/W2561178802, https://openalex.org/W2026337277, https://openalex.org/W1909387666, https://openalex.org/W2112749339, https://openalex.org/W2120196685, https://openalex.org/W2075553387, https://openalex.org/W1985451401, https://openalex.org/W2963374947, https://openalex.org/W2023434464, https://openalex.org/W1978335532, https://openalex.org/W2314313325, https://openalex.org/W2090026441, https://openalex.org/W2060084491, https://openalex.org/W1858709208, https://openalex.org/W4300094059, https://openalex.org/W1595409123
referenced_works_count	20
abstract_inverted_index.+	88
abstract_inverted_index.1	35, 55, 63
abstract_inverted_index.2	38, 57, 59, 65, 67
abstract_inverted_index.]	60, 68
abstract_inverted_index.a	17, 24, 73
abstract_inverted_index.m	8
abstract_inverted_index.n	13, 87, 89
abstract_inverted_index.)/	58, 66
abstract_inverted_index.In	20
abstract_inverted_index.We	0, 71
abstract_inverted_index.at	31
abstract_inverted_index.be	39
abstract_inverted_index.by	16
abstract_inverted_index.is	28, 98, 110
abstract_inverted_index.of	26, 43
abstract_inverted_index.Δ	97
abstract_inverted_index.Let	33
abstract_inverted_index.O(n	85
abstract_inverted_index.The	45
abstract_inverted_index.and	36, 61
abstract_inverted_index.any	105
abstract_inverted_index.for	7
abstract_inverted_index.log	86, 90
abstract_inverted_index.the	2, 99
abstract_inverted_index.two	46, 106
abstract_inverted_index.Δ)	91
abstract_inverted_index.ℓ	34, 37
abstract_inverted_index.+ℓ	56, 64
abstract_inverted_index.This	108
abstract_inverted_index.each	21
abstract_inverted_index.have	53
abstract_inverted_index.high	94
abstract_inverted_index.load	4, 102
abstract_inverted_index.pair	25
abstract_inverted_index.step	23
abstract_inverted_index.such	50
abstract_inverted_index.that	51, 77
abstract_inverted_index.they	52
abstract_inverted_index.this	78
abstract_inverted_index.time	22
abstract_inverted_index.with	93
abstract_inverted_index.[(ℓ	54, 62
abstract_inverted_index.among	12
abstract_inverted_index.bound	109
abstract_inverted_index.nodes	14, 27, 47
abstract_inverted_index.steps	92
abstract_inverted_index.their	40
abstract_inverted_index.where	96
abstract_inverted_index.almost	81
abstract_inverted_index.graph.	19
abstract_inverted_index.nodes.	107
abstract_inverted_index.number	42
abstract_inverted_index.simple	74
abstract_inverted_index.tight.	112
abstract_inverted_index.tokens	9, 49
abstract_inverted_index.within	84
abstract_inverted_index.balance	83
abstract_inverted_index.between	104
abstract_inverted_index.initial	101
abstract_inverted_index.maximal	100
abstract_inverted_index.perfect	82
abstract_inverted_index.process	6, 79
abstract_inverted_index.provide	72
abstract_inverted_index.random.	32
abstract_inverted_index.reaches	80
abstract_inverted_index.showing	76
abstract_inverted_index.tokens,	69
abstract_inverted_index.tokens.	44
abstract_inverted_index.analysis	75
abstract_inverted_index.complete	18
abstract_inverted_index.consider	1
abstract_inverted_index.exchange	48
abstract_inverted_index.selected	29
abstract_inverted_index.balancing	5
abstract_inverted_index.connected	15
abstract_inverted_index.following	3
abstract_inverted_index.uniformly	30
abstract_inverted_index.difference	103
abstract_inverted_index.respective	41
abstract_inverted_index.arbitrarily	11
abstract_inverted_index.distributed	10
abstract_inverted_index.probability,	95
abstract_inverted_index.respectively.	70
abstract_inverted_index.asymptotically	111
cited_by_percentile_year.max	98
cited_by_percentile_year.min	89
countries_distinct_count	2
institutions_distinct_count	4
citation_normalized_percentile.value	0.8664157
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	False