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)

In a generalized network design (GND) problem, a set of resources are assigned to multiple communication requests. Each request contributes its weight to the resources it uses and the total load on a resource is then translated to the cost it incurs via a resource specific cost function. For example, a request may be to establish a virtual circuit, thus contributing to the load on each edge in the circuit. Motivated by energy efficiency applications, recently, there is a growing interest in GND using cost functions that exhibit (dis)economies of scale ((D)oS), namely, cost functions that appear subadditive for small loads and superadditive for larger loads. The current paper advances the existing literature on approximation algorithms for GND problems with (D)oS cost functions in various aspects: (1) we present a generic approximation framework that yields approximation results for a much wider family of requests in both directed and undirected graphs; (2) our framework allows for unrelated weights, thus providing the first non-trivial approximation for the problem of scheduling unrelated parallel machines with (D)oS cost functions; (3) our framework is fully combinatorial and runs in strongly polynomial time; (4) the family of (D)oS cost functions considered in the current paper is more general than the one considered in the existing literature, providing a more accurate abstraction for practical energy conservation scenarios; and (5) we obtain the first approximation ratio for GND with (D)oS cost functions that depends only on the parameters of the resources' technology and does not grow with the number of resources, the number of requests, or their weights. The design of our framework relies heavily on Roughgarden's smoothness toolbox (JACM 2015), thus demonstrating the possible usefulness of this toolbox in the area of approximation algorithms., Comment: 39 pages, 1 figure. An extended abstract of this paper is to appear in the 50th Annual ACM Symposium on the Theory of Computing (STOC 2018)

It was suggested that a programmable matter system (composed of multiple computationally weak mobile particles) should remain connected at all times since otherwise, reconnection is difficult and may be impossible. At the same time, it was not clear that allowing the system to disconnect carried a significant advantage in terms of time complexity. We demonstrate for a fundamental task, that of leader election, an algorithm where the system disconnects and then reconnects automatically in a non-trivial way (particles can move far away from their former neighbors and later reconnect to others). Moreover, the runtime of the temporarily disconnecting deterministic leader election algorithm is linear in the diameter. Hence, the disconnecting -- reconnecting algorithm is as fast as previous randomized algorithms. When comparing to previous deterministic algorithms, we note that some of the previous work assumed weaker schedulers. Still, the runtime of all the previous deterministic algorithms that did not assume special shapes of the particle system (shapes with no holes) was at least quadratic in $n$, where $n$ is the number of particles in the system. (Moreover, the new algorithm is even faster in some parameters than the deterministic algorithms that did assume special initial shapes.) Since leader election is an important module in algorithms for various other tasks, the presented algorithm can be useful for speeding up other algorithms under the assumption of a strong scheduler. This leaves open the question: "can a deterministic algorithm be as fast as the randomized ones also under weaker schedulers?", PODC 2021

A matching of a graph is a subset of edges no two of which share a common vertex, and a maximum matching is a matching of maximum cardinality. In a b-matching every vertex v has an associated bound \(b_v\), and a maximum b-matching is a maximum set of edges, such that every vertex v appears in at most \(b_v\) of them. We study an extension of this problem, termed Hierarchical b-Matching. In this extension, the vertices are arranged in a hierarchical manner. At the first level the vertices are partitioned into disjoint subsets, with a given bound for each subset. At the second level the set of these subsets is again partitioned into disjoint subsets, with a given bound for each subset, and so on. We seek for a maximum set of edges, that obey all bounds (that is, no vertex v participates in more than \(b_v\) edges, then all the vertices in one subset do not participate in more that subset’s bound of edges, and so on hierarchically). This is a sub-problem of the matroid matching problem which is \(\textsc {NP}\text {-hard}\) in general. It corresponds to the special case where the matroid is restricted to be laminar and the weights are unity. A pseudo-polynomial algorithm for the weighted laminar matroid matching problem is presented in [8]. We propose a polynomial-time algorithm for Hierarchical b-matching, i.e. the unweighted laminar matroid matching problem, and discuss how our techniques can possibly be generalized to the weighted case.

A new \emph{spanner} construction algorithm is presented, working under the \emph{LOCAL} model with unique edge IDs. Given an $n$-node communication graph, a spanner with a constant stretch and $O (n^{1 + \varepsilon})$ edges (for an arbitrarily small constant $\varepsilon > 0$) is constructed in a constant number of rounds sending $O (n^{1 + \varepsilon})$ messages whp. Consequently, we conclude that every $t$-round LOCAL algorithm can be transformed into an $O (t)$-round LOCAL algorithm that sends $O (t \cdot n^{1 + \varepsilon})$ messages whp. This improves upon all previous message-reduction schemes for LOCAL algorithms that incur a $\log^{\Omega (1)} n$ blow-up of the round complexity., Comment: Appeared at International Symposium on Distributed Computing (DISC) 2019

