Abstract: Distributed graph algorithms study how global computational tasks can be solved through purely local interactions between nodes of a network. In this seminar, we introduce the LOCAL model, a central framework for studying distributed computation, and explain how locality constraints shape the complexity of graph problems. Starting from classical symmetry-breaking tasks, we will also cover some fundamental result in the area, including Linial’s $O(\log^\star n)$-round algorithm for $\Delta^2$-coloring and the notion of locally checkable labeling problems (LCLs) introduced by Naor and Stockmeyer..
Il seminario organizzato dai dottorandi di Matematica e si svolgerà in presenza presso il Dipartimento di Matematica e Fisica, Lungotevere Dante 376, aula M3.
Link identifier #identifier__24354-1Sito Web
Link identifier #identifier__179219-2Immagine Completa
This post is also available in:
Link identifier #identifier__147826-5
Eng