A Loosely Self-stabilizing Protocol for Randomized Congestion Control with Logarithmic Memory
Feldmann, Michael
Götte, Thorsten
Scheideler, Christian
ddc:000
We consider congestion control in peer-to-peer distributed systems.
The 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).
We 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.
The server can modify these probabilities when clients send messages.
Ideally, we wish to converge to a state with $\sum p(v) = \sigma$ and $p(v) = p(w)$ for all $v,w \in V$.
We propose a \emph{loosely} self-stabilizing protocol with a slightly relaxed legitimate state.
Our 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})$.
This property is then maintained for $\Omega(n^{\mathfrak{c}})$ rounds in expectation.
In particular, the initial client probabilities and server variables are not necessarily well-defined, i.e., they may have arbitrary values.
Our protocol uses only $O(W + \log n)$ bits of memory where $W$ is length of node identifiers, making it very lightweight.
Finally we state a lower bound on the convergence time an see that our protocol performs asymptotically optimal (up to some polylogarithmic factor).
Springer, Cham
2019
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://ris.uni-paderborn.de/record/13182
Feldmann M, Götte T, Scheideler C. A Loosely Self-stabilizing Protocol for Randomized Congestion Control with Logarithmic Memory. In: <i>Proceedings of the 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>. Lecture Notes in Computer Science. Springer, Cham; 2019:149-164. doi:<a href="https://doi.org/10.1007/978-3-030-34992-9_13">https://doi.org/10.1007/978-3-030-34992-9_13</a>
eng
info:eu-repo/semantics/altIdentifier/doi/https://doi.org/10.1007/978-3-030-34992-9_13
info:eu-repo/semantics/altIdentifier/arxiv/1909.04544
info:eu-repo/semantics/closedAccess