Electing a leader is a fundamental task in distributed computing. In its implicit version, only the leader must know who is the elected leader. This article focuses on studying the message and time complexity of randomized implicit leader election in synchronous distributed networks. Surprisingly, the most “obvious” complexity bounds have not been proven for randomized algorithms. In particular, the seemingly obvious lower bounds of Ω( m ) messages, where m is the number of edges in the network, and Ω( D ) time, where D is the network diameter, are nontrivial to show for randomized (Monte Carlo) algorithms. (Recent results, showing that even Ω( n ), where n is the number of nodes in the network, is not a lower bound on the messages in complete networks, make the above bounds somewhat less obvious). To the best of our knowledge, these basic lower bounds have not been established even for deterministic algorithms, except for the restricted case of comparison algorithms, where it was also required that nodes may not wake up spontaneously and that D and n were not known. We establish these fundamental lower bounds in this article for the general case, even for randomized Monte Carlo algorithms. Our lower bounds are universal in the sense that they hold for all universal algorithms (namely, algorithms that work for all graphs), apply to every D , m , and n , and hold even if D , m , and n are known, all the nodes wake up simultaneously, and the algorithms can make any use of node's identities. To show that these bounds are tight, we present an O ( m ) messages algorithm. An O ( D ) time leader election algorithm is known. A slight adaptation of our lower bound technique gives rise to an Ω( m ) message lower bound for randomized broadcast algorithms. An interesting fundamental problem is whether both upper bounds (messages and time) can be reached simultaneously in the randomized setting for all graphs. The answer is known to be negative in the deterministic setting. We answer this problem partially by presenting a randomized algorithm that matches both complexities in some cases. This already separates (for some cases) randomized algorithms from deterministic ones. As first steps towards the general case, we present several universal leader election algorithms with bounds that tradeoff messages versus time. We view our results as a step towards understanding the complexity of universal leader election in distributed networks.

This paper investigates the message complexity of distributed information spreading in adversarial dynamic networks. While distributed computations in dynamic networks have been studied intensively over the last years, almost all of the existing work solely focuses on the time complexity of distributed algorithms. In information spreading, the goal is to spread k tokens of information to every node on an n-node network. We consider the amortized (average) message complexity of spreading a token, assuming that the number of tokens is large. In a static network, this basic problem can be solved using (asymptotically optimal) O(n) amortized messages per token. Our focus is on token-forwarding algorithms, which do not manipulate tokens in any way other than storing, copying, and forwarding them. We present two sets of results depending on how nodes send messages to their neighbors: 1. Local broadcast: We show a tight lower bound of Ω(n^2) on the number of amortized local broadcasts, which is matched by the naive flooding algorithm. The lower bound holds for randomized algorithms against a strongly adaptive adversary. 2. Unicast: We study the message complexity as a function of the number of dynamic changes in the network. To facilitate this, we introduce adversary-competitive message complexity as a natural complexity measure for analyzing dynamic networks: The adversary pays a unit cost for every topological change and the message cost of an algorithm is determined as the actual number of messages sent minus the total cost of the adversary. Under this model, we give a deterministic algorithm that obtains an optimal amortized message complexity of O(n) if the number of tokens k is sufficiently large. We also present a randomized algorithm that achieves subquadratic amortized message complexity for much smaller k under an oblivious adversary.

This paper studies a new online problem, referred to as \emph{min-cost perfect matching with delays (MPMD)}, defined over a finite metric space (i.e., a complete graph with positive edge weights obeying the triangle inequality) $\mathcal{M}$ that is known to the algorithm in advance. Requests arrive in a continuous time online fashion at the points of $\mathcal{M}$ and should be served by matching them to each other. The algorithm is allowed to delay its request matching commitments, but this does not come for free: the total cost of the algorithm is the sum of metric distances between matched requests \emph{plus} the sum of times each request waited since it arrived until it was matched. A randomized online MPMD algorithm is presented whose competitive ratio is $O (\log^{2} n + \log \Delta)$, where $n$ is the number of points in $\mathcal{M}$ and $\Delta$ is its aspect ratio. The analysis is based on a machinery developed in the context of a new stochastic process that can be viewed as two interleaved Poisson processes; surprisingly, this new process captures precisely the behavior of our algorithm. A related problem in which the algorithm is allowed to clear any unmatched request at a fixed penalty is also addressed. It is suggested that the MPMD problem is merely the tip of the iceberg for a general framework of online problems with delayed service that captures many more natural problems., Comment: An extended abstract will appear in Proceedings of ACM STOC 2016

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.

We initiate the study of error confinement in distributed applications, where the goal is that only nodes that were directly hit by a fault may deviate from their correct external behavior, and only temporarily. The external behavior of all other nodes must remain impeccable, even though their internal state may be affected. Error confinement is impossible if an adversary is allowed to inflict arbitrary transient faults on the system, since the faults might completely wipe out input values. We introduce a new fault tolerance measure we call agility, which quantifies the strength of an algorithm that disseminate information, against state corrupting faults.We study the basic problem of broadcast, and propose algorithms that guarantee error confinement with optimal agility to within a constant factor, even in asynchronous networks when the topology is unknown. These algorithms can serve as building blocks in more general reactive systems. Previous results in exploring locality in reactive systems were not error confined, and relied on the assumption (not used in current paper) that the errors hitting each node are probabilistic, such that a faulty node itself, or its neighbor, can detect the node faulty.The main algorithm uses the novel core bootstrapping technique, that seems inherent for voting in reactive networks; its analysis leads to an interesting combinatorial problem. The technique and the analysis may be of independent interest

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.

