For overlay networks, the ability to recover from a variety of problems like membership changes or faults is a key element to preserve their functionality. In recent years, various self-stabilizing overlay networks have been proposed that have the advantage of being able to recover from any illegal state. However, the vast majority of these networks cannot give any guarantees on its functionality while the recovery process is going on. We are especially interested in searchability, i.e., the functionality that search messages for a specific identifier are answered successfully if a node with that identifier exists in the network. We investigate overlay networks that are not only self-stabilizing but that also ensure that monotonic searchability is maintained while the recovery process is going on, as long as there are no corrupted messages in the system. More precisely, once a search message from node u to another node v is successfully delivered, all future search messages from u to v succeed as well. Monotonic searchability was recently introduced in OPODIS 2015, in which the authors provide a solution for a simple line topology. We present the first universal approach to maintain monotonic searchability that is applicable to a wide range of topologies. As the base for our approach, we introduce a set of primitives for manipulating overlay networks that allows us to maintain searchability and show how existing protocols can be transformed to use theses primitives. We complement this result with a generic search protocol that together with the use of our primitives guarantees monotonic searchability. As an additional feature, searching existing nodes with the generic search protocol is as fast as searching a node with any other fixed routing protocol once the topology has stabilized. Keywords and phrases Monotonic Self-Stabilization, Topological Self-Stabilization, Overlay Networks This is the full version of a correspondent paper appearing in the DISC 2016 proceedings. * This work was partially supported by the German Research Foundation (DFG) within the Collaborative Research Center "On-The-Fly Computing" (SFB 901).  The Internet has opened up tremendous opportunities for people to interact and exchange information. Particularly popular ways to interact are peer-to-peer systems and social networks. For these systems it is very important that they are highly available. However, once these systems become large enough, changes and faults are not an exception but the rule. Therefore, mechanisms are needed that ensure that whenever problems occur, they are quickly repaired, and all parts of the system that are still functional should not be affected by the repair process. Protocols that are able to recover from arbitrary states are also known as self-stabilizing protocols. Since the seminal paper by Dijkstra in 1974 [6], self-stabilizing protocols have been investigated for many classical problems including leader election, consensus, matching, clock synchronization and token distribution problems. Recently, also various protocols for self-stabilizing overlay networks have been proposed (e.g., [9, 17, 12, 15] ). However, for all of these protocols it is only known that they eventually converge to the desired solution, but the convergence process is not necessarily monotonic. In other words, it is not ensured for two points in time t, t with t < t that the functionality of the topology at time t is better than the functionality at time t. In this paper, we continue our research started in [20] and investigate protocols for selfstabilizing overlay networks that guarantee the monotonic preservation of a characteristic that we call searchability, i.e., once a search message from node u to another node v is successfully delivered, all future search messages from u to v succeed as well. Searchability is a useful and natural characteristic for an overlay network since searching for other participants is one of the most common tasks in real-world networks. Moreover, a protocol that maintains monotonic searchability has the huge advantage that in every state, even if the self-stabilization process has not converged yet, the parts of the topology that are already in a legal state can be used for search requests. Instead of focusing on a specific topology, as done in [20] , we present an approach that is aimed at universality. As a base, we present a set of primitives for overlay network maintainance for which we prove that they enable monotonic searchability. On top of that, we give a generic search protocol that, together with a protocol that solely uses these primitives, guarantees monotonic searchability. Additionally, we show that existing self-stabilizing overlay network protocols can be transformed to use our primitives. To the best of our knowledge, we are the first to investigate monotonic searchability as an attempt to explore maintaining properties beyond the traditional "time and space" metrics during stabilization. We believe that the question of how to maintain monotonic searchability and similar properties during topological stabilization has a lot of potential for future research. We consider a distributed system consisting of a fixed set of nodes in which each node has a unique reference and a unique immutable numerical identifier (or short id). The system is controlled by a protocol that specifies the variables and actions that are available in each node. In addition to the protocol-based variables there is a system-based variable for each node called channel whose values are sets of messages. We denote the channel of a node u as u.Ch and it contains all incoming messages to u. Its message capacity is unbounded and messages never get lost. A node can add a message to u.Ch if it has a reference of u. There are two types of actions that a protocol can execute. The first type has the form of a standard procedure label ( parameters ) : command , where label is the unique name of that action, parameters specifies the parameter list of the action, and command specifies the statements to be executed when calling that action. Such actions can be called locally (which causes their immediate execution) and remotely. In fact, we assume that every message must be of the form label ( parameters ), where label specifies the action to be called in the receiving node and parameters contains the parameters to be passed to that action call. All other messages are ignored by nodes. The second type has the form label : guard −→ command , where label and command are defined as above and guard is a predicate over local variables. We call an action whose guard is simply true a timeout action. The system state is an assignment of values to every variable of each node and messages to each channel. An action in some node u is enabled in some system state if its guard evaluates to true, or if there is a message in u.Ch requesting to call it. In the latter case, when the corresponding action is executed, the message is processed (in which case it is removed from u.Ch). An action is disabled otherwise. Receiving and processing a message is considered as an atomic step. A computation is an infinite fair sequence of system states such that for each state S i , the next state S i+1 is obtained by executing an action that is enabled in S i . This disallows the overlap of action execution, i.e., action execution is atomic. We assume weakly fair action execution and fair message receipt. Weakly fair action execution means that if an action is enabled in all but finitely many states of a computation, then this action is executed infinitely often. Note that a timeout action of a node is executed infinitely often. Fair message receipt means that if a computation contains a state in which there is a message in a channel of a node that enables an action in that node, then that action is eventually executed with the parameters of that message, i.e., the message is eventually processed. Besides these fairness assumptions, we place no bounds on message propagation delay or relative nodes execution speeds, i.e., we allow fully asynchronous computations and non-FIFO message delivery. A computation suffix is a sequence of computation states past a particular state of this computation. In other words, the suffix of the computation is obtained by removing the initial state and finitely many subsequent states. Note that a computation suffix is also a computation. We say a state S is reachable from a state S if starting in S there is a sequence of action executions such that we end up in state S . We use the notion S < S as a shorthand to indicate that the state S happened chronologically before S . We consider protocols that do not manipulate the internals of node references. Specifically, a protocol is compare-store-send if the only operations that it executes on node references is comparing them, storing them in local memory and sending them in a message. In a compare-store-send protocol, a node may learn a new reference of a node only by receiving it in a message. A compare-store-send protocol cannot create new references. It can only operate on the references given to it. The overlay network of a set of nodes is determined by their knowledge of each other. We say that there is a (directed) edge from a to b, denoted by (a, b), if node a stores a reference of b in its local memory or has a message in a.Ch carrying the reference of b. In the former case, the edge is called explicit, and in the latter case, the edge is called implicit. Messages can only be sent via explicit edges. Note that message receipt converts an implicit edge to an explicit edge since the message is in the local memory of a node while it is processed. With N G we denote the directed network (multi-)graph given by the explicit and implicit 4 Towards a Universal Approach for Monotonic Searchability edges. EN G is the subgraph of N G induced by only the explicit edges. A weakly connected component of a directed graph G is a subgraph of G of maximum size so that for any two nodes u and v in that subgraph there is a (not necessarily directed) path from u to v. Two nodes that are not in the same weakly connected component are disconnected. We assume that the positions of the processes in the topology are encapsulated in their identifier and that there is a distance measure which is based on the identifiers of the processes and which can be checked locally. That is, for a given identifier ID, each node u can decide for each neighbor v whether v is closer to the node w with id(w) = ID if such a node exists (we also say that id(v) is closer to ID than id(u) or dist(id(v), ID) < dist(id(u), ID) ). For a node u, we define R(u, ID) as the set containing u and all processes v for which there is a path Q from u to v via explicit edges such that for each edge (a, b) that is traversed in Q it holds that dist(id(b), ID) < dist(id(a), ID) . Furthermore, for a set U , we define R(U, ID) := u∈U R (u, ID). In this paper we are particularly concerned with search requests, i.e., Search(v, destID) messages that are routed along EN G according to a given search protocol, where v is the sender of the message and destID is the identifier of a node we are looking for. We assume that Search() requests are initiated locally by an (possibly user controlled) application operating on top of the network. Note that destID does not need to be an id of an existing node w, since it is also possible that we are searching for a node that is not in the system. If a Search(v, destID) message reaches a node w with id(w) = destID, the search request succeeds; if the message reaches some node u with id(u) = destID and cannot be forwarded anymore according to the given search protocol, the search request fails. A protocol is self-stabilizing if it satisfies the following two properties as long as no transient faults occur. Convergence: starting from an arbitrary system state, the protocol is guaranteed to arrive at a legitimate state. Closure: starting from a legitimate state the protocol remains in legitimate states thereafter. A self-stabilizing protocol is thus able to recover from transient faults regardless of their nature. Moreover, a self-stabilizing protocol does not have to be initialized as it eventually starts to behave correctly regardless of its initial state. In topological self-stabilization we allow self-stabilizing protocols to perform changes to the overlay network N G. A legitimate state may then include a particular graph topology or a family of graph topologies. We are interested in self-stabilizing protocols that stabilize to static topologies, i.e., in every computation of the protocol that starts from a legitimate state, EN G stays the same, as long as the node set stays the same. In this paper we are not focusing on building a self-stabilizing protocol for a particular topology. Instead we are interested in providing a reliable protocol for searching in a wide range of topologies that fulfill certain requirements. Traditionally, search protocols for a given topology were only required to deliver the search messages reliably once a legitimate state has been reached. However, it is not possible to determine when a legitimate state has been reached. Furthermore, searching reliably during the stabilization phase is much more involved. We say a self-stabilizing protocol satisfies monotonic searchability according to some search protocol R if it holds for any pair of nodes v, w that once a Search(v, id(w)) request (that is routed according to R) initiated at time t succeeds, any Search(v, id(w)) request initiated at a time t > t will succeed. We do not mention R if it is clear from the context. A protocol is said to satisfy non-trivial monotonic searchability if (i) it satisfies C. Scheideler and A. Setzer and T. Strothmann 5 monotonic searchability and (ii) every computation of the protocol contains a suffix such that for each pair of nodes v, w, Search(v, id(w)) requests will succeed if there is a path from v to w in the target topology. Throughout the paper we will only investigate non-trivial monotonic searchability. Consequently, whenever we use the term monotonic searchability in the following, we implicitly refer to non-trivial monotonic searchability. A message invariant is a predicate of the following form: If there is a message m in the incoming channel of a node, then a logical predicate P must hold. A protocol may specify one or more message invariants. An arbitrary message m in a system is called corrupted if the existence of m violates one or multiple message invariants. A state S is called admissible if there are no corrupted messages in S. We say a (self-stabilizing) protocol admissibly satisfies a predicate P if the following two conditions hold: (i) the predicate is satisfied in all computation suffixes of the protocol that start from admissible states, and (ii) every computation of the protocol contains at least one admissible state. A protocol unconditionally satisfies a predicate if it satisfies this predicate starting from any state. The following was proven in [20]: Consequently, to prove monotonic searchability for a protocol (according to a given search protocol R) it is sufficient to show that: (i) in every computation of the protocol that starts from an admissible state, every state is admissible, (ii) in every computation of the protocol there is an admissible state, and (iii) the protocol satisfies monotonic searchability according to R in every computation that starts from an admissible state. Note that we have not defined any invariants yet and it is possible to pick invariants such that the set of admissible states equals the set of legitimate states, in which the problem becomes trivial. However, for the invariants we provide, any initial topology can be an admissible state. In particular, as long as no corrupt messages are initially in the system, our protocols satisfy monotonic searchability throughout the computation. We will show that a broad class of existing self-stabilizing protocols can be transformed to satisfy monotonic searchability. More specifically, we will consider protocols that fulfill the mdl property, i.e., for any action a of the protocol it holds that (i) a node u executing action a will always keep a reference of another node v in its local memory if an edge (u, v) is part of the final topology, and (ii) if a node u executing action a in state S decides not to keep a reference of another node v in its local memory, every other action of the protocol executed by u in a subsequent state will decide to not keep the reference of v, and (iii) a node u executing action a decides deterministically and solely based on its local memory whether to send and where to send the reference of v, (iv) in every legitimate state, for every reference of a node v contained in a message m in the channel of a node u (i.e., for any implicit edge (u, v)), there are fixed cycle-free paths (u = u 1 , u 2 , . . . , u k ) such that u i sends the reference of v to u i+1 , and u k has an explicit edge (u k , v) (note that there is only one path if the reference is never duplicated), i.e., the reference of v is forwarded along fixed paths until it finally fuses with an existing reference, and (v) any stable edge that may be traversed by the search protocol and any implicit edge that results from a delegation of an explicit edge that may have been traversed by the search protocol, is only delegated to a node whose distance (in the underlying distance metric) is closer to the target than the corrent node. Informally speaking, the first two properties imply that the protocol monotonically converges to its desired topology, since edges of the topology are always kept and edges that are not part of the topology are obviated over time. The last property implies that in legitimate states, all implicit edges will eventually merge with explicit edges. Note that the mdl property is 6 Towards a Universal Approach for Monotonic Searchability generally not a severe restriction. Most existing protocols that stabilize to static topologies naturally fulfill this property (see Section 6). In addition to the mdl property and the assumption that the final topology is static, we have one more condition on the topologies and their distance measures. The generic search protocol we will use to achieve monotonic searchability assumes that in the target topology for every pair of nodes u, v within the same connected component, there is a path of explicit edges from u to v with the property that each edge on the path strictly decreases the distance to v (i.e., for each edge (a, b) that is traversed in the path, dist (id(b), id(v) Note that many topologies naturally fulfill this property (in particular, whenever the distance is defined as the number of nodes on a shortest path). To the best of our knowledge, we are the first to solve the problem of searching reliably during the stabilization phase in self-stabilizing topologies. Although routing with a low dilation is a major motivation behind the use of overlay topologies, prior to this work, one could not rely on the routing paths in such topologies 1 : In previous approaches, it can happen that a node u is able to send a message to a node v, while it is unable to do so in a later state, only because the system has not stabilized yet (which is not locally detectable by the nodes). In our solution, once a search message from a node u has successfully arrived at a node v, every further search message from u to v will also arrive at its destination, regardless of whether the system has fully stabilized or not. We present a universal set of primitives for manipulating edges that protocols should use and a simple generic search protocol, which together satisfy monotonic searchability. Moreover, we provide a general description of how a broad class of self-stabilizing protocols for overlay networks can be transformed such that they use these primitives, thus satisfying monotonic searchability afterwards. Our results of Section 3 may be of independent interest, where we reinvestigate the fundamental primitives for manipulating edges introduced in [16] and strengthen the results concerning the universality of these primitives. The paper is organized as follows: We give a short overview of related work in Section 2. In Section 3, we describe primitives for manipulating edges introduced in [16] that are the base for our new primitives for searchability. In Section 4, we describe these new primitives that one should use in a protocol to enable monotonic searchability and show that conventional protocols for the self-stabilization of a topology can be transformed into ones using the new primitives. In Section 5, we present a generic search protocol according to which such protocols satisfy monotonic searchability and prove its correctness. In Section 6, we give examples on how to apply our results to existing topologies, namely the list and the SKIP + graph. A conclusion and outlook (Section 7) mark the end of the paper.  The idea of self-stabilization in distributed computing was introduced in a classical paper by E.W. Dijkstra in 1974 [6], in which he investigated the problem of self-stabilization in a token ring. In order to recover certain network topologies from any weakly connected state, researchers started with simple line and ring networks (e.g., [21, 19, 10] ). Over the years more and more network topologies were considered, ranging from skip lists and skip graphs [17, 11] , to expanders [9], hypertrees and double-headed radix trees [8, 2] , and small-world graphs [15] . Also a universal algorithm for topological self-stabilization is known [3] . In the last 20 years many approaches have been investigated that focus on maintaining safety properties during convergence phase of self-stabilization, e.g. snap-stabilization [4, 5] , super-stabilization [7] , safe convergence [14] and self-stabilization with service guarantee [13] . A protocol is snap-stabilizing if it always behaves according to its specification independent of its initial configuration. Snap-stabilization has a user-centric safety property (whereas the other approaches are system-centric), i.e. it ensures that the answer to a properly initiated user request by the protocol is correct. Safe convergence ensures that (1) the system quickly converges to a safe configuration, and (2) the safety property stays satisfied during the stabilization under protocol actions. However, external disruptions are not handled in safe convergence. A super-stabilizing protocol guarantees that (1) starting from a legitimate configuration, a safety property is preserved after only one specific topology change, and (2) the safety property is maintained during recovering to a legitimate configuration assuming that no more topology change occurs during stabilization phase. Self-stabilization with service guarantee provides and maintains the safety property even before stabilization, unlike super-stabilization. Closest to our work is the notion of monotonic convergence by Yamauchi and Tixeuil [22] . A self-stabilizing protocol is monotonically converging if every change done by a node p makes the system approach a legitimate state and if every node changes its output only once. The authors investigate monotonically converging protocols for different classical distributed problems (e.g., leader election and vertex coloring) and focus on the amount of non-local information that is needed for them. Research on monotonic searchability was initiated in [20] , in which the authors proved that it is impossible to satisfy monotonic searchability if corrupted messages are present. In addition, they presented a self-stabilizing protocol for the line topology that is able to satisfy monotonic searchability.
Building on that research, the same authors presented a universal approach for maintaining monotonic searchability at DISC 2016 along with a generic routing protocol that can be applied to a wide range of topologies REF .
Towards a Universal Approach for Monotonic Searchability in Self-Stabilizing Overlay Networks
ArXiv
ArXiv
Computer Science