Seminario di Informatica Teorica

Venerdì 13 Ottobre 2023 alle ore 15.00, presso il Dipartimento di Matematica e Fisica (via della Vasca Navale, 84 - Aula B), nell'ambito dei seminari di Logica ed Informatica Teorica si terrà il seminario della dott.ssa Isabella Ziccardi (Università Bocconi) dal titolo "Distributed Self-Stabilizing MIS Algorithms".

Sarà possibile seguire l'evento anche sulla piattaforma Link identifier #identifier__34733-1Microsoft Teams.

Abstract:
I will discuss self-stabilizing distributed algorithms that find a Maximal Independent Set in an n-vertex graph. These algorithms share the feature of utilizing randomization to break symmetry. I will compare them based on the following parameters: the number of states used by each node, the knowledge of the graph required by each node, and their stabilization time.
The first three algorithms are obtained by reconsidering some existing algorithms and making them self-stabilizing by introducing additional states. The first algorithm gets along with three states, but each node must have knowledge of ∆, the maximum node degree. In the second algorithm, nodes only need to be aware of their degree, but each node v has O(∆(v)) states, where ∆(v) is the degree of v. The third algorithm also requires O(∆(v)) states for each node v, but it works in the restricted beeping communication model. All three algorithms stabilize in O(log n) rounds with high probability.
Lastly, I will talk about two algorithms that aim to create self-stabilizing algorithms with a constant number of states while requiring no knowledge of the underlying graph. The first algorithm is a natural process that, despite its simplicity, has received limited attention in the literature. It stabilizes in O(polylog(n)) rounds for specific graph families but may exhibit slower convergence time on general graphs. The final algorithm is a modification of this simple process, that tries to fix the particular situations that slow down the convergence.