A Loosely Self-stabilizing Protocol for Randomized Congestion Control with Logarithmic Memory

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 clients in this paper) that want to send messages to a fixed common peer (called 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 loosely self-stabilizing protocol with a slightly relaxed legimate state. Our protocol lets the system converge from any initial state to a state where $\sum p(v)\in [\sigma \pm ϵ]$ and $|p(v)-p(w)| \in O(\frac{1}{n})$\mathrm{.}Thispropertyisthenmaintainedfor$\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 identifers, 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).