Shared counters are among the most basic coordination structures in distributed computing. Known implementations of shared counters are either blocking, non-linearizable, or have a sequential bottleneck. We present the first counter algorithm that is both linearizable, non-blocking, and can provably achieve high throughput in k-synchronous executions—executions in which process speeds vary by at most a constant factor k. The algorithm is based on a novel variation of the software combining paradigm that we call bounded-wait combining (BWC). It can thus be used to obtain implementations, possessing the same properties, of any object that supports combinable operations, such as a stack or a queue. Unlike previous combining algorithms where processes may have to wait for each other indefinitely, in the BWC algorithm, a process only waits for other processes for a bounded period of time and then “takes destiny in its own hands”. In order to reason rigorously about the parallelism attainable by our algorithm, we define a novel metric for measuring the throughput of shared objects, which we believe is interesting in its own right. We use this metric to prove that our algorithm achieves throughput of Ω(N/ log N) in k-synchronous executions, where N is the number of processes that can participate in the algorithm. Our algorithm uses two tools that we believe may prove useful for obtaining highly parallel non-blocking implementation of additional objects. The first are “synchronous locks”, locks that are respected by processes only in k-synchronous executions and are disregarded otherwise; the second are “pseduo-transactions”—a weakening of regular transactions that allows higher parallelism.

In this article, we show that keeping track of history enables significant improvements in the communication complexity of dynamic network protocols. We present a communication optimal maintenance of a spanning tree in a dynamic network. The amortized (on the number of topological changes) message complexity is O ( V ), where V is the number of nodes in the network. The message size used by the algorithm is O (log |ID|) where |ID| is the size of the name space of the nodes. Typically, log |ID| = O (log V ). Previous algorithms that adapt to dynamic networks involved Ω ( E ) messages per topological change—inherently paying for re-computation of the tree from scratch. Spanning trees are essential components in many distributed algorithms. Some examples include broadcast (dissemination of messages to all network nodes), multicast, reset (general adaptation of static algorithms to dynamic networks), routing, termination detection , and more. Thus, our efficient maintenance of a spanning tree implies the improvement of algorithms for these tasks. Our results are obtained using a novel technique to save communication. A node uses information received in the past in order to deduce present information from the fact that certain messages were NOT sent by the node's neighbor. This technique is one of our main contributions.

" How well connected is the network? " This is one of the most fundamental questions one would ask when facing the challenge of designing a communication network. Three major notions of connectivity have been considered in the literature, but in the context of traditional (single-layer) networks, they turn out to be equivalent. This paper introduces a model for studying the three notions of connectivity in multi-layer networks. Using this model, it is easy to demonstrate that in multi-layer networks the three notions may differ dramatically. Unfortunately, in contrast to the single-layer case, where the values of the three connectivity notions can be computed efficiently, it has been recently shown in the context of WDM networks (results that can be easily translated to our model) that the values of two of these notions of connectivity are hard to compute or even approximate in multi-layer networks. The current paper shed some positive light into the multi-layer connectivity topic: we show that the value of the third connectivity notion can be computed in polynomial time and develop an approximation for the construction of well connected overlay networks., Comment: Structural Information and Communication Complexity - 19th International Colloquium, 2012, Jun 2012, Reykjavik, Iceland. 2015

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.

A synchronizer with a phase counter (sometimes called asynchronous phase clock) is an asynchronous distributed algorithm, where each node maintains a local "pulse counter" that simulates the global clock in a synchronous network. In this paper, we present a time-optimal self-stabilizing scheme for such a synchronizer, assuming unbounded counters. We give a simple rule by which each node can compute its pulse number as a function of its neighbors' pulse numbers. We also show that some of the popular correction functions for phase clock synchronization are not self-stabilizing in asynchronous networks. Using our rule, the counters stabilize in time bounded by the diameter of the network, without invoking global operations. We argue that the use of unbounded counters can be justified by the availability of memory for counters that are large enough to be practically unbounded and by the existence of reset protocols that can be used to restart the counters in some rare cases where faults will make this necessary.

International audience; This paper demonstrates the usefulness of distributed local verification of proofs, as a tool for the design of self-stabilizing algorithms.In particular, it introduces a somewhat generalized notion of distributed local proofs, and utilizes it for improving the time complexity significantly, while maintaining space optimality. As a result, we show that optimizing the memory size carries at most a small cost in terms of time, in the context of Minimum Spanning Tree (MST). That is, we present algorithms that are both time and space efficient for both constructing an MST and for verifying it.This involves several parts that may be considered contributions in themselves.First, we generalize the notion of local proofs, trading off the time complexity for memory efficiency. This adds a dimension to the study of distributed local proofs, which has been gaining attention recently. Specifically, we design a (self-stabilizing) proof labeling scheme which is memory optimal (i.e., $O(\log n)$ bits per node), and whose time complexity is $O(\log ^2 n)$ in synchronous networks, or $O(\Delta \log ^3 n)$ time in asynchronous ones, where $\Delta$ is the maximum degree of nodes. This answers an open problem posed by Awerbuch and Varghese (FOCS 1991). We also show that $\Omega(\log n)$ time is necessary, even in synchronous networks. Another property is that if $f$ faults occurred, then, within the requireddetection time above, they are detected by some node in the $O(f\log n)$ locality of each of the faults.Second, we show how to enhance a known transformer that makes input/output algorithms self-stabilizing. It now takes as input an efficient construction algorithm and an efficient self-stabilizing proof labeling scheme, and produces an efficient self-stabilizing algorithm. When used for MST, the transformer produces a memory optimal self-stabilizing algorithm, whose time complexity, namely, $O(n)$, is significantly better even than that of previous algorithms. (The time complexity of previous MST algorithms that used $\Omega(\log^2 n)$ memory bits per node was $O(n^2)$, and the time for optimal space algorithms was $O(n|E|)$.) Inherited from our proof labelling scheme, our self-stabilising MST construction algorithm also has the following two properties: (1) if faults occur after the construction ended, then they are detected by some nodes within $O(\log ^2 n)$ time in synchronous networks, or within $O(\Delta \log ^3 n)$ time in asynchronous ones, and (2) if $f$ faults occurred, then, within the required detection time above, they are detected within the $O(f\log n)$ locality of each of the faults. We also show how to improve the above two properties, at the expense of some increase in the memory.

