The question of "what can be computed locally?" lies at the heart of distributed computing in networks. As established in Naor and Stockmeyer's seminal paper (STOC 1993, Edsger W. Dijkstra Prize in Distributed Computing 2025), this question is undecidable, even for graph problems whose solutions can be checked locally. In this paper, we adopt a novel perspective on the question, by asking for which classes Π of problems, and for which classes G of graphs, all problems in Π can be solved efficiently in a distributed manner in all graphs of G. This paper focuses on two natural candidates for such an approach, namely the class of problems expressible in first-order logic (FO), because they possess an intrinsic form of locality thanks to Gaifman's theorem, and the class of graphs with bounded expansion, because they form a large class of graphs encompassing, e.g., planar, bounded-genus, bounded-treewidth, and bounded-degree graphs, as well as graphs excluding a fixed minor or topological minor, sparse Erdös--Rényi graphs (a.a.s.), and several network models such as stochastic block models for suitable parameter ranges.

We address the problem of Termination Detection (TD) in asynchronous networks. It is known that TD cannot be achieved in the context of self-stabilization, except in the specific case where the TD algorithm is snap-stabilizing, i.e., it always behaves according to its specification regardless of the initial configuration. In this paper, we propose a generic, deterministic, snap-stabilizing, silent algorithm that detects whether an observed terminating silent self-stabilizing algorithm, A, has converged to a configuration that satisfies an intended predicate. Our algorithm assumes that nodes know (an upper bound on) the network diameter D. However, it requires no underlying structure, nor specific topology (arbitrary network), and works in anonymous networks, i.e., our algorithm uses no kind of assumption allowing distinguishing one or more nodes. Furthermore, it works under the weakest scheduling assumptions a.k.a, the unfair daemon. Built over any asynchronous self-stabilizing underlying unison U, our solution adds only O(log D) bits per node. Since there exists no unison algorithm with better space complexity, the extra space of our solution is negligible w.r.t. the space complexity of the underlying unison algorithm. Our algorithm provides a positive answer in O(max (k, k’, D)) time units, where k and k’ are the stabilization time complexities of A and U, respectively.

