[adyn-talks] ADYN seminar: 31.03.2025, 17:00 CET
Dear all, the DFG Research Unit ADYN invites you to their next online seminar session on Zoom: *Monday, March 31st, 17:00 CET*. Link: https://rwth.zoom-x.de/j/68837156442?pwd=H4OW7bUYYAMXSPiqvxXuEMuTTmk7VY.1 Meeting-ID: 688 3715 6442 Kenncode: 593098 The following talks will be given: (1) "Naively Sorting Evolving Data is Optimal and Robust" by George Giakkoupis (Inria Centre at Rennes University) (2) "Fast Self-Stabilizing Ranking" by Thorsten Götte (Hamburg University) Abstracts: (1) In the evolving sorting problem, introduced by Anagnostopoulos, Kumar, Mahdian and Upfal (2011), the true ranking changes while the sorting algorithm is processing the input. More precisely, each comparison operation of the algorithm is followed by a sequence of evolution steps, where an evolution step perturbs the true rank of a random item by a "small" random value. The goal is to maintain an ordering that remains close to the true ranking over time. I will present a very simple sorting algorithm, which samples a random pair of adjacent items in each step and swaps them if they are out of order. The algorithm achieves and maintains, with high probability, optimal total deviation, $O(n)$, and optimal maximum deviation, $O(log n)$, under very general model assumptions. G. Giakkoupis, M. Kiwi and D. Los. Naively sorting evolving data is optimal and robust. Proc. 65th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 2217-2242, 2024. (2) We present a silent, self-stabilizing ranking protocol for the population protocol model of distributed computing, where agents interact in randomly chosen pairs to solve a common task. We are given $n$ anonymous agents, and the goal is to assign each agent a unique rank in $\{1, \dots, n\}$. Given unique ranks, it is straightforward to select a designated leader. Thus, our protocol is a self-stabilizing leader election protocol as well. Ranking requires at least $n$ states per agent; hence, the goal is to minimize the additional number of states, called overhead states. The core of our protocol is a space-efficient but non-self-stabilizing ranking protocol that requires only $n + O(\log n)$ states. Our protocol stabilizes in $O(n^2\ log n)$ interactions w.h.p. and in expectation, using $n + O(\log^2 n)$ states in total. Our stabilization time is asymptotically optimal. In comparison to the currently best known ranking protocol by Burman et al. [PODC ‘21], which requires $n + \Omega(n)$ states, our result exponentially improves the number of overhead states. Please note that the following session will already take place one week later on April 7th. For more information on ADYN and the seminar series, visit our website using the link https://adyn.informatik.rwth-aachen.de/ . Best, Tim
Dear all, I was reminded of the time shift this Sunday. Hence, the session will start at 17:00 CEST (not CET) , i.e., 5pm German time. Best, Tim On 28/03/2025 10:05, Tim Koglin wrote:
Dear all,
the DFG Research Unit ADYN invites you to their next online seminar session on Zoom:
*Monday, March 31st, 17:00 CET*.
Link: https://rwth.zoom-x.de/j/68837156442?pwd=H4OW7bUYYAMXSPiqvxXuEMuTTmk7VY.1
Meeting-ID: 688 3715 6442
Kenncode: 593098
The following talks will be given:
(1) "Naively Sorting Evolving Data is Optimal and Robust" by George Giakkoupis (Inria Centre at Rennes University)
(2) "Fast Self-Stabilizing Ranking" by Thorsten Götte (Hamburg University)
Abstracts:
(1) In the evolving sorting problem, introduced by Anagnostopoulos, Kumar, Mahdian and Upfal (2011), the true ranking changes while the sorting algorithm is processing the input. More precisely, each comparison operation of the algorithm is followed by a sequence of evolution steps, where an evolution step perturbs the true rank of a random item by a "small" random value. The goal is to maintain an ordering that remains close to the true ranking over time. I will present a very simple sorting algorithm, which samples a random pair of adjacent items in each step and swaps them if they are out of order. The algorithm achieves and maintains, with high probability, optimal total deviation, $O(n)$, and optimal maximum deviation, $O(log n)$, under very general model assumptions.
G. Giakkoupis, M. Kiwi and D. Los. Naively sorting evolving data is optimal and robust. Proc. 65th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 2217-2242, 2024.
(2) We present a silent, self-stabilizing ranking protocol for the population protocol model of distributed computing, where agents interact in randomly chosen pairs to solve a common task. We are given $n$ anonymous agents, and the goal is to assign each agent a unique rank in $\{1, \dots, n\}$. Given unique ranks, it is straightforward to select a designated leader. Thus, our protocol is a self-stabilizing leader election protocol as well. Ranking requires at least $n$ states per agent; hence, the goal is to minimize the additional number of states, called overhead states. The core of our protocol is a space-efficient but non-self-stabilizing ranking protocol that requires only $n + O(\log n)$ states. Our protocol stabilizes in $O(n^2\ log n)$ interactions w.h.p. and in expectation, using $n + O(\log^2 n)$ states in total. Our stabilization time is asymptotically optimal. In comparison to the currently best known ranking protocol by Burman et al. [PODC ‘21], which requires $n + \Omega(n)$ states, our result exponentially improves the number of overhead states.
Please note that the following session will already take place one week later on April 7th.
For more information on ADYN and the seminar series, visit our website using the link https://adyn.informatik.rwth-aachen.de/ .
Best,
Tim
participants (1)
-
Tim Koglin