אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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.