Algorithms for mutual exclusion aim to isolate potentially concurrent accesses to the same shared resources. Motivated by distributed computing research on programmable matter and population protocols where interactions among entities are often assumed to be isolated, Daymude, Richa, and Scheideler (SAND`22) introduced a variant of the local mutual exclusion problem that applies to arbitrary dynamic networks: each node, on issuing a lock request, must acquire exclusive locks on itself and all its persistent neighbors, i.e., the neighbors that remain connected to it over the duration of the lock request. Assuming adversarial edge dynamics, semi-synchronous or asynchronous concurrency, and anonymous nodes communicating via message passing, their randomized algorithm achieves mutual exclusion (non-intersecting lock sets) and lockout freedom (eventual success with probability 1). However, they did not analyze their algorithm’s runtime. In this paper, we prove that any node will successfully lock itself and its persistent neighbors within 𝒪(nΔ³) open rounds of its lock request in expectation, where n is the number of nodes in the dynamic network, Δ is the maximum degree of the dynamic network, rounds are normalized to the execution time of the "slowest" node, and "closed" rounds when some persistent neighbors are already locked by another node are ignored (i.e., only "open" rounds are considered).

In the context of self-stabilization, a silent algorithm guarantees that the communication registers (a.k.a register) of every node do not change once the algorithm has stabilized. At the end of the 90’s, Dolev et al. [Acta Inf. '99] showed that, for finding the centers of a graph, for electing a leader, or for constructing a spanning tree, every silent deterministic algorithm must use a memory of Omega(log n) bits per register in n-node networks. Similarly, Korman et al. [Dist. Comp. '07] proved, using the notion of proof-labeling-scheme, that, for constructing a minimum-weight spanning tree (MST), every silent algorithm must use a memory of Omega(log^2n) bits per register. It follows that requiring the algorithm to be silent has a cost in terms of memory space, while, in the context of self-stabilization, where every node constantly checks the states of its neighbors, the silence property can be of limited practical interest. In fact, it is known that relaxing this requirement results in algorithms with smaller space-complexity. In this paper, we are aiming at measuring how much gain in terms of memory can be expected by using arbitrary deterministic self-stabilizing algorithms, not necessarily silent. To our knowledge, the only known lower bound on the memory requirement for deterministic general algorithms, also established at the end of the 90’s, is due to Beauquier et al. [PODC '99] who proved that registers of constant size are not sufficient for leader election algorithms. We improve this result by establishing the lower bound Omega(log log n) bits per register for deterministic self-stabilizing algorithms solving (Delta+1)-coloring, leader election or constructing a spanning tree in networks of maximum degree Delta.

We present the first self-stabilizing algorithm for leader election in arbitrary topologies whose space complexity is O(max{log Delta, log log n}) bits per node, where n is the network size and Delta its degree. This complexity is sub-logarithmic in n when Delta = n^o(1).

The minimum spanning tree (MST) construction is a classical problem in Distributed Computing for creating a globally minimized structure distributedly. Self-stabilization is versatile technique for forward recovery that permits to handle any kind of transient faults in a unified manner. The loop-free property provides interesting safety assurance in dynamic networks where edge-cost changes during operation of the protocol. We present a new self-stabilizing MST protocol that improves on previous known approaches in several ways. First, it makes fewer system hypotheses as the size of the network (or an upper bound on the size) need not be known to the participants. Secondly, it is loop-free in the sense that it guarantees that a spanning tree structure is always preserved while edge costs change dynamically and the protocol adjusts to a new MST. Finally, time complexity matches the best known results, while space complexity results show that this protocol is the most efficient to date.

Self-stabilizing algorithms are distributed algorithms supporting transient failures. Starting from any configuration, they allow the system to detect whether the actual configuration is legal, and, if not, they allow the system to eventually reach a legal configuration. In the context of network computing, it is known that, for every task, there is a self-stabilizing algorithm solving that task, with optimal space-complexity, but converging in an exponential number of rounds. On the other hand, it is also known that, for every task, there is a self-stabilizing algorithm solving that task in a linear number of rounds, but with large space-complexity. It is however not known whether for every task there exists a self-stabilizing algorithm that is simultaneously space-efficient and time-efficient. In this paper, we make a first attempt for answering the question of whether such an efficient algorithm exists for every task, by focussing on constrained spanning tree construction tasks. We present a general roadmap for the design of silent space-optimal self-stabilizing algorithms solving such tasks, converging in polynomially many rounds under the unfair scheduler. By applying our roadmap to the task of constructing minimum-weight spanning tree (MST), and to the task of constructing minimum-degree spanning tree (MDST), we provide algorithms that outperform previously known algorithms designed and optimized specifically for solving each of these two tasks.

The diameter of a network is one of the most fundamental network parameters. Being able to compute the diameter is an important problem in the analysis of large networks, and moreover this parameter has many important practical applications in real networks. As a consequence, it is natural to study this problem in a distributed system, and more specifically in a distributed system tolerant to transient faults. More specifically, we are interested in the problem to identify one of the centers of graph. Once done, we construct a minimum diameter spanning tree rooted in this centre. Of course, the challenging problem is to compute one centre of the graph. We present a uniform self-stabilizing algorithm for the minimum diameter spanning tree construction problem in the state model. Our protocol has several attractive features that makes it suitable for practical purposes. It is the first algorithm for this problem that operates under the unfair adversary (also called unfair daemon). In other words, no restriction is made on the distributed behaviour of the system. Consequently, it is the hardest adversary to deal with. Moreover, our algorithm needs only O(log n) bits of memory per process (where n is the number of processes), that improves the previous result by a factor n. These improvements are not achieved to the detriment of the convergence time, that stays reasonable with O(n2) rounds.

This paper focuses on compact deterministic self-stabilizing solutions for the leader election problem. Self-stabilization is a versatile approach to withstand any kind of transient failures. Leader election is a fundamental building block in distributed computing, enabling to distinguish a unique node, in order to, e.g., execute particular actions. When the protocol is required to be silent (i.e., when communication content remains fixed from some point in time during any execution), there exists a lower bound of Ω(log n) bits of memory per node participating to the leader election (where n denotes the number of nodes in the system). This lower bound holds even in rings.

This paper is dedicated to the connection, by a provider, of multiple groups of nodes spread over a network. The role of the provider is to interconnect the members of every group. For this purpose, it must distribute the available links of the network between the groups. The general aim then is to allocate these links in such a way that the communications latencies in the allocated structure are equivalent to the ones in the original (full) network for each group. We study two approaches constructing structures preserving the maximum latency (called the diameter). Unfortunately we show that the associated optimization graph problems are difficult (one cannot be approximated by a constant and the other is NP-complete). Due to these difficulties we relax the constraint on the diameter and propose to construct a unique tree connecting all the groups together. We give a heuristic to treat this problem and we propose several analytical results on its maximum and average latencies performance.

We propose a self-stabilizing algorithm for constructing a Minimum-Degree Spanning Tree (MDST) in undirected networks. Starting from an arbitrary state, our algorithm is guaranteed to converge to a legitimate state describing a spanning tree whose maximum node degree is at most Delta*+ 1, where Delta* is the minimum possible maximum degree of a spanning tree of the network. To the best of our knowledge our algorithm is the first self-stabilizing solution for the construction of a minimum-degree spanning tree in undirected graphs. The algorithm uses only local communications (nodes interact only with the neighbors at one hop distance). Moreover, the algorithm is designed to work in any asynchronous message passing network with reliable FIFO channels. Additionally, we use a fine grained atomicity model (i.e. the send/receive atomicity). The time complexity of our solution is O(mn2log n) where m is the number of edges and n is the number of nodes. The memory complexity is O(delta log n) in the send-receive atomicity model (delta is the maximal degree of the network).