TY - CONF
AB - 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).
AU - Feldmann, Michael
AU - GĂ¶tte, Thorsten
AU - Scheideler, Christian
ID - 13182
T2 - Proceedings of the 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)
TI - A Loosely Self-stabilizing Protocol for Randomized Congestion Control with Logarithmic Memory
ER -