We present optimal online algorithms for two related known problems involving Steiner Arborescence, improving both the lower and the upper bounds. One of them is the well studied continuous problem of the Rectilinear Steiner Arborescence$$\text{RSA}$$. We improve the lower bound and the upper bound on the competitive ratio for $$\text{RSA}$$ from $$O\log N$$ and $$\varOmega \sqrt{\log N}$$ to $$\varTheta \frac{\log N}{\log \log N}$$, where N is the number of Steiner points. This separates the competitive ratios of $$\text{RSA}$$ and the Symetric-$$\text{RSA}$$$$\text{SRSA}$$, two problems for which the bounds of Berman and Coulston is STOC 1997 were identical. The second problem is one of the Multimedia Content Distribution problems presented by Papadimitriou et al. in several papers and Charikar et al. SODA 1998. It can be viewed as the discrete counterparts or a network counterpart of $$\text{RSA}$$. For this second problem we present tight bounds also in terms of the network size, in addition to presenting tight bounds in terms of the number of Steiner points the latter are similar to those we derived for $$\text{RSA}$$.

In the CONGEST model, a communications network is an undirected graph whose $n$ nodes are processors and whose $m$ edges are the communications links between processors. At any given time step, a message of size $O(\log n)$ may be sent by each node to each of its neighbors. We show for the synchronous model: If all nodes start in the same round, and each node knows its ID and the ID's of its neighbors, or in the case of MST, the distinct weights of its incident edges and knows $n$, then there are Monte Carlo algorithms which succeed w.h.p. to determine a minimum spanning forest (MST) and a spanning forest (ST) using $O(n \log^2 n/\log\log n)$ messages for MST and $O(n \log n )$ messages for ST, resp. These results contradict the "folk theorem" noted in Awerbuch, et.al., JACM 1990 that the distributed construction of a broadcast tree requires $\Omega(m)$ messages. This lower bound has been shown there and in other papers for some CONGEST models; our protocol demonstrates the limits of these models. A dynamic distributed network is one which undergoes online edge insertions or deletions. We also show how to repair an MST or ST in a dynamic network with asynchronous communication. An edge deletion can be processed in $O(n\log n /\log \log n)$ expected messages in the MST, and $O(n)$ expected messages for the ST problem, while an edge insertion uses $O(n)$ messages in the worst case. We call this "impromptu" updating as we assume that between processing of edge updates there is no preprocessing or storage of additional information. Previous algorithms for this problem that use an amortized $o(m)$ messages per update require substantial preprocessing and additional local storage between updates.

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.

We present optimal competitive algorithms for two interrelated known problems involving Steiner Arborescence. One is the continuous problem of the Symmetric Rectilinear Steiner Arborescence (\({\sc SRSA}\)), whose online version was studied by Berman and Coulston as a symmetric version of the known Rectilinear Steiner Arborescence (RSA) problem. A very related, but discrete problem (studied separately in the past) is the online Multimedia Content Delivery (\({\sc MCD}\)) problem on line networks, presented originally by Papadimitriou, Ramanathan, and Rangan. An efficient content delivery was modeled as a low cost Steiner arborescence in a grid of network×time they defined. We study here the version studied by Charikar, Halperin, and Motwani (who used the same problem definitions, but removed some constraints on the inputs). The bounds on the competitive ratios introduced separately in the above papers were similar for the two problems: O(logN) for the continuous problem and O(logn) for the network problem, where N was the number of terminals to serve, and n was the size of the network. The lower bounds were \(\Omega(\sqrt{\log N})\) and \(\Omega(\sqrt{\log n})\) correspondingly.

We present algorithms for distributed verification and silent-stabilization of a DFS(Depth First Search) spanning tree of a connected network. Computing and maintaining such a DFS tree is an important task, e.g., for constructing efficient routing schemes. Our algorithm improves upon previous work in various ways. Comparable previous work has space and time complexities of O(nlogΔ) bits per node and O(nD) respectively, where Δ is the highest degree of a node, n is the number of nodes and D is the diameter of the network. In contrast, our algorithm has a space complexity of O(logn) bits per node, which is optimal for silent-stabilizing spanning trees and runs in O(n) time. In addition, our solution is modular since it utilizes the distributed verification algorithm as an independent subtask of the overall solution. It is possible to use the verification algorithm as a stand alone task or as a subtask in another algorithm. To demonstrate the simplicity of constructing efficient DFS algorithms using the modular approach, we also present a (non-silent) self-stabilizing DFS token circulation algorithm for general networks based on our silent-stabilizing DFS tree. The complexities of this token circulation algorithm are comparable to the known ones.

