Search

We study network coordination problems, as captured by the setting of generalized network design (Emek et al., STOC 2018), in the face of uncertainty resulting from partial information that the network users hold regarding the actions of their peers. This uncertainty is formalized using Alon et al.'s Bayesian ignorance framework (TCS 2012). While the approach of Alon et al. is purely combinatorial, the current paper takes into account computational considerations: Our main technical contribution is the development of (strongly) polynomial time algorithms for local decision making in the face of Bayesian uncertainty., Comment: 25 pages, 0 figure. An extended abstract of this paper is to appear in the 27th Annual European Symposium on Algorithms (ESA 2019)

Developing self-stabilizing solutions is considered to be more challenging and complicated than developing classical solutions, where a proper initialization of the variables can be assumed. Hence, to ease the task of the developers, some automatic techniques have been proposed to design self-stabilizing algorithms. In this paper, we propose an automatic transformer for algorithms in an extended population protocol model . Population protocols is a model that was introduced recently for networks with a large number of resource-limited mobile agents. We use a variant of this model. First, we assume agents having characteristics (e.g., moving speed, communication radius) affecting their intercommunication “speed”, which is reflected by their cover times . Second, we assume the existence of a special agent with an unbounded memory, the base station . The automatic transformer takes as an input an algorithm solving a static problem (and meeting some additional rather natural requirements) and outputs a self-stabilizing algorithm for the same problem. The transformer is built using a re-execution approach (the technique consisting of executing an algorithm repeatedly in order to obtain its self-stabilizing version). We show that in the model we use, a transformer based on such an approach is impossible without the assumption of an unbounded memory agent.

This paper is intended more to ask questions than give answers. Specifically, we consider models for labeling schemes, and discuss issues regarding the number of labels consulted vs. the sizes of the labels.Recently, quite a few papers studied methods for representing network properties by assigning informative labels to the vertices of a network. Consider a graph function f on pairs of vertices (for example, f can be the distance function). In an f-labeling scheme, the labels are constructed in such a way so that given the labels of any two vertices u and v, one can compute the function f(u,v) (e.g. the graph distance between u and v) just by looking at these two labels. Some very involved lower bounds for the sizes of the labels were proven. Also, some highly sophisticated labeling schemes were developed to ensure short labels.In this paper, we demonstrate that such lower bounds are very sensitive to the number of vertices consulted. That is, we show several constructions of such labeling schemes that beat the lower bounds by large margins. Moreover, as opposed to the strong technical skills that were needed to develop the traditional labeling schemes, most of our schemes are almost trivial. The catch is that in our model, one needs to consult the labels of three vertices instead of two. That is, a query about vertices u and v can access also the label of some third vertex w (w is determined by the labels of u and v). More generally, we address the model in which a query about vertices u and v can access also the labels of c other vertices. We term our generalized model labeling schemes with queries.The main importance of this model is theoretical. Specifically, this paper may serve as a first step towards investigating different tradeoffs between the amount of labels consulted and the amount of information stored at each vertex. As we show, if all vertices can be consulted then the problem almost reduces to the corresponding sequential problem. On the other hand, consulting just the labels of u and v (or even just the label of u) reduces the problem to a purely distributed one. Therefore, in a sense, our model spans a range of intermediate notions between the sequential and the distributed settings.In addition to the theoretical interest, we also show cases that schemes constructed for our model can be translated to the traditional model or to the sequential model, thus, simplifying the construction for those models as well. For implementing query labeling schemes in a distributed environment directly, we point at a potential usage for some new paradigms that became common recently, such as P2P and overlay networks.

We consider a distributed version of the graph exploration and mapping problem where a mobile agent has to traverse the edges of an unlabelled (i.e., anonymous) graph and return to its starting point, building a map of the graph in the process. In our case, instead of a single agent, there are k identical (i.e., mutually indistinguishable) agents initially dispersed among the n nodes of the graph. The agents can communicate by writing to the small public bulletin boards available at each node. The objective is for each agent to build an identically labelled map of the graph; we call this the Labelled Map Construction problem. This problem is much more difficult than exploration by a single agent, because it involves achieving cooperation among multiple agents. In fact, this problem is deterministically unsolvable in some cases. We present deterministic algorithms that successfully and efficiently solve the problem under the condition that the values of n and k are co-prime with each other. We also show how the problem of Labelled Map Construction is related to other problems like leader election and rendezvous of agents.

We study the scenario where a transient batch of faults hits a minority of the nodes in a distributed system by corrupting their state. We concentrate on the basic persistent bit problem, where the system is required to maintain a 01 value in the face of transient failures by means of replication. We give an algorithm to stabilize the value to a correct state quickly; that is, denoting the unknown number of faulty nodes by f, our algorithm recovers the value of the bit at all nodes in O(f) time units for any f < n2, where n is the number of all nodes. Moreover, complete state quiescence occurs in O(diam) time units, where diam denotes the actual diameter of the network. This means that the value persists indefinitely so long as any f < n2 faults are followed by Ω(diam) fault-free time units. (Strict self-stabilization requires recovery forf ⩾ n2 as well.) We prove matching lower bounds on both the output stabilization time and the state quiescence time. Using our persistent bit algorithm, we present a transformer which takes a distributed non-reactive non-stabilizing protocol P, and produces a protocol P1 which solves the problem P solves, with the additional property that if a batch of faults changes the state of f < n2 of the nodes, then the output is recovered in O(f) time units, and the state stabilizes in O(diam) time units. Our upper and lower bounds are all proved in the synchronous network model.

A new paradigm for the design of self-stabilizing distributed algorithms, called local detection , is introduced. The essence of the paradigm is in defining a local condition based on the state of a processor and its immediate neighborhood such that the system is in a globally legal state if and only if the local condition is satisfied at all the nodes. In this work we also extend the model of self-stabilizing networks traditionally assuming memory failure to include the model of dynamic networks (assuming edge failures and recoveries). We apply the paradigm to the extended model which we call “dynamic self-stabilizing networks”. Without loss of generality, we present the results in the least restrictive shared memory model of read/write atomicity, to which end we construct basic information transfer primitives. Using local detection, we develop deterministic and randomized self-stabilizing algorithms that maintain a rooted spanning tree in a general network whose topology changes dynamically. The deterministic algorithm assumes unique identities while the randomized assumes an anonymous network. The algorithms use a constant number of memory words per edge in each node; and both the size of memory words and of messages is the number of bits necessary to represent a node identity (typically O (log n ) bits where n is the size of the network). These algorithms provide for the easy construction of self-stabilizing protocols for numerous tasks: reset, routing, topology-update and self-stabilization transformers that automatically self-stabilize existing protocols for which local detection conditions can be defined.