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
