---
_id: '13182'
abstract:
- lang: eng
text: "We consider congestion control in peer-to-peer distributed systems. \r\nThe
problem can be reduced to the following scenario: Consider a set $V$ of $n$ peers
(called \\emph{clients} in this paper) that want to send messages to a fixed common
peer (called \\emph{server} in this paper).\r\nWe assume that each client $v \\in
V$ sends a message with probability $p(v) \\in [0,1)$ and the server has a capacity
of $\\sigma \\in \\mathbb{N}$, i.e., it can recieve at most $\\sigma$ messages
per round and excess messages are dropped.\r\nThe server can modify these probabilities
when clients send messages.\r\nIdeally, we wish to converge to a state with $\\sum
p(v) = \\sigma$ and $p(v) = p(w)$ for all $v,w \\in V$.\t\r\n\r\nWe propose a
\\emph{loosely} self-stabilizing protocol with a slightly relaxed legitimate state.
\ \r\nOur protocol lets the system converge from \\emph{any} initial state to
a state where $\\sum p(v) \\in \\left[\\sigma \\pm \\epsilon\\right]$ and $|p(v)-p(w)|
\\in O(\\frac{1}{n})$. \r\nThis property is then maintained for $\\Omega(n^{\\mathfrak{c}})$
rounds in expectation.\r\nIn particular, the initial client probabilities and
server variables are not necessarily well-defined, i.e., they may have arbitrary
values.\r\n\r\nOur protocol uses only $O(W + \\log n)$ bits of memory where $W$
is length of node identifiers, making it very lightweight.\r\nFinally we state
a lower bound on the convergence time an see that our protocol performs asymptotically
optimal (up to some polylogarithmic factor).\r\n"
author:
- first_name: Michael
full_name: Feldmann, Michael
id: '23538'
last_name: Feldmann
- first_name: Thorsten
full_name: Götte, Thorsten
id: '34727'
last_name: Götte
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: 'Feldmann M, Götte T, Scheideler C. A Loosely Self-stabilizing Protocol for
Randomized Congestion Control with Logarithmic Memory. In: Proceedings of the
21st International Symposium on Stabilization, Safety, and Security of Distributed
Systems (SSS). Lecture Notes in Computer Science. Springer, Cham; 2019:149-164.
doi:https://doi.org/10.1007/978-3-030-34992-9_13'
apa: Feldmann, M., Götte, T., & Scheideler, C. (2019). A Loosely Self-stabilizing
Protocol for Randomized Congestion Control with Logarithmic Memory. In Proceedings
of the 21st International Symposium on Stabilization, Safety, and Security of
Distributed Systems (SSS) (pp. 149–164). Springer, Cham. https://doi.org/10.1007/978-3-030-34992-9_13
bibtex: '@inproceedings{Feldmann_Götte_Scheideler_2019, series={Lecture Notes in
Computer Science}, title={A Loosely Self-stabilizing Protocol for Randomized Congestion
Control with Logarithmic Memory}, DOI={https://doi.org/10.1007/978-3-030-34992-9_13},
booktitle={Proceedings of the 21st International Symposium on Stabilization, Safety,
and Security of Distributed Systems (SSS)}, publisher={Springer, Cham}, author={Feldmann,
Michael and Götte, Thorsten and Scheideler, Christian}, year={2019}, pages={149–164},
collection={Lecture Notes in Computer Science} }'
chicago: Feldmann, Michael, Thorsten Götte, and Christian Scheideler. “A Loosely
Self-Stabilizing Protocol for Randomized Congestion Control with Logarithmic Memory.”
In Proceedings of the 21st International Symposium on Stabilization, Safety,
and Security of Distributed Systems (SSS), 149–64. Lecture Notes in Computer
Science. Springer, Cham, 2019. https://doi.org/10.1007/978-3-030-34992-9_13.
ieee: M. Feldmann, T. Götte, and C. Scheideler, “A Loosely Self-stabilizing Protocol
for Randomized Congestion Control with Logarithmic Memory,” in Proceedings
of the 21st International Symposium on Stabilization, Safety, and Security of
Distributed Systems (SSS), 2019, pp. 149–164.
mla: Feldmann, Michael, et al. “A Loosely Self-Stabilizing Protocol for Randomized
Congestion Control with Logarithmic Memory.” Proceedings of the 21st International
Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS),
Springer, Cham, 2019, pp. 149–64, doi:https://doi.org/10.1007/978-3-030-34992-9_13.
short: 'M. Feldmann, T. Götte, C. Scheideler, in: Proceedings of the 21st International
Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS),
Springer, Cham, 2019, pp. 149–164.'
date_created: 2019-09-10T12:48:33Z
date_updated: 2022-01-06T06:51:30Z
ddc:
- '000'
department:
- _id: '79'
doi: https://doi.org/10.1007/978-3-030-34992-9_13
external_id:
arxiv:
- '1909.04544'
file:
- access_level: closed
content_type: application/pdf
creator: mfeldma2
date_created: 2019-09-11T11:20:16Z
date_updated: 2019-09-11T11:20:16Z
file_id: '13188'
file_name: main.pdf
file_size: 428908
relation: main_file
success: 1
file_date_updated: 2019-09-11T11:20:16Z
has_accepted_license: '1'
language:
- iso: eng
page: 149-164
project:
- _id: '2'
name: SFB 901 - Project Area A
- _id: '5'
name: SFB 901 - Subproject A1
- _id: '1'
name: SFB 901
publication: Proceedings of the 21st International Symposium on Stabilization, Safety,
and Security of Distributed Systems (SSS)
publisher: Springer, Cham
series_title: Lecture Notes in Computer Science
status: public
title: A Loosely Self-stabilizing Protocol for Randomized Congestion Control with
Logarithmic Memory
type: conference
user_id: '23538'
year: '2019'
...