The difference between the speed of the actions of different processes is typically considered as an obstacle that makes the achievement of cooperative goals more difficult. In this work, we aim to highlight potential benefits of such asynchrony phenomena to tasks involving symmetry breaking. Specifically, in this paper, identical except for their speeds mobile agents are placed at arbitrary locations on a continuous cycle of length n and use their speed difference in order to rendezvous fast. We normalize the speed of the slower agent to be 1, and fix the speed of the faster agent to be some ci¾?>i¾?1. An agent does not know whether it is the slower agent or the faster one. The straightforward distributed-race DR algorithm is the one in which both agents simply start walking until rendezvous is achieved. It is easy to show that, in the worst case, the rendezvous time of DR is n/ci¾?-i¾?1. Note that in the interesting case, where c is very close to 1 e.g., ci¾?=i¾?1i¾?+i¾?1/n k , this bound becomes huge. Our first result is a lower bound showing that, up to a multiplicative factor of 2, this bound is unavoidable, even in a model that allows agents to leave arbitrary marks the white board model, even assuming sense of direction, and even assuming n and c are known to agents. That is, we show that under such assumptions, the rendezvous time of any algorithm is at least $\frac{n}{2c-1}$ if ci¾?≤i¾?3 and slightly larger specifically, $\frac{n}{c+1}$ if ci¾?>i¾?3. We then manage to construct an algorithm that precisely matches the lower bound for the case ci¾?≤i¾?2, and almost matches it when ci¾?>i¾?2. Moreover, our algorithm performs under weaker assumptions than those stated above, as it does not assume sense of direction, and it allows agents to leave only a single mark a pebble and only at the place where they start the execution. Finally, we investigate the setting in which no marks can be used at all, and show tight bounds for ci¾?≤i¾?2, and almost tight bounds for ci¾?>i¾?2.

Fundamental local symmetry breaking problems such as Maximal Independent Set (MIS) and coloring have been recognized as important by the community, and studied extensively in (standard) graphs. In particular, fast (i.e., logarithmic run time) randomized algorithms are well-established for MIS and Δ + 1-coloring in both the LOCAL and CONGEST distributed computing models. On the other hand, comparatively much less is known on the complexity of distributed symmetry breaking in hypergraphs. In particular, a key question is whether a fast (randomized) algorithm for MIS exists for hypergraphs.

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.

Afek, Awerbuch, Plotkin, and Saks identified an important fundamental problem inherent to distributed networks, which they called the Resource Controller problem. Consider, first, the problem in which one node (called the "root") is required to estimate the number of events that occurred all over the network. This counting problem can be viewed as a useful variant of the heavily studied and used task of topology update (that deals with collecting all remote information). The Resource Controller problem generalizes the counting problem: such remote events are considered as requests, and the counting node, i.e., the "root", also issues permits for the requests. That way, the number of request granted can be controlled (bounded).An efficient Resource Controller was constructed in the paper by Afek et al., which can operate on a dynamic network assuming that the network is spanned by a tree that may only grow, and only by allowing leaves to join the tree. In contrast, the Resource Controller presented here can operate under a more general dynamic model, allowing the spanning tree of the network to undergo both insertions and deletions of both leaves and internal nodes. Despite the more dynamic network model we allow, the message complexity of our controller is always at most the message complexity of the more restricted controller.All the applications for the controller of Afek et al. apply also for our controller. Moreover, with the same message complexity, our controller can handle these applications under the more general dynamic model mentioned above. In particular, under the more general dynamic model, the new controller can be transformed into an efficient size-estimation protocol, i.e., a protocol allowing the root to maintain a constant estimation of the number of nodes in the dynamically changing network. Informally, the resulted new size-estimation protocol uses O(log2n) amortized message complexity per topological change (assuming that the number of changes in the network size is "not too small"), where n is the current number of nodes in the network. In addition, with the same message complexity (as that of the size-estimation protocol), the new controller can be used to solve the name-assignment problem by assigning and maintaining unique log n+O(1)-bit identifiers for the nodes of the dynamic network.The new size-estimation protocol can be used for other applications, not mentioned in the paper by Afek et al.. Specifically, it can be used to extend many existing labeling schemes supporting different queries (e.g routing, ancestry, etc.) so that these schemes can now operate correctly also under more general models. These extensions maintain the same asymptotic sizes of the corresponding labels (or routing tables) of the original schemes and incur only a relatively low extra additive cost to the message complexity of the corresponding original schemes.

This paper concerns randomized leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete n-node networks that runs in O(1) rounds and (with high probability) takes only \(O(\sqrt{n}\log^{3/2} n)\) messages to elect a unique leader (with high probability). This algorithm is then extended to solve leader election on any connected non-bipartite n-node graph G in O(τ(G)) time and \(O(\tau(G)\sqrt{n}\log^{3/2} n)\) messages, where τ(G) is the mixing time of a random walk on G. The above result implies highly efficient (sublinear running time and messages) leader election algorithms for networks with small mixing times, such as expanders and hypercubes. In contrast, previous leader election algorithms had at least linear message complexity even in complete graphs. Moreover, super-linear message lower bounds are known for time-efficient deterministic leader election algorithms. Finally, an almost-tight lower bound is presented for randomized leader election, showing that \(\Omega(\sqrt n)\) messages are needed for any O(1) time leader election algorithm which succeeds with high probability. It is also shown that Ω(n 1/3) messages are needed by any leader election algorithm that succeeds with high probability, regardless of the number of the rounds. We view our results as a step towards understanding the randomized complexity of leader election in distributed networks.

