--- _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' ...