Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Events

The Taub Faculty of Computer Science Events and Talks

TDC Seminar: Self-Stabilizing Algorithms in the Uniform Port Model
event speaker icon
Liam Brinker (Technion)
event date icon
Monday, 12.01.2026, 13:30
event location icon
Meyer 1061

We introduce a distributed computational model referred to as the \emph{uniform port} model.
An algorithm operating in this model is defined by means of local automata associated with the ports (a.k.a. half-edges) of the input graph.
The crux of the uniform port model is that the local automata are identical and admit a constant size description, making the model \emph{truly uniform}.
Moreover, since the new model explicitly supports the assignment of (input and) output labels to the graph's (half-)edges, it is much more expressive than existing fully uniform distributed computational models that are restricted to assignments of output labels to the graph's nodes.

The main technical contribution of this work is the design of efficient (i.e., with poly-logarithmic time complexity) self-stabilizing uniform port algorithms for various fundamental local symmetry breaking problems, including maximal matching, maximal independent set, and maximal edge and node $c$-coloring.
While efficient self-stabilizing algorithms for local symmetry breaking problems have been extensively studied in stronger computational models, our work is the first to demonstrate the existence of such algorithms in a truly uniform model.