A control architecture for a high-speed packet-switched network is described. The architecture was designed and implemented as part of the PARIS (subsequently plaNET and BBNS) networking project at IBM. This high bandwidth network for integrated communication (data, voice, video) is currently operational as a laboratory prototype. It will also be deployed within the AURORA Testbed that is part of the NSF/DARPA gigabit networking program. The high bandwidth dictates the need for specialized hardware to support faster packet handling for both point-to-point and multicast connections. A faster and more efficient network control is also required in order to support the increased number of connections and their changing requirements with time. The new network control architecture presented exploits specialized hardware, thereby enabling tasks to be performed faster and with less computation overhead. In particular, since control information can be distributed quickly using hardware packet handling mechanisms, decisions can be made based upon more complete and accurate information. In some respects, this has the effect of having the benefits of centralized control (e.g., easier bandwidth resource allocation to connections), while retaining the fault tolerance and scalability of a distributed architecture. >

This paper concerns {\em randomized} leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete $n$-node networks that runs in O(1) rounds and (with high probability) uses only $O(\sqrt{n}\log^{3/2} n)$ messages to elect a unique leader (with high probability). When considering the "explicit" variant of leader election where eventually every node knows the identity of the leader, our algorithm yields the asymptotically optimal bounds of O(1) rounds and O(n) messages. This algorithm is then extended to one solving leader election on any connected non-bipartite $n$-node graph $G$ in $O(\tau(G))$ time and $O(\tau(G)\sqrt{n}\log^{3/2} n)$ messages, where $\tau(G)$ is the mixing time of a random walk on $G$. The above result implies highly efficient (sublinear running time and messages) leader election algorithms for networks with small mixing times, such as expanders and hypercubes. In contrast, previous leader election algorithms had at least linear message complexity even in complete graphs. Moreover, super-linear message lower bounds are known for time-efficient {\em deterministic} leader election algorithms. Finally, we present an almost matching lower bound for randomized leader election, showing that $\Omega(\sqrt n)$ messages are needed for any leader election algorithm that succeeds with probability at least $1/e + \eps$, for any small constant $\eps > 0$. We view our results as a step towards understanding the randomized complexity ofleader election in distributed networks., Comment: Best Paper Award winner at ICDCN 2013, CDCN 2013 14th International Conference on Distributed Computing and Networking. Tata Institute of Fundamental Research, Mumbai, India

The Dynamic Content Distribution problem addresses the trade-off between storage and delivery costs in modern virtual Content Delivery Networks (CDNs). That is, a video file can be stored in multiple places so that the request of each user is served from a location that is near by to the user. This minimizes the delivery costs, but is associated with a storage cost. This problem is NP-hard even in grid networks. In this paper, we present a constant factor approximation algorithm for grid networks. We also present an O(logδ)-competitive algorithm, where δ is the normalized diameter of the network, for general networks with general metrics. We show a matching lower bound by using a reduction from online undirected Steiner tree. Our algorithms use a rather intuitive approach that has an elegant representation in geometric terms.

Algorithms for the group testing problem when there is no a priori information on the number of defective items are considered. The efficiency criterion used is the competitive ratio, which is the ratio of the number of tests required by an algorithm when there is no a priori information on the number of defective items, to the number of tests required by an optimal algorithm when the number of defective items is known in advance. A new algorithm is presented, and it is shown that the competitive ratio of this algorithm is 2. This result is an improvement over a previous algorithm due to Du and Hwang (1990) the competitive ratio of which is 2.75. It also proves a conjecture made by Du and Hwang. A new application of group testing techniques for high-speed network is discussed.

This paper demonstrates the usefulness of distributed local verification of proofs, as a tool for the design of algorithms. In particular, it introduces a somewhat generalized notion of distributed local proofs, and utilizes it for improving the memory size complexity, while obtaining time efficiency too.As a result, we show that optimizing the memory size carries at most a small cost in terms of time, in the context of Minimum Spanning Tree (MST). That is, we present algorithms that are both time and space efficient for constructing an MST, for verifying it, and for detecting the location of the faults. This involves several steps that may be considered contributions in themselves.First, we generalize the notion of local proofs, trading off the locality (or, really, the time complexity) for memory efficiency. This adds a dimension to the study of distributed local proofs, that has been gaining attention recently.Second, as opposed to previous studies that presented only the labels verification part of a proof labeling schemes, we present here also a space and time efficient distributed self stabilizing marker algorithm to generates those labels. This presents proof labeling schemes as an algorithmic tool.Finally, we show how to enhance a known transformer that makes input/output algorithms self stabilizing. It now takes as input an efficient construction algorithm and an efficient self stabilizing proof labeling scheme, and produces an efficient self stabilizing algorithm.When used for MST, the transformer produces a memory optimal (i.e., O(log n) bits per node) self stabilizing algorithm, whose time complexity, namely, O(n), is significantly better even than that of previous algorithms that where not space optimal. (The time complexity of previous MST algorithms that used ©(log2n) memory bits per node was O(n2), and the time for optimal space algorithms was O(n|E|).)Our MST algorithm also has the important property that, if faults occur after the construction ended, then they are detected by some nodes within O(log2n) time in synchronous networks, or within O(? log2n) time in asynchronous ones. This property is inherited from the specific proof labeling scheme we construct. It answers an open problem posed by Awerbuch and Varghese (FOCS 1991). We also show that ©(log n) time is necessary if the memory size is restricted to O(log n) bits, even in synchronous networks.Another property is that if f faults occurred, then, within the required detection time above, they are detected by some node in the O(f log n) locality of each of the faults. We also show how to improve the above detection time and locality, at the expense of some increase in the memory.

