{"ID":6267099,"CreatedAt":"2026-07-10T01:11:38.759438437Z","UpdatedAt":"2026-07-13T01:02:08.706470581Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.08244","arxiv_id":"2607.08244","title":"Self-Stabilizing Algorithms in the Uniform Port Model","abstract":"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 a single constant-size finite automaton is hosted by every port of every graph, 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 facilitates natural formulations of (half-)edge-labeling problems such as maximal matching and sinkless orientation, which are outside the expressivity scope of prior node-centric truly uniform distributed computational models. The main technical contribution of this paper is the design of efficient (i.e., with poly-logarithmic runtime) \\emph{self-stabilizing} uniform port algorithms, operating on general graphs, for various fundamental local symmetry breaking problems, including maximal independent set, maximal matching, sinkless orientation, and maximal node/edge $k$-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.","short_abstract":"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 a single constant-size finite automaton is...","url_abs":"https://arxiv.org/abs/2607.08244","url_pdf":"https://arxiv.org/pdf/2607.08244v1","authors":"[\"Liam Brinker\",\"Yuval Emek\",\"Oren Louidor\"]","published":"2026-07-09T08:44:14Z","proceeding":"cs.DC","tasks":"[\"cs.DC\"]","methods":"[]","has_code":false}