We analyze ways by which people decompose into groups in distributed systems. We are interested in systems in which an agent can increase its utility by connecting to other agents, but must also pay a cost that increases with the size of the sys- tem. The right balance is achieved by the right size group of agents. We formulate and analyze three intuitive and realistic games and show how simple changes in the protocol can dras- tically improve the price of anarchy of these games. In partic- ular, we identify two important properties for a low price of anarchy: agreement in joining the system, and the possibil- ity of appealing a rejection from a system. We show that the latter property is especially important if there are some pre- existing constraints regarding who may collaborate (or com- municate) with whom., Comment: Accepted at AAAI 2013: Twenty-Seventh Conference on Artificial Intelligence, Bellevue, Washington, USA

Shared counters are the key to solving a variety of coordination problems on multiprocessor machines, such as barrier synchronization and index distribution. It is desired that they, like shared objects in general, be robust, linearizable and scalable. We present the first linearizable and wait-free shared counter algorithm that achieves high throughput without a-priori knowledge about the system's level of asynchrony. Our algorithm can be easily adapted to any other combinable objects as well, such as stacks and queues. In particular, in an N-process execution E, our algorithm achieves high throughput of Ω(N/φE2 log2 φElogN), where φE is E's level of asynchrony. Moreover, our algorithm stands any constant number of faults. If E contains a constant number of faults, then our algorithm still achieves high throughput of Ω(N/φ′E2 log2 φ′E logN), where φ′E bounds the relative speeds of any two processes, at a time that both of them participated in E and none of them failed. Our algorithm can be viewed as an adaptive version of the Bounded-Wait-Combining (BWC) prior art algorithm. BWC receives as an input an argument φ as a (supposed) upper bound of φE, and achieves optimal throughput if φ = φE. However, if the given φ happens to be lower than the actual φE, or much greater than φE, then the throughput of BWC degraded significantly. Moreover, whereas BWC is only lock-free, our algorithm is more robust, since it is wait-free. To achieve high throughput and wait-freedom, we present a method that guarantees (for some common kind of procedures) the procedure's successful termination in a bounded time, regardless of shared memory contention. This method may prove useful by itself, for other problems

The problem of distributed leader election in an asynchronous complete network, in the presence of faults that occurred prior to the execution of the election algorithm, is discussed. Failures of this type are encountered, for example, during a recovery from a crash in the network. For a network with n processors, k of which start the algorithm that uses at most O(n log k+n+kt) messages is presented and shown to be optimal. An optimal algorithm for the case where the identities of the neighbors are known is also presented. It is noted that the order of the message complexity of a t-resilient algorithm is not always higher than that of a nonresilient one. The t-resilient algorithm is a systematic modification of an existing algorithm for a fault-free network. >

We investigate protocols for authenticated exchange of messages between two parties in a communication network. Secure authenticated exchange is essential for network security. It is not difficult to design simple and seemingly correct solutions for it, however, many such 'solutions' can be broken. We give some examples of such protocols and we show a useful methodology which can be used to break many protocols. In particular, we break a protocol that is being standardized by the ISO.We present a new authenticated exchange protocol which is both provably secure and highly efficient and practical. The security of the protocol is proven, based on an assumption about the the cryptosystem employed (namely, that it is secure when used in CBC mode on a certain message space). We think that this assumption is quite reasonable for many cryptosystems, and furthermore it is often assumed in practical use of the DES cryptosystem. Our protocol cannot be broken using the methodology we present (which was strong enough to catch all protocol flaws we found). The reduction to the security of the encryption mode, indeed captures the non-existence of the exposures that the methodology catches (specialized to the actual use of encryption in our protocol). Furthermore, the protocol prevents chosen plaintext or ciphertext attacks on the cryptosystem.The proposed protocol is efficient and practical in several aspects. First, it uses only conventional cryptography (like the DES, or any privately-shared one-way function) and no public-key. Second, the protocol does not require synchronized clocks or counter management. Third, only a small number of encryption operations is needed (we use no decryption), all with a single shared key. In addition, only three messages are exchanged during the protocol, and the size of these messages is minimal. These properties are similar to existing and proposed actual protocols. This is essential for integration of the proposed protocol into existing systems and embedding it in existing communication protocols.

Recently, quite a few papers studied methods for representing network properties by assigning informative labels to the vertices of a network. Consulting the labels given to any two vertices u and v for some function f (e.g. "distance(u, v)") one can compute the function (e.g. the graph distance between u and v). Some very involved lower bounds for the sizes of the labels were proven. In this paper, we demonstrate that such lower bounds are very sensitive to the number of vertices consulted. That is, we show several almost trivial constructions of such labeling schemes that beat the lower bounds by large margins. The catch is that one needs to consult the labels of three vertices instead of two. We term our generalized model labeling schemes with queries. Additional contributions are several extensions. In particular, we show that it is easy to extend our schemes for tree to work also in the dynamic scenario. We also demonstrate that the study of the queries model can help in designing a scheme for the traditional model too. Finally, we demonstrate extensions to the non-distributed environment. In particular, we show that one can preprocess a general weighted graph using almost linear space so that flow queries can be answered in almost constant time.

Shared counters are among the most basic coordination structures in distributed computing. Known implementations of shared counters are either blocking, non-linearizable, or have a sequential bottleneck. We present the first counter algorithm that is both linearizable, nonblocking, and can provably achieve high throughput in semisynchronous executions. The algorithm is based on a novel variation of the software combining paradigm that we call bounded-wait combining. It can thus be used to obtain implementations, possessing the same properties, of any object that supports combinable operations, such as stack or queue. Unlike previous combining algorithms where processes may have to wait for each other indefinitely, in the bounded-wait combining algorithm a process only waits for other processes for a bounded period of time and then ‘takes destiny in its own hands'. In order to reason rigorously about the parallelism attainable by our algorithm, we define a novel metric for measuring the throughput of shared objects which we believe is interesting in its own right. We use this metric to prove that our algorithm can achieve throughput of Ω(N / logN) in executions where process speeds vary only by a constant factor, where N is the number of processes that can participate in the algorithm. We also introduce and use pseduo-transactions – a technique for concurrent execution that may prove useful for other algorithms.

We study the scenario where a batch of transient faults hits an asynchronous distributed system by corrupting the state of some f nodes. We concentrate on the basic majority consensus problem, where nodes are required to agree on a common output value which is the input value of the majority of them. We give a fully self-stabilizing adaptive algorithm, i.e., the output value stabilizes in O(f) time at all nodes, for any unknown f. Moreover, a state stabilization occurs in time proportional to the (unknown) diameter of the network. Both upper bounds match known lower bounds to within a constant factor. Previous results (stated for a slightly less general problem called “persistent bit”) assumed the synchronous network model, and that f

A self-stabilizing distributed protocol can recover from any state-corrupting fault. A self-stabilizing protocol is called adaptive if its recovery time is proportional to the number of processors hit by the fault. General adaptive protocols are known for the special case of function computations: these are tasks that map static distributed inputs to static distributed outputs. In reactive distributed systems, input values at each node change on-line, and dynamic distributed outputs are to be generated in response in an on-line fashion. To date, only some specific reactive tasks have had an adaptive implementation. In this paper we outline the first proof that all reactive tasks admit adaptive protocols. The key ingredient of the proof is an algorithm for distributing input values in an adaptive fashion. Our algorithm is optimal, up to a constant factor, in its fault resilience, response time, and recovery time.

As communication networks grow, existing fault handling tools become increasingly unaffordable. In many cases the reason is that they involve global measures such as global time-outs or reset procedures, and their cost grows with the size of the network. Rather, for a fault handling mechanism to scale to large networks, it should involve local measures, or, at worse, fault local measures, i.e. measures the cost of which depends only on the number of failed nodes (which, thanks to to-day's technology, grows much slower than the networks). This decreases the recovery time and, moreover, often allows the non-faulty regions of the networks to continue their operation even during the recovery of the faulty parts. We describe several research ideas that lead in this direction.

In this paper we present time-optimal self-stabilizing algorithms for asynchronous distributed spanning tree computation in networks. We present both a randomized algorithm for anonymous networks as well as a deterministic version for ID-based networks. Our protocols are the first to be time-optimal (i.e. stabilize in time O(diameter)) without any prior knowledge of the network size or diameter, assuming we are allowed messages of size O(ID). Both results are achieved through a new technique of symmetry breaking that may be of independent interest.

In this paper we develop a graph-oriented model for dealing with broadcasting in radio networks. Using this model, optimality in broadcasting protocols is defined, and it is shown that the problem of finding an optimal protocol is NP-hard. A polynomial time algorithm is proposed under which a channel is assigned to nodes from global, multiple-source broadcasting considerations. In particular, nodes participating in the broadcast do not interfere with each other's transmissions, but otherwise simultaneous channel reuse is permitted. Protocol implementations of this approach by frequency division and by time division are given. It is shown that, using these protocols, bounded delay for broadcasted messages can be guaranteed.

In this paper we analyze perfectly secure key distribution schemes for dynamic conferences. In this setting, any member of a group of t users can compute a common key using only his private initial piece of information and the identities of the other t −1 users in the group. Keys are secure against coalitions of up to k users; that is, even if k users pool together their pieces they cannot compute anything about a key of any conference comprised of t other users. First we consider a noninteractive model where users compute the common key without any interaction. We prove the tight bound on the size of each user's piece of information of[formula]times the size of the common key. Then, we consider the model where interaction is allowed in the common key computation phase and show a gap between the models by exhibiting a one-round interactive scheme in which the user's information is only k + t −1 times the size of the common key. Finally, we present its adaptation to network topologies with neighbourhood constraints and to asymmetric (e.g., client-server) communication models.