The distributed Data Retrieval (DR) model consists of k peers connected by a complete peer-to-peer communication network, and a trusted external data source that stores an array X of n bits (n ≫ k). Up to β k of the peers might fail in any execution (for β ∈ [0, 1)). Peers can obtain the information either by inexpensive messages passed among themselves or through expensive queries to the source array X. In the DR model, we focus on designing protocols that minimize the number of queries performed by any nonfaulty peer (a measure referred to as the query complexity) while maximizing the resiliency parameter β. The Download problem requires each nonfaulty peer to correctly learn the entire array X. Earlier work on this problem focused on synchronous communication networks and established several deterministic and randomized upper and lower bounds. Our work is the first to extend the study of distributed data retrieval to asynchronous communication networks. We address the Download problem under both the Byzantine and crash failure models. We present query-optimal deterministic solutions in an asynchronous model that can tolerate any fixed fraction β < 1 of crash faults. In the Byzantine failure model, it is known that deterministic protocols incur a query complexity of Ω(n) per peer, even under synchrony. We extend this lower bound to randomized protocols in the asynchronous model for β ≥ 1/2, and further show that for β < 1/2, a randomized protocol exists with near-optimal query complexity.

We study fault-tolerant consensus in a variant of the synchronous message passing model, where, in each round, every node can choose to be awake or asleep. This is known as the sleeping model (Chatterjee, Gmyr, Pandurangan PODC 2020) and defines the awake complexity (also called energy complexity), which measures the maximum number of rounds that any node is awake throughout the execution. Only awake nodes can send and receive messages in a given round and all messages sent to sleeping nodes are lost. We present new deterministic consensus algorithms that tolerate up to f < n crash failures, where n is the number of nodes. Our algorithms match the optimal time complexity lower bound of f+1 rounds. For multi-value consensus, where the input values are chosen from some possibly large set, we achieve an energy complexity of 𝒪(⌈ f² / n ⌉) rounds, whereas for binary consensus, we show an algorithm to achieve 𝒪(⌈ f / √n ⌉) energy complexity.

We consider the Download problem in the Data Retrieval Model, introduced in (DISC'24), where a distributed set of peers, some of which may be Byzantine, seek to learn n bits of data stored at a trustworthy external data source. Each bit of data can be learned by a peer either through a direct (costly) query of the source or through other peers that have already learned it; the goal is to design a collaborative protocol that reduces the maximum number of bits queried by any one peer ("query complexity"). We achieve optimal query complexity in a synchronous fully connected network with resilience to any constant fraction β < 1 of Byzantine peers, under varying assumptions regarding time and message size.

We consider the Download problem in the Data Retrieval Model, introduced in DISC'24, where a distributed set of peers, some of which may be Byzantine, seek to learn n bits of data stored at a trustworthy external data source. Each bit of data can be learned by a peer either through a direct and costly query of the source or through other peers that have already learned it; the goal is to design a collaborative protocol that reduces the query complexity defined as the maximum number of bits queried by any honest peer. We begin with a randomized protocol for the Download problem that achieves optimal query complexity, up to a logarithmic factor. For a stronger "dynamic" adversary that can change the set of Byzantine peers from one round to the next, we achieve optimality (within log factors) for both query complexity (in expectation) and time complexity, but with larger messages. In broadcast communication, where all peers (including Byzantine peers) are required to send the same message to all peers, we achieve (up to log factors) an optimal trade-off between query complexity, time complexity, and message size with the dynamic adversary. All of our protocols can tolerate any constant fraction β < 1 of Byzantine peers.

The distributed Data Retrieval (DR) model consists of k peers connected by a complete peer-to-peer communication network, and a trusted external data source that stores an array X of n bits (n ≫ k). Up to β k of the peers might fail in any execution (for β ∈ [0, 1)). Peers can obtain the information either by inexpensive messages passed among themselves or through expensive queries to the source array X. In the DR model, we focus on designing protocols that minimize the number of queries performed by any nonfaulty peer (a measure referred to as query complexity) while maximizing the resilience parameter β. The Download problem requires each nonfaulty peer to correctly learn the entire array X. Earlier work on this problem focused on synchronous communication networks and established several deterministic and randomized upper and lower bounds. Our work is the first to extend the study of distributed data retrieval to asynchronous communication networks. We address the Download problem under both the Byzantine and crash failure models. We present query-optimal deterministic solutions in an asynchronous model that can tolerate any fixed fraction β < 1 of crash faults. In the Byzantine failure model, it is known that deterministic protocols incur a query complexity of Ω(n) per peer, even under synchrony. We extend this lower bound to randomized protocols in the asynchronous model for β ≥ 1/2, and further show that for β < 1/2, a randomized protocol exists with near-optimal query complexity. To the best of our knowledge, this is the first work to address the Download problem in asynchronous communication networks.

Abstract. We consider the problem of characterizing degree sequences that can be realized by a bipartite graph. If a partition of the sequence into the two sides of the bipartite graph is given as part of the input, then there is a complete characterization that was established more than 60 years ago. However, the general question, in which a partition and a realizing graph need to be determined, is still open. We investigate the role of an important class of special partitions, called High-Low partitions, which separate the degrees of a sequence into two groups, the high degrees and the low degrees. We show that when the High-Low partition exists and satisfies some natural properties, analyzing the High-Low partition resolves the bigraphic realization problem. For sequences that are known to be not realizable by a bipartite graph or that are undecided, we provide approximate realizations based on the High-Low partition.

Necessary and sufficient conditions for a pair of integer sequences to be the degree sequences of the two sides of a bipartite graph were established more than six decades ago by Gale and Ryser. In contrast, the general question of deciding whether a single sequence is bigraphic, namely, can be realized by a bipartite graph, is still open. We consider even sequences, in which the multiplicity of any integer in the degree sequence is even. One can always partition an even sequence into two identical sequences, resulting in an equal partition. We show that if a given even sequence d is graphic, then there are only two options: either d is bigraphic, or d is 2-bigraphic, namely, can be realized by a bipartite multigraph with maximum multiplicity 2. For an r -graphic sequence we show that it is t -bigraphic for some t ≤ 2 r , and we also show that the analysis is tight, namely that t = 2 r is possible. In addition, we show that given an r -graphic sequence d , there exists an even sequence d ′ which is similar to d in a well-defined sense such that d ′ is even and r -graphic, and therefore t -bigraphic for some t ≤ 2 r .

A sequence d = (d_1,d_2, …, d_n) of positive integers is graphic if it is the degree sequence of some simple graph G, and planaric if it is the degree sequence of some simple planar graph G. It is known that if ∑ d ≤ 2n - 2, then d has a realization by a forest, hence it is trivially planaric. In this paper, we seek bounds on ∑ d that guarantee that if d is graphic then it is also planaric. We show that this holds true when ∑ d ≤ 4n-4-2ω₁, where ω₁ is the number of 1’s in d. Conversely, we show that there are graphic sequences with ∑ d = 4n-2ω₁ that are non-planaric. For the case ω₁ = 0, we show that d is planaric when ∑ d ≤ 4n-4. Conversely, we show that there is a graphic sequence with ∑ d = 4n-2 that is non-planaric. In fact, when ∑ d ≤ 4n-6-2ω₁, d can be realized by a graph with a 2-page book embedding.

We study a framework for modeling distributed network systems assisted by a reliable and powerful cloud service. Our framework aims at capturing hybrid systems based on a point to point message passing network of machines, with the additional capability of being able to access the services of a trusted high-performance external entity (the cloud). We focus on one concrete aspect that was not studied before, namely, ways of utilizing the cloud assistance in order to attain increased resilience against Byzantine behavior of machines in the network. Our network is modeled as a congested clique comprising $k$ machines that are completely connected to form a clique and can communicate with each other by passing small messages. In every execution, up to $βk$ machines (for suitable values of $β\in [0, 1)$) are allowed to be Byzantine, i.e., behave maliciously including colluding with each other, with the remaining $γk$ or more machines being \emph{honest} (for $γ=1-β$). Additionally, the machines in our congested clique can access data through a trusted cloud via queries. This externality of the data captures many real-world distributed computing scenarios and provides a natural context for exploring Byzantine resilience for essentially all conceivable problems. Moreover, we are no longer bound by the usual limits of $β< 1/3$ or even $β< 1/2$ that are typically seen in Byzantine Agreement. We focus on a few fundamental problems. We start with the ${\textsf{Download}}$ problem, wherein the cloud stores $n$ bits and these $n$ bits must be downloaded to all of the $k$ machines. In addition to ${\textsf{Download}}$, we also consider the problem of computing the ${\textsf{Disjunction}}$ and ${\textsf{Parity}}$ of the bits in the cloud. We study these problems under several settings comprising various $β$ values and adversarial capabilities.

The paper considers the SUPPORTED model of distributed computing introduced by Schmid and Suomela [HotSDN'13], generalizing the LOCAL and CONGEST models. In this framework, multiple instances of the same problem, differing from each other by the subnetwork to which they apply, recur over time, and need to be solved efficiently online. To do that, one may rely on an initial preprocessing phase for computing some useful information. This preprocessing phase makes it possible, in some cases, to overcome locality-based time lower bounds. A first contribution of the current paper is expanding the spectrum of problem types to which the SUPPORTED model applies. In addition to subnetwork-defined recurrent problems, we introduce also recurrent problems of two additional types: (i) instances defined by partial client sets, and (ii) instances defined by partially fixed outputs. Our second contribution is illustrating the versatility of the SUPPORTED framework by examining recurrent variants of three classical graph problems. The first problem is Minimum Client Dominating Set (CDS), a recurrent version of the classical dominating set problem with each recurrent instance requiring us to dominate a partial client set. We provide a constant time approximation scheme for CDS on trees and planar graphs. The second problem is Color Completion (CC), a recurrent version of the coloring problem in which each recurrent instance comes with a partially fixed coloring (of some of the vertices) that must be completed. We study the minimum number of new colors and the minimum total number of colors necessary for completing this task. The third problem we study is a recurrent version of Locally Checkable Labellings (LCL) on paths of length $n$. We show that such problems have complexities that are either $Θ(1)$ or $Θ(n)$, extending the results of Foerster et al. [INFOCOM'19].

We study the SUPPORTED model of distributed computing introduced by Schmid and Suomela [15], generalizing the LOCAL and CONGEST models. In this framework, multiple instances of the same problem, differing from each other by some problem specific input, recur over time, and need to be solved efficiently online. To do that, one may rely on an initial preprocessing phase for computing some useful information. This preprocessing phase makes it possible, in some cases, to obtain improved distributed algorithms, overcoming locality-based time lower bounds.

Theoretical study of optimization problems in wireless communication often deals with tasks that concern a single point. For example, the power control problem requires computing a power assignment guaranteeing that each transmitting station s i is successfully received at a single receiver point r i . This paper aims at addressing communication applications that require handling two-dimensional tasks (e.g., guaranteeing successful transmission in entire regions rather than at specific points). The natural approach to two-dimensional optimization tasks is to discretize the optimization domain, e.g., by sampling points within the domain. The straightforward implementation of the discretization approach, however, might incur high time and memory requirements, and moreover, it cannot guarantee exact solutions. The alternative proposed and explored in this paper is based on establishing the minimum principle 1 for the signal to interference and noise ratio (SINR) function with free space path loss (i.e., when the signal decays in proportion to the square of the distance between the transmitter and receiver). Essentially, the minimum principle allows us to reduce the dimension of the optimization domain without losing anything in the accuracy or quality of the solution. More specifically, when the two-dimensional optimization domain is bounded and free from any interfering station, the minimum principle implies that it is sufficient to optimize the SINR function over the boundary of the domain, as the “hardest” points to be satisfied reside on the boundary and not in the interior. We then utilize the minimum principle as the basis for an improved discretization technique for solving two-dimensional problems in the SINR model. This approach is shown to be useful for handling optimization problems over two dimensions (e.g., power control, energy minimization); in providing tight bounds on the number of null cells in the reception map; and in approximating geometric and topological properties of the wireless reception map (e.g., maximum inscribed sphere). The minimum principle, as well as the interplay between continuous and discrete analysis presented in this paper, are expected to pave the way to future study of algorithmic SINR in higher dimensions.

A singularly (near) optimal distributed algorithm is one that is (near) optimal in \emph{two} criteria, namely, its time and message complexities. For \emph{synchronous} CONGEST networks, such algorithms are known for fundamental distributed computing problems such as leader election [Kutten et al., JACM 2015] and Minimum Spanning Tree (MST) construction [Pandurangan et al., STOC 2017, Elkin, PODC 2017]. However, it is open whether a singularly (near) optimal bound can be obtained for the MST construction problem in general \emph{asynchronous} CONGEST networks. We present a randomized distributed MST algorithm that, with high probability, computes an MST in \emph{asynchronous} CONGEST networks and takes $\tilde{O}(D^{1+ε} + \sqrt{n})$ time and $\tilde{O}(m)$ messages, where $n$ is the number of nodes, $m$ the number of edges, $D$ is the diameter of the network, and $ε>0$ is an arbitrarily small constant (both time and message bounds hold with high probability). Our algorithm is message optimal (up to a polylog$(n)$ factor) and almost time optimal (except for a $D^ε$ factor). Our result answers an open question raised in Mashregi and King [DISC 2019] by giving the first known asynchronous MST algorithm that has sublinear time (for all $D = O(n^{1-ε})$) and uses $\tilde{O}(m)$ messages. Using a result of Mashregi and King [DISC 2019], this also yields the first asynchronous MST algorithm that is sublinear in both time and messages in the $KT_1$ CONGEST model. A key tool in our algorithm is the construction of a low diameter rooted spanning tree in asynchronous CONGEST that has depth $\tilde{O}(D^{1+ε})$ (for an arbitrarily small constant $ε> 0$) in $\tilde{O}(D^{1+ε})$ time and $\tilde{O}(m)$ messages. To the best of our knowledge, this is the first such construction that is almost singularly optimal in the asynchronous setting.

We study the Budgeted Dominating Set (BDS) problem on uncertain graphs, namely, graphs with a probability distribution p associated with the edges, such that an edge e exists in the graph with probability p(e). The input to the problem consists of a vertex-weighted uncertain graph 𝒢 = (V, E, p, ω) and an integer budget (or solution size) k, and the objective is to compute a vertex set S of size k that maximizes the expected total domination (or total weight) of vertices in the closed neighborhood of S. We refer to the problem as the Probabilistic Budgeted Dominating Set (PBDS) problem. In this article, we present the following results on the complexity of the PBDS problem. 1) We show that the PBDS problem is NP-complete even when restricted to uncertain trees of diameter at most four. This is in sharp contrast with the well-known fact that the BDS problem is solvable in polynomial time in trees. We further show that PBDS is 𝖶[1]-hard for the budget parameter k, and under the Exponential time hypothesis it cannot be solved in n^o(k) time. 2) We show that if one is willing to settle for (1-ε) approximation, then there exists a PTAS for PBDS on trees. Moreover, for the scenario of uniform edge-probabilities, the problem can be solved optimally in polynomial time. 3) We consider the parameterized complexity of the PBDS problem, and show that Uni-PBDS (where all edge probabilities are identical) is 𝖶[1]-hard for the parameter pathwidth. On the other hand, we show that it is FPT in the combined parameters of the budget k and the treewidth. 4) Finally, we extend some of our parameterized results to planar and apex-minor-free graphs. Our first hardness proof (Thm. 1) makes use of the new problem of k-Subset Σ-Π Maximization (k-SPM), which we believe is of independent interest. We prove its NP-hardness by a reduction from the well-known k-SUM problem, presenting a close relationship between the two problems.

No abstract available.

This paper concerns designing distributed algorithms that are singularly optimal, i.e., algorithms that are simultaneously time and message optimal, for the fundamental leader election problem in asynchronous networks. Kutten et al. (JACM 2015) presented a singularly near optimal randomized leader election algorithm for general synchronous networks that ran in O(D) time and used O(m log n) messages (where D, m, and n are the network’s diameter, number of edges and number of nodes, respectively) with high probability. Both bounds are near optimal (up to a logarithmic factor), since Ω(D) and Ω(m) are the respective lower bounds for time and messages for leader election even for synchronous networks and even for (Monte-Carlo) randomized algorithms. On the other hand, for general asynchronous networks, leader election algorithms are only known that are either time or message optimal, but not both. Kutten et al. (DISC 2020) presented a randomized asynchronous leader election algorithm that is singularly near optimal for complete networks, but left open the problem for general networks. This paper shows that singularly near optimal (up to polylogarithmic factors) bounds can be achieved for general asynchronous networks. We present a randomized singularly near optimal leader election algorithm that runs in O(D + log² n) time and O(m log² n) messages with high probability. Our result is the first known distributed leader election algorithm for asynchronous networks that is near optimal with respect to both time and message complexity and improves over a long line of results including the classical results of Gallager et al. (ACM TOPLAS, 1983), Peleg (JPDC, 1989), and Awerbuch (STOC, 89).

The classical degree realization problem is defined as follows: Given a sequence d̄ = (d_1,…,d_n) of positive integers, construct an n-vertex graph in which each vertex u_i has degree d_i (or decide that no such graph exists). In this article, we present and study the related selected neighbor degree realization problem, which requires that each vertex u_i of G has a neighbor of degree d_i. We solve the problem when G is required to be acyclic (i.e., a forest), and present a sufficient and necessary condition for a given sequence to be realizable.

We study graph realization problems from a distributed perspective. The problem is naturally applicable to the distributed construction of overlay networks that must satisfy certain degree or connectivity properties, and we study it in the node capacitated clique (NCC) model of distributed computing, recently introduced for representing peer-to-peer networks.We focus on two central variants, degree-sequence realization and minimum threshold-connectivity realization. In the degree sequence problem, each node v is associated with a degree d(v), and the resulting degree sequence is realizable if it is possible to construct an overlay network in which the degree of each node v is d(v). The minimum threshold-connectivity problem requires us to construct an overlay network that satisfies connectivity constraints specified between every pair of nodes.Overlay network realizations can be either explicit or implicit. Explicit realizations require both endpoints of any edge in the realized graph to be aware of the edge. In implicit realizations, on the other hand, at least one endpoint of each edge of the realized graph needs to be aware of the edge.The main realization algorithms we present are the following. (1) A $\tilde O(\min \{ \sqrt m ,\Delta \} )$ time algorithm for implicit realization of a degree sequence. Here, Δ = maxvd(v) is the maximum degree and m = (1/2) v d(v) is the number of edges in the final realization. (2) A $\tilde O\left( \Delta \right)$ time algorithm for an explicit realization of a degree sequence. We first compute an implicit realization and then transform it into an explicit one in $\tilde O\left( \Delta \right)$ additional rounds. (3) A $\tilde O\left( \Delta \right)$ time algorithm for the threshold connectivity problem that obtains an explicit solution and an improved $\tilde O\left( 1 \right)$ algorithm for implicit realization when all nodes know each other’s IDs. These algorithms are 2-approximations w.r.t. the number of edges. Our algorithms are complemented by lower bounds showing tightness up to log n factors. Additionally, we provide algorithms for realizing trees and an $\tilde O\left( 1 \right)$ round algorithm for approximate degree sequence realization.

We consider the problem of realizable interval sequences. An interval sequence is comprised of $n$ integer intervals $[a_i,b_i]$ such that $0\le a_i\leq b_i \le n-1$ and is said to be graphic/realizable if there exists a graph with degree sequence, say, $D=(d_1,\ldots,d_n),$ satisfying the condition $a_i\leq d_i\leq b_i$ for each $i\in[1,n]$. There is a characterization (also implying an $O(n)$ verifying algorithm) known for realizability of interval sequences, which is a generalization of the Erdös--Gallai characterization for graphic sequences. However, given any realizable interval sequence, there is no known algorithm for computing a corresponding graphic certificate in $o(n^2)$ time. In this paper, we provide an $O(n \log n)$ time algorithm for computing a graphic sequence for any realizable interval sequence. In addition, when the interval sequence is nonrealizable, we show how to find a graphic sequence having minimum deviation with respect to the given interval sequence in the same time. Finally, we consider variants of the problem, such as computing the most-regular graphic sequence and computing a minimum extension of a length $p$ nongraphic sequence to a graphic one.

In the future, analysis of social networks will conceivably move from graphs to hypergraphs. However, theory has not yet caught up with this type of data organizational structure. By introducing and analyzing a general model of preferential attachment hypergraphs, this paper makes a step towards narrowing this gap. We consider a random preferential attachment model H(p, Y) for network evolution that allows arrivals of both nodes and hyperedges of random size. At each time step t, two possible events may occur: (1) [vertex arrival event:] with probability p > 0 a new vertex arrives and a new hyperedge of size Yt, containing the new vertex and Yt − 1 existing vertices, is added to the hypergraph; or (2) [hyperedge arrival event:] with probability 1 − p, a new hyperedge of size Yt, containing Yt existing vertices, is added to the hypergraph. In both cases, the involved existing vertices are chosen independently at random according to the preferential attachment rule, i.e., with probability proportional to their degree, where the degree of a vertex is the number of edges containing it. Assuming general restrictions on the distribution of Yt, we prove that the H(p, Y) model generates power law networks, i.e., the expected fraction of nodes with degree k is proportional to k−1−⌈, where [EQUATION]. This extends the special case of preferential attachment graphs, where Yt = 2 for every t, yielding ⌈ = 2/(2 − p). Therefore, our results show that the exponent of the degree distribution is sensitive to whether one considers the structure of a social network to be a hypergraph or a graph. We discuss, and provide examples for, the implications of these considerations.

This paper presents and studies a generalization of the microscopic image reconstruction problem (MIR) introduced by Frosini and Nivat [Andrea Frosini and Maurice Nivat, 2007; Nivat, 2002]. Consider a specimen for inspection, represented as a collection of points typically organized on a grid in the plane. Assume each point x has an associated physical value l_x, which we would like to determine. However, it might be that obtaining these values precisely (by a surgical probe) is difficult, risky, or impossible. The alternative is to employ aggregate measuring techniques (such as EM, CT, US or MRI), whereby each measurement is taken over a larger window, and the exact values at each point are subsequently extracted by computational methods. In this paper we extend the MIR framework in a number of ways. First, we consider a generalized setting where the inspected object is represented by an arbitrary graph G, and the vector l in R^n assigns a value l_v to each node v. A probe centered at a vertex v will capture a window encompassing its entire neighborhood N[v], i.e., the outcome of a probe centered at v is P_v = sum_{w in N[v]} l_w. We give a criterion for the graphs for which the extended MIR problem can be solved by extracting the vector l from the collection of probes, P^- = {P_v | v in V}. We then consider cases where such reconstruction is impossible (namely, graphs G for which the probe vector P is inconclusive, in the sense that there may be more than one vector l yielding P). Let us assume that surgical probes (whose outcome at vertex v is the exact value of l_v) are technically available to us (yet are expensive or risky, and must be used sparingly). We show that in such cases, it may still be possible to achieve reconstruction based on a combination of a collection of standard probes together with a suitable set of surgical probes. We aim at identifying the minimum number of surgical probes necessary for a unique reconstruction, depending on the graph topology. This is referred to as the Minimum Surgical Probing problem (MSP). Besides providing a solution for the above problems for arbitrary graphs, we also explore the range of possible behaviors of the Minimum Surgical Probing problem by determining the number of surgical probes necessary in certain specific graph families, such as perfect k-ary trees, paths, cycles, grids, tori and tubes.

We consider shortest paths computation and related tasks from the viewpoint of network algorithms, where the n-node input graph is also the computational system: nodes represent processors and edges represent communication links, which can in each time step carry an $$\mathcal {O}(\log n)$$ -bit message. We identify several basic distributed distance computation tasks that are highly useful in the design of more sophisticated algorithms and provide efficient solutions. We showcase the utility of these tools by means of several applications.

This paper introduces an extended notion of expansion suitable for radio networks. A graph G=(V,E) is said to be an (α_w, β_w) -\em wireless expander if for every subset S \subseteq V s.t. |S|łeq α_w \cdot |V| , there exists a subset S'\subseteq S s.t. there are at least β_w \cdot |S| vertices in V\backslash S that are adjacent in G to exactly one vertex in S' . The main question we ask is the following: to what extent are ordinary expanders also good wireless expanders? We answer this question in a nearly tight manner. On the positive side, we show that any (α, β)-expander with maximum degree Δ and β\geq 1/Δ$ is also a $(α_w, β_w)$ wireless expander with α_w \ge α$ and β_w = Ømega(β / łog (2 \cdot \min\Δ / β, Δ \cdot β\ ))$. Thus the wireless expansion can be smaller than the ordinary expansion by at most a factor that is logarithmic in \min\Δ / β, Δ \cdot β\ , which, in turn, depends on the average degree rather than the maximum degree of the graph. In particular, for low arboricity graphs (such as planar graphs), the wireless expansion matches the ordinary expansion up to a constant factor. We complement this positive result by presenting an explicit construction of a "bad'' (α, β) -expander for which the wireless expansion is β_w = O(β / łog (2 \cdot \min\Δ / β, Δ \cdot β\ ) . We also analyze the theoretical properties of wireless expanders and their connection to unique neighbor expanders, and then demonstrate their applicability: Our results (both the positive and the negative) yield improved bounds for the spokesmen election problem that was introduced in the seminal paper of Chlamtac and Weinstein from 1991 to devise efficient broadcasting for multihop radio networks. Our negative result yields a significantly simpler proof than that from the seminal paper of Kushilevitz and Mansour from 1998 for a lower bound on the broadcast time in radio networks.

This paper demonstrates that the Preferential Attachment rule naturally emerges in the context of evolutionary network formation, as the unique Nash equilibrium of a simple social network game. In this game, each node aims at maximizing its degree in the future, representing its social capital in the "society" formed by the nodes and their connections. This result provides additional formal support to the commonly used Preferential Attachment model, initially designed to capture the "rich get richer" aphorism. In the process of establishing our result, we expose new connections between Preferential Attachment, random walks, and Young»s Lattice.

A fault-tolerant structure for a network is required to continue functioning following the failure of some of the network’s edges or vertices. This article addresses the problem of designing a fault-tolerant (α , β) approximate BFS structure (or FT-ABFS structure for short), namely, a subgraph H of the network G such that subsequent to the failure of some subset F of edges or vertices, the surviving part of H (namely, H \ F ) still contains an approximate BFS spanning tree for (the surviving part of) G , satisfying dist( s,v,H \ F ) ≤ α ċ dist( s,v,G \ F )+ β for every v isin V . Our first result is an algorithm that given an n -vertex unweighted undirected graph G and a source s constructs a multiplicative (3,0) FT-ABFS structure rooted at s resilient to a failure of a single edge with at most 4 n edges (improving by an O (log n ) factor on the near-tight result of Baswana and Khanna (2010) for the special case of edge failures). This was recently improved to 2n edges by Bilò et al. (2014). Next, we consider the multiple edge faults case, for a constant integer f >1, we prove that there exists a (polynomial-time constructible) (3 f , f log n ) FT-ABFS structure with O ( f n ) edges that is resilient against f faults. We also show the existence of a (3 f +1,0) FT-ABFS structure with O ( f log f n ċ n ) edges. We then consider additive (1, β ) FT-ABFS structures and demonstrate an interesting dichotomy between multiplicative and additive spanners. In contrast to the linear size of ( α ,0) FT-ABFS structures, we show that for every n , there exist δ , ε >0, and n -vertex graphs G with a source s for which any (1, n δ ) FT-ABFS structure rooted at s has Ω ( n 7/6 −ε) edges. For the case of additive stretch 3, we show that (1,3) FT-ABFS structures admit a lower bound of Ω ( n 5/4 ) edges.

Population control policies are proposed and in some places employed as a means towards curbing population growth. This paper is concerned with a disturbing side-effect of such policies, namely, the potential risk of societal fragmentation due to changes in the distribution of family sizes. This effect is illustrated in some simple settings and demonstrated by simulation. In addition, the dependence of societal fragmentation on family size distribution is analyzed. In particular, it is shown that under the studied model, any population control policy that disallows families of 3 or more children incurs the possible risk of societal fragmentation.

Area coverage is an important task for mobile robots, mainly due to its applicability in many domains, such as search and rescue. In this paper we study the problem of multi-robot coverage, in which the robots must obey a strong communication restriction: they should maintain connectivity between teammates throughout the coverage. We formally describe the Multi-Robot Connected Tree Coverage problem, and an algorithm for covering perfect N-ary trees while adhering to the communication requirement. The algorithm is analyzed theoretically, providing guarantees for coverage time by the notion of speedup factor. We enhance the theoretically-proven solution with a dripping heuristic algorithm, and show in extensive simulations that it significantly decreases the coverage time. The algorithm is then adjusted to general (not necessarily perfect) N-ary trees and additional experiments prove its efficiency. Furthermore, we show the use of our solution in a simulated officebuilding scenario. Finally, we deploy our algorithm on real robots in a real office building setting, showing efficient coverage time in practice.

Consider a random preferential attachment model G(p) for network evolution that allows both node and edge arrivals. Starting with an arbitrary nonempty graph G0, at each time step, there are two possible events: with probability p > 0 a new node arrives and a new edge is added between the new node and an existing node, and with probability 1 - p a new edge is added between two existing nodes. In both cases, the involved existing nodes are chosen at random according to preferential attachment, i.e., with probability proportional to their degree. G(p) is known to generate power law networks, i.e., the fraction of nodes with degree k is proportional to k-β. Here β=(4-p)/(2-p) is in the range (2,3].

A distributed task is local if its time complexity is (nearly) constant, otherwise it is global. Unfortunately, local tasks are relatively scarce, and most distributed tasks require time at least logarithmic in the network size (and often higher than that). In a dynamic setting, i.e., when the network undergoes repeated and frequent topological changes, such as vertex and edge insertions and deletions, it is desirable to be able to perform a local update procedure around the modified part of the network, rather than running a static global algorithm from scratch following each change. This paper makes a step towards establishing the hypothesis that many (statically) non-local distributed tasks are local-on-average in the dynamic setting, namely, their amortized time complexity is O(log* n). Towards establishing the plausibility of this hypothesis, we propose a strategy for transforming static O(polylog(n)) time algorithms into dynamic O(log* n) amortized time update procedures. We then demonstrate the usefulness of our strategy by applying it to several fundamental problems whose static time complexity is logarithmic, including forest-decomposition, edge-orientation and coloring sparse graphs, and show that their amortized time complexity in the dynamic setting is indeed O(log* n).

Approximate matchings in fully dynamic graphs have been intensively studied in recent years. Gupta and Peng [FOCS'13] presented a deterministic algorithm for maintaining fully dynamic (1 + ∊)-approximate maximum cardinality matching (MCM) in general graphs with worst-case update time , for any ∊ > 0, where m denotes the current number of edges in the graph. Despite significant research efforts, this update time barrier remains the state-of-the-art even if amortized time bounds and randomization are allowed or the approximation factor is allowed to increase from 1 + ∊ to 2 – ∊, and even in basic graph families such as planar graphs. This paper presents a simple deterministic algorithm whose performance depends on the density of the graph. Specifically, we maintain fully dynamic (1 + ∊)-approximate MCM with worst-case update time O(α · ∊–2) for graphs with arboricity1 bounded by α. The update time bound holds even if the arboricity bound α changes dynamically. Since the arboricity ranges between 1 and , our density-sensitive bound O(α ·∊–2) naturally generalizes the bound of Gupta and Peng. For the family of bounded arboricity graphs (which includes forests, planar graphs, and graphs excluding a fixed minor), in the regime ∊ = O(1) our update time reduces to a constant. This should be contrasted with the previous best 2-approximation results for bounded arboricity graphs, which achieve either an O(log n) worst-case bound (Kopelowitz et al, ICALP'14) or an amortized bound (He et al., ISAAC'14), where n stands for the number of vertices in the graph. En route to this result, we provide local algorithms of independent interest for maintaining fully dynamic approximate matching and vertex cover.

This article proposes a forbidden-set labeling scheme for the family of unweighted graphs with doubling dimension bounded by α. For an n -vertex graph G in this family, and for any desired precision parameter ϵ > 0, the labeling scheme stores an O (1 + ϵ − 1 ) 2α log 2 n -bit label at each vertex. Given the labels of two end-vertices s and t , and the labels of a set F of “forbidden” vertices and/or edges, our scheme can compute, in O (1 + ϵ − 1 ) 2α · | F | 2 log n time, a 1 + ϵ stretch approximation for the distance between s and t in the graph G ∖ F . The labeling scheme can be extended into a forbidden-set labeled routing scheme with stretch 1 + ϵ for graphs of bounded doubling dimension.

A fault-tolerant structure for a network is required for continued functioning following the failure of some of the network’s edges or vertices. This article considers breadth-first search (BFS) spanning trees and addresses the problem of designing a sparse fault-tolerant BFS structure (FT-BFS structure), namely, a sparse subgraph T of the given network G such that subsequent to the failure of a single edge or vertex, the surviving part T ′ of T still contains a BFS spanning tree for (the surviving part of) G . For a source node s , a target node t , and an edge e ∈ G , the shortest s − t path P s , t , e that does not go through e is known as a replacement path . Thus, our FT-BFS structure contains the collection of all replacement paths P s , t , e for every t ∈ V ( G ) and every failed edge e ∈ E ( G ). Our main results are as follows. We present an algorithm that for every n -vertex graph G and source node s constructs a (single edge failure) FT-BFS structure rooted at s with O ( n ċ min {Depth( s ), √n{) edges, where Depth( s ) is the depth of the BFS tree rooted at s . This result is complemented by a matching lower bound, showing that there exist n -vertex graphs with a source node s for which any edge (or vertex) FT-BFS structure rooted at s has Ω( n 3/2 ) edges. We then consider fault-tolerant multi-source BFS structures (FT-MBFS structures), aiming to provide (following a failure) a BFS tree rooted at each source s ∈ S for some subset of sources S ⊆ V . Again, tight bounds are provided, showing that there exists a poly-time algorithm that for every n -vertex graph and source set S ⊆ V of size σ constructs a (single failure) FT-MBFS structure T *( S ) from each source s i ∈ S , with O (√σ ċ n 3/2) edges, and, on the other hand, there exist n -vertex graphs with source sets S ⊆ V of cardinality σ, on which any FT-MBFS structure from S has Ω(√σ ċ n 3/2 ) edges. Finally, we propose an O (log n ) approximation algorithm for constructing FT-BFS and FT-MBFS structures. The latter is complemented by a hardness result stating that there exists no Ω(log n ) approximation algorithm for these problems under standard complexity assumptions. In comparison with previous constructions, our algorithm is deterministic and may improve the number of edges by a factor of up to √ n for some instances. All our algorithms can be extended to deal with one vertex failure as well, with the same performance.

Is there a bias in paper selection processes for conferences? This work addresses one aspect of this question, and empirically examines if there is a bias in favor of the collaborators of the technical program committee members. Specifically, we check whether a paper written by a past collaborator of a program committee member is more likely to be accepted to the conference. If so, one might say that the program committee members were biased; if not, then they are fair. In order to answer the bias question, we studied 12 ACM/IEEE conferences over several years. For each annual meeting of a conference we constructed its social network, whose vertices are the program committee members and the authors of the papers accepted to the meeting. Two researchers are collaborators (neighbors in the network) if they have co-authored a paper before the meeting. In turn, for each meeting network, we calculated the coverage of the program committee in the network, which is the ratio between the number of authors that are collaborators of the program committee, and the total number of the authors-vertices of the meeting. We compared the coverage of the real meeting's social networks, to the coverage in artificially generated meetings (random and others). We view a program committee as coverage biased if its coverage is significantly higher than that of corresponding artificially generated meetings of the conference. Our findings show that, although there are some coverage biased program committees, in most meetings, the coverage in the real meetings is the same as, and sometimes less than, the artificially generated ones, indicating that on average there is probably no bias in favor of papers written by collaborators of the program committee members for these high quality conferences.

Theoretical study of optimization problems in wireless communication often deals with zero-dimensional tasks. For example, the power control problem requires computing a power assignment guaranteeing that each transmitting station is successfully received at a single receiver point. This paper aims at addressing communication applications that require handling 2-dimensional tasks (e.g., Guaranteeing successful transmission in entire regions rather than in specific points). A natural approach to such tasks is to discretize the 2-dimensional optimization domain, e.g., By sampling points within the domain. This approach, however, might incur high time and memory requirements, and moreover, it cannot guarantee exact solutions. Towards this goal, we establish the minimum principle for the SINR function with free-space path loss (i.e., When the signal decays in proportion to the square of the distance between the transmitter and receiver). We then utilize it as a discretization technique for solving two-dimensional problems in the SINR model. This approach is shown to be useful for handling optimization problems over two dimensions (e.g., Power control, energy minimization), in providing tight bounds on the number of null-cells in the reception map, and in approximating geometrical and topological properties of the wireless reception map (e.g., Maximum inscribed sphere). Essentially, the minimum principle allows us to reduce the dimension of the optimization domain without losing anything in the accuracy or quality of the solution. More specifically, when the two dimensional optimization domain is bounded and free from any interfering station, the minimum principle implies that it is sufficient to optimize over the boundary of the domain, as the "hardest" points to be satisfied reside on boundary and not in the interior. We believe that the minimum principle, as well as the interplay between continuous and discrete analysis presented in this paper, may pave the way to future study of algorithmic SINR in higher dimensions.

The glass ceiling effect has been defined in a recent US Federal Commission report as "the unseen, yet unbreakable barrier that keeps minorities and women from rising to the upper rungs of the corporate ladder, regardless of their qualifications or achievements". It is well documented that many societies and organizations exhibit a glass ceiling. In this paper we formally define and study the glass ceiling effect in social networks and propose a natural mathematical model, called the biased preferential attachment model, that partially explains the causes of the glass ceiling effect. This model consists of a network composed of two types of vertices, representing two sub-populations, and accommodates three well known social phenomena: (i) the "rich get richer" mechanism, (ii) a minority-majority partition, and (iii) homophily. We prove that our model exhibits a strong moment glass ceiling effect and that all three conditions are necessary, i.e., removing any one of them will prevent the appearance of a glass ceiling effect. Additionally, we present empirical evidence taken from a mentor-student network of researchers (derived from the DBLP database) that exhibits both a glass ceiling effect and the above three phenomena.

This paper initiates the study of fault resilient network structures that mix two orthogonal protection mechanisms:(a) backup, namely, augmenting the structure with many (redundant) low-cost but fault-prone components, and (b) reinforcement, namely, acquiring high-cost but fault-resistant components. To study the trade-off between these two mechanisms in a concrete setting, we address the problem of designing a (b,r) fault-tolerant BFS (or (b,r) FT-BFS for short) structure,namely, a subgraph H of the network G consisting of two types of edges: a set E' ⊆ E of r(n) fault-resistant reinforcement edges, which are assumed to never fail, and a (larger) set E(H) \ E' of b(n) fault-prone backup edges, such that subsequent to the failure of a single fault-prone backup edge e ∈ E \ E', the surviving part of H still contains a BFS spanning tree for (the surviving part of) G, satisfying dist(s,v,H\{e}) ≤ dist(s,v,G \{e}) for every v ∈ V and e ∈ E \ E'.We establish the following tradeoff: For every real ε ∈ (0,1], if r(n) = Θ(n1-ε),then b(n) = Θ(n{1+ε) is necessary and sufficient.More specifically, as shown in ESA'13, for ε=1, FT-BFS structures (with no reinforced edges) require Θ(n3/2) edges, and this is sufficient. At the other extreme, if ε=0, then n-1 reinforced edges suffice (with no need for backup). Here, we present a polynomial time algorithm that given an undirected graph G=(V,E), a source vertex s and a real ε ∈ (0,1], constructs a (b(n),r(n)) FT-BFS with r(n) = O(n1-ε) and b(n) = O(min{1/ε • n1+ε • log n, n3/2). We complement this result by providing a nearly matching lower bound, showing that there are n-vertex graphs for which any (b(n),r(n)) FT-BFS structure requires Ω(min{n{1+ε, n3/2}) backup edges when r(n)=Ω(n1-ε) edges are reinforced.

This article studies the topological properties of wireless communication maps and their usability in algorithmic design. We consider the SINR model, which compares the received power of a signal at a receiver against the sum of strengths of other interfering signals plus background noise. To describe the behavior of a multistation network, we use the convenient representation of a reception map, which partitions the plane into reception zones, one per station, and the complementary region of the plane where no station can be heard. SINR diagrams have been studied in Avin et al. [2009] for the specific case where all stations use the same power. It was shown that the reception zones are convex (hence connected) and fat, and this was used to devise an efficient algorithm for the fundamental problem of point location. Here we consider the more general (and common) case where transmission energies are arbitrary (or nonuniform). Under that setting, the reception zones are not necessarily convex or even connected. This poses the algorithmic challenge of designing efficient point location techniques for the nonuniform setting, as well as the theoretical challenge of understanding the geometry of SINR diagrams (e.g., the maximal number of connected components they might have). Our key result exhibits a striking contrast between d - and ( d +1)-dimensional maps for a network embedded in d -dimensional space. Specifically, it is shown that whereas the d -dimensional map might be highly fractured, drawing the map in one dimension higher “heals” the zones, which become connected (in fact, hyperbolically connected). We also provide bounds for the fatness of reception zones. Subsequently, we consider algorithmic applications and propose a new variant of approximate point location.

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.

A fault-tolerant structure for a network is required to continue functioning following the failure of some of the network's edges or vertices. This paper addresses the problem of designing a fault-tolerant (α, β) approximate BFS structure (or FT-ABFS structure for short), namely, a subgraph H of the network G such that subsequent to the failure of some subset F of edges or vertices, the surviving part of H still contains an approximate BFS spanning tree for (the surviving part of) G, satisfying dist(s, v, H\F) ≤ α-dist(s, v, G\F)+β for every v ∊ V. We first consider multiplicative (α, 0) FT-ABFS structures resilient to a failure of a single edge or vertex, and present an algorithm that given an n-vertex unweighted undirected graph G and a source s constructs a (3,0) FT-ABFS structure rooted at s with at most 3n edges (improving by an O(logn) factor on the near-tight result of [3]). Assuming at most f edge failures, for constant integer f > 1, we prove that there exists a (poly-time constructible) (3(f +1), (f +1) logn) FT-ABFS structure with O(fn) edges. We then consider additive (1, β) FT-ABFS structures. In contrast to the linear size of (α, 0) FT-ABFS structures, we show that for every β ∊ [1,O(logn)] there exists an n-vertex graph G with a source s for which any (1, β) FT-ABFS structure rooted at s has Ω(n1+∊(β)) edges, for some function ∊(β) ∊ (0,1). In particular, (1,3) FT-ABFS structures admit a lower bound of Ω(n5/4) edges. These lower bounds demonstrate an interesting dichotomy between multiplicative and additive spanners; whereas (α, 0) FT-ABFS structures of size O(n) exist (for α ≥ 3), their additive counterparts, (1,β) FT-ABFS structures, are of super-linear size. Our lower bounds are complemented by an upper bound, showing that there exists a poly-time algorithm that for every n-vertex unweighted undirected graph G and source s constructs a (1,4) FT-ABFS structure rooted at s with at most O(n4/3) edges.

A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, have to meet at the same node. Agents move in synchronous rounds. Each agent has a different label. Up to f of the agents are Byzantine. We consider two levels of Byzantine behavior. A strongly Byzantine agent can choose an arbitrary port when it moves and it can convey arbitrary information to other agents, while a weakly Byzantine agent can do the same, except changing its label. What is the minimum number of good agents that guarantees deterministic gathering of all of them, with termination? We solve exactly this Byzantine gathering problem in arbitrary networks for weakly Byzantine agents and give approximate solutions for strongly Byzantine agents, both when the size of the network is known and when it is unknown. It turns out that both the strength versus the weakness of Byzantine behavior and the knowledge of network size significantly impact the results. For weakly Byzantine agents, we show that any number of good agents permits solving the problem for networks of known size. If the size is unknown, then this minimum number is f +2. More precisely, we show a deterministic polynomial algorithm that gathers all good agents in an arbitrary network, provided that there are at least f +2 of them. We also provide a matching lower bound: we prove that if the number of good agents is at most f +1, then they are not able to gather deterministically with termination in some networks. For strongly Byzantine agents, we give a lower bound of f +1, even when the graph is known: we show that f good agents cannot gather deterministically in the presence of f Byzantine agents even in a ring of known size. On the positive side, we give deterministic gathering algorithms for at least 2 f +1 good agents when the size of the network is known and for at least 4 f +2 good agents when it is unknown.

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 paper 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. The "obvious" lower bounds of Ω(m) messages (m is the number of edges in the network) and Ω(D) time (D is the network diameter) are non-trivial to show for randomized (Monte Carlo) algorithms. (Recent results that show that even Ω(n) (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 limited case of comparison algorithms, where it was also required that some nodes may not wake up spontaneously, and that D and n were not known).

Given a simple graph G=(V,E) and a set of sources S ⊆ V, denote for each node ν ε V by Lν(∞) the lexicographically ordered list of distance/source pairs (d(s,v),s), where s ∈ S. For integers d,k ∈ N∪{∞}, we consider the source detection, or (S,d,k)-detection task, requiring each node v to learn the first k entries of Lν(∞) (if for all of them d(s,v) ≤ d) or all entries (d(s,v),s) ∈ Lν(∞) satisfying that d(s,v) ≤ d (otherwise). Solutions to this problem provide natural generalizations of concurrent breadth-first search (BFS) tree constructions. For example, the special case of k=∞ requires each source s ∈ S to build a complete BFS tree rooted at s, whereas the special case of d=∞ and S=V requires constructing a partial BFS tree comprising at least k nodes from every node in V.

The celebrated Perron–Frobenius (PF) theorem is stated for irreducible nonnegative square matrices, and provides a simple characterization of their eigenvectors and eigenvalues. The importance of this theorem stems from the fact that eigenvalue problems on such matrices arise in many fields of science and engineering, including dynamical systems theory, economics, statistics and optimization. However, many real-life scenarios give rise to nonsquare matrices. Despite the extensive development of spectral theories for nonnegative matrices, the applicability of such theories to non-convex optimization problems is not clear. In particular, a natural question is whether the PF Theorem (along with its applications) can be generalized to a nonsquare setting. Our paper provides a generalization of the PF Theorem to nonsquare multiple choice matrices. The extension can be interpreted as representing systems with additional degrees of freedom, where each client entity may choose between multiple servers that can cooperate in serving it (while potentially interfering with other clients). This formulation is motivated by applications to power control in wireless networks, economics and others, all of which extend known examples for the use of the original PF Theorem. We show that the option of cooperation does not improve the situation, in the sense that in the optimum solution, no cooperation is needed, and only one server per client entity needs to work. Hence, the additional power of having several potential servers per client translates into choosing the “best” single server and not into sharing the load between the servers in some way, as one might have expected. The two main contributions of the paper are (i) a generalized PF Theorem that characterizes the optimal solution for a non-convex problem, and (ii) an algorithm for finding the optimal solution in polynomial time. In addition, we extend the definitions of irreducibility and largest eigenvalue of square matrices to nonsquare ones in a novel and non-trivial way, which turns out to be necessary and sufficient for our generalized theorem to hold. To characterize the optimal solution, we use techniques from a wide range of areas. In particular, the analysis exploits combinatorial properties of polytopes, graph-theoretic techniques and analytic tools such as spectral properties of nonnegative matrices and root characterization of integer polynomials.

A central theme in distributed network algorithms concerns understanding and coping with the issue of locality . Yet despite considerable progress, research efforts in this direction have not yet resulted in a solid basis in the form of a fundamental computational complexity theory for locality. Inspired by sequential complexity theory, we focus on a complexity theory for distributed decision problems . In the context of locality, solving a decision problem requires the processors to independently inspect their local neighborhoods and then collectively decide whether a given global input instance belongs to some specified language. We consider the standard LOCAL model of computation and define LD( t ) (for local decision ) as the class of decision problems that can be solved in t communication rounds. We first study the intriguing question of whether randomization helps in local distributed computing, and to what extent. Specifically, we define the corresponding randomized class BPLD( t , p , q ), containing all languages for which there exists a randomized algorithm that runs in t rounds, accepts correct instances with probability at least p , and rejects incorrect ones with probability at least q . We show that p 2 + q = 1 is a threshold for the containment of LD( t ) in BPLD( t , p , q ). More precisely, we show that there exists a language that does not belong to LD( t ) for any t = o ( n ) but does belong to BPLD( 0 , p , q ) for any p , q ∈ (0,1) such that p 2 + q ≤ 1. On the other hand, we show that, restricted to hereditary languages, BPLD( t , p , q )=LD( O ( t )), for any function t , and any p , q ∈ (0,1) such that p 2 + q > 1. In addition, we investigate the impact of nondeterminism on local decision, and establish several structural results inspired by classical computational complexity theory. Specifically, we show that nondeterminism does help, but that this help is limited, as there exist languages that cannot be decided locally nondeterministically. Perhaps surprisingly, it turns out that it is the combination of randomization with nondeterminism that enables to decide all languages in constant time . Finally, we introduce the notion of local reduction, and establish a couple of completeness results.

This paper studies the reception zones of a wireless network in the SINR model with receivers that employ interference cancellation (IC). IC is a recently developed technique that allows a receiver to decode interfering signals, and cancel them from the received signal in order to decode its intended message. We first derive the important topological properties of the reception zones and their relation to high-order Voronoi diagrams and other geometric objects. We then discuss the computational issues that arise when seeking an efficient description of the zones. Our main fundamental result states that although potentially there are exponentially many possible cancellation orderings, and as a result, reception zones, in fact there are much fewer nonempty such zones. We prove a linear bound (hence tight) on the number of zones and provide a polynomial time algorithm to describe the diagram. Moreover, we introduce a novel parameter, the Compactness Parameter, which influences the tightness of our bounds. We then utilize these properties to devise a logarithmic time algorithm to answer point-location queries for networks with IC.

A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, have to meet at the same node. Agents move in synchronous rounds. Each agent has a different label. Up to f of the agents are Byzantine. We consider two levels of Byzantine behavior. A strongly Byzantine agent can choose an arbitrary port when it moves and it can convey arbitrary information to other agents, while a weakly Byzantine agent can do the same, except changing its label. What is the minimum number of good agents that guarantees deterministic gathering of all of them, with termination? We solve exactly this Byzantine gathering problem in arbitrary networks for weakly Byzantine agents, and give approximate solutions for strongly Byzantine agents, both when the size of the network is known and when it is unknown. It turns out that both the strength versus weakness of Byzantine behavior and the knowledge of network size significantly impact the results. For weakly Byzantine agents we show that any number of good agents permit to solve the problem for networks of known size. If the size is unknown, then this minimum number is f + 2. More precisely, we show a deterministic polynomial algorithm that gathers all good agents in an arbitrary network, provided that there are at least f + 2 of them. We also provide a matching lower bound: we prove that if the number of good agents is at most f + 1, then they are not able to gather deterministically with termination in some networks. For strongly Byzantine agents we give a lower bound of f + 1, even when the graph is known: we show that f good agents cannot gather deterministically in the presence of f Byzantine agents even in a ring of known size. On the positive side we give deterministic gathering algorithms for at least 2f + 1 good agents when the size of the network is known, and for at least 4f + 2 good agents when it is unknown.

We study randomized gossip-based processes in dynamic networks that are motivated by information discovery in large-scale distributed networks such as peer-to-peer and social networks. A well-studied problem in peer-to-peer networks is resource discovery, where the goal for nodes (hosts with IP addresses) is to discover the IP addresses of all other hosts. Also, some of the recent work on self-stabilization algorithms for P2P/overlay networks proceed via discovery of the complete network. In social networks, nodes (people) discover new nodes through exchanging contacts with their neighbors (friends). In both cases the discovery of new nodes changes the underlying network --- new edges are added to the network --- and the process continues in the changed network. Rigorously analyzing such dynamic (stochastic) processes in a continuously changing topology remains a challenging problem with obvious applications.

The rules governing the availability and quality of connections in a wireless network are described by physical models such as the signal-to-interference & noise ratio (SINR) model. For a collection of simultaneously transmitting stations in the plane, it is possible to identify a reception zone for each station, consisting of the points where its transmission is received correctly. The resulting SINR diagram partitions the plane into a reception zone per station and the remaining plane where no station can be heard. SINR diagrams appear to be fundamental to understanding the behavior of wireless networks, and may play a key role in the development of suitable algorithms for such networks, analogous perhaps to the role played by Voronoi diagrams in the study of proximity queries and related issues in computational geometry. So far, however, the properties of SINR diagrams have not been studied systematically, and most algorithmic studies in wireless networking rely on simplified graph-based models such as the unit disk graph (UDG) model, which conveniently abstract away interference-related complications, and make it easier to handle algorithmic issues, but consequently fail to capture accurately some important aspects of wireless networks. This article focuses on obtaining some basic understanding of SINR diagrams, their properties and their usability in algorithmic applications. Specifically, we have shown that assuming uniform power transmissions, the reception zones are convex and relatively well-rounded. These results are then used to develop an efficient approximation algorithm for a fundamental point location problem in wireless networks.

We study the verification problem in distributed networks, stated as follows. Let $H$ be a subgraph of a network $G$ where each vertex of $G$ knows which edges incident on it are in $H$. We would like to verify whether $H$ has some properties, e.g., if it is a tree or if it is connected (every node knows at the end of the process whether $H$ has the specified property or not). We would like to perform this verification in a decentralized fashion via a distributed algorithm. The time complexity of verification is measured as the number of rounds of distributed communication. In this paper we initiate a systematic study of distributed verification and give almost tight lower bounds on the running time of distributed verification algorithms for many fundamental problems such as connectivity, spanning connected subgraph, and $s$-$t$ cut verification. We then show applications of these results in deriving strong unconditional time lower bounds on the hardness of distributed approximation for many classical optimization problems including minimum spanning tree (MST), shortest paths, and minimum cut. Many of these results are the first nontrivial lower bounds for both exact and approximate distributed computation, and they resolve previous open questions. Moreover, our unconditional lower bound of approximating MST subsumes and improves upon the previous hardness of approximation bound of Elkin [M. Elkin, SIAM J. Comput., 36 (2006), pp. 433--456] as well as the lower bound for (exact) MST computation of Peleg and Rubinovich [D. Peleg and V. Rubinovich, SIAM J. Comput., 30 (2000), pp. 1427--1442]. Our result implies that there can be no distributed approximation algorithm for MST that is significantly faster than the current exact algorithm for any approximation factor. Our lower bound proofs show an interesting connection between communication complexity and distributed computing which turns out to be useful in establishing the time complexity of exact and approximate distributed computation of many problems.

A central theme in distributed network algorithms concerns understanding and coping with the issue of locality. Despite considerable progress, research efforts in this direction have not yet resulted in a solid basis in the form of a fundamental computational complexity theory for locality. Inspired by sequential complexity theory, we focus on a complexity theory for distributed decision problems. In the context of locality, solving a decision problem requires the processors to independently inspect their local neighborhoods and then collectively decide whether a given global input instance belongs to some specified language. We consider the standard LOCAL model of computation and define LD(t) (for local decision) as the class of decision problems that can be solved in t communication rounds. We first study the intriguing question of whether randomization helps in local distributed computing, and to what extent. Specifically, we define the corresponding randomized class BPLD(t,p,q), containing all languages for which there exists a randomized algorithm that runs in t rounds, accepts correct instances with probability at least p and rejects incorrect ones with probability at least q. We show that p2+q = 1 is a threshold for the containment of LD(t) in BPLD(t,p,q). More precisely, we show that there exists a language that does not belong to LD(t) for any t=o(n) but does belong to BPLD(0,p,q) for any p,q ∈ (0,1] such that p2+q≤1. On the other hand, we show that, restricted to hereditary languages, BPLD(t,p,q) = LD(O(t)), for any function t and any p,q ∈ (0,1] such that p2+q>;1. In addition, we investigate the impact of non-determinism on local decision, and establish some structural results inspired by classical computational complexity theory. Specifically, we show that non-determinism does help, but that this help is limited, as there exist languages that cannot be decided non-deterministically. Perhaps surprisingly, it turns out that it is the combination of randomization with non-determinism that enables to decide all languages in constant time. Finally, we introduce the notion of local reduction, and establish some completeness results.

The power control problem for wireless networks in the SINR model requires determining the optimal power assignment for a set of communication requests such that the SINR threshold is met for all receivers. If the network topology is known to all participants, then it is possible to compute an optimal power assignment in polynomial time. In realistic environments, however, such global knowledge is usually not available to every node. In addition, protocols that are based on global computation cannot support mobility and hardly adapt when participants dynamically join or leave the system. In this paper we present and analyze a fully distributed power control protocol that is based on local information. For a set of communication pairs, each consisting of a sender node and a designated receiver node, the algorithm enables the nodes to converge to the optimal power assignment (if there is one under the given constraints) quickly with high probability. Two types of bounded resources are considered, namely, the maximal transmission energy and the maximum distance between any sender and receiver. It is shown that the restriction to local computation increases the convergence rate by only a multiplicative factor of O(log n + log log Ψmax), where Ψmaxis the maximal power constraint of the network. If the diameter of the network is bounded by Lmaxthen the increase in convergence rate is given by O(log n + log log Lmax).

This paper establishes tight bounds for the Minimum-weight Spanning Tree (MST) verification problem in the distributed setting. Specifically, we provide an MST verification algorithm that achieves simultaneously tilde ~O(|E|) messages and $tilde O(sqrt{n} + D) time, where |E| is the number of edges in the given graph G and D is G's diameter. On the negative side, we show that any MST verification algorithm must send Omega(|E|) messages and incur ~Omega(sqrt{n} + D) time in worst case. Our upper bound result appears to indicate that the verification of an MST may be easier than its construction, since for MST construction, both lower bounds of Omega(|E|) messages and Omega(sqrt{n} + D) time hold, but at the moment there is no known distributed algorithm that constructs an MST and achieves simultaneously tilde O(|E|) messages and ´~O(sqrt{n} + D) time. Specifically, the best known time-optimal algorithm (using ~O(sqrt{n} + D) time) requires O(|E|+n^{3/2}) messages, and the best known message-optimal algorithm (using ~O(|E|) messages) requires O(n) time. On the other hand, our lower bound results indicate that the verification of an MST is not significantly easier than its construction.

In this paper we study the topological properties of wireless communication maps and their usability in algorithmic design. We consider the SINR model, which compares the received power of a signal at a receiver against the sum of strengths of other interfering signals plus background noise. To describe the behavior of a multi-station network, we use the convenient representation of a reception map. In the SINR model, the resulting SINR diagram partitions the plane into reception zones, one per station, and the complementary region of the plane where no station can be heard. SINR diagrams have been studied in [3] for the specific case where all stations use the same power. It is shown that the reception zones are convex (hence connected) and fat, and this is used to devise an efficient algorithm for the fundamental problem of point location. Here we consider the more general (and common) case where transmission energies are arbitrary (or non-uniform). Under that setting, the reception zones are not necessarily convex or even connected. This poses the algorithmic challenge of designing efficient point location techniques for the non-uniform setting, as well as the theoretical challenge of understanding the geometry of SINR diagrams (e.g., the maximal number of connected components they might have). We achieve several results in both directions. We establish a form of weaker convexity in the case where stations are aligned on a line and use this to derive a tight bound on the number of connected components in this case. In addition, one of our key results concerns the behavior of a (d+1)-dimensional map, i.e., a map in one dimension higher than the dimension in which stations are embedded. Specifically, although the d-dimensional map might be highly fractured, drawing the map in one dimension higher "heals" the zones, which become connected (in fact hyperbolically connected). In addition, as a step toward establishing a weaker form of convexity for the d-dimensional map, we study the interference function and show that it satisfies the maximum principle. This is done through an analysis technique based on looking at the behavior of systems composed on lines of densely placed weak stations, as the number of stations tends to infinity, keeping their total transmission energy fixed. Finally, we turn to consider algorithmic applications, and propose a new variant of approximate point location.

We study the verification problem in distributed networks, stated as follows. Let H be a subgraph of a network G where each vertex of G knows which edges incident on it are in H. We would like to verify whether H has some properties, e.g., if it is a tree or if it is connected (every node knows in the end of the process whether H has the specified property or not). We would like to perform this verification in a decentralized fashion via a distributed algorithm. The time complexity of verification is measured as the number of rounds of distributed communication.

The paper proposes a forbidden-set labeling scheme for the family of graphs with doubling dimension bounded by α. For an n-vertex graph G in this family, and for any desired precision parameter ε > 0, the labeling scheme stores an O(1+α-1)2α log2 n-bit label at each vertex. Given the labels of two end-vertices s and t, and the labels of a set F of "forbidden" vertices and/or edges, our scheme can compute, in time polynomial in the length of the labels, a 1+ε stretch approximation for the distance between s and t in the graph GF. The labeling scheme can be extended into a forbidden-set labeled routing scheme with stretch 1 + ε for graphs of bounded doubling dimension.

In the {\em uncapacitated facility location} problem, given a graph, a set of demands and opening costs, it is required to find a set of facilities $R$, so as to minimize the sum of the cost of opening the facilities in $R$ and the cost of assigning all node demands to open facilities. This paper concerns the {\em robust fault-tolerant} version of the uncapacitated facility location problem (RFTFL). In this problem, one or more facilities might fail, and each demand should be supplied by the closest open facility that did not fail. It is required to find a set of facilities $R$, so as to minimize the sum of the cost of opening the facilities in $R$ and the cost of assigning all node demands to open facilities that did not fail, after the failure of up to $\alpha$ facilities. We present a polynomial time algorithm that yields a 6.5-approximation for this problem with at most one failure and a $1.5 + 7.5\alpha$-approximation for the problem with at most $\alpha > 1$ failures. We also show that the $RFTFL$ problem is NP-hard even on trees, and even in the case of a single failure.

Let $(V,\delta)$ be a finite metric space, where $V$ is a set of $n$ points and $\delta$ is a distance function defined for these points. Assume that $(V,\delta)$ has a constant doubling dimension $d$ and assume that each point $p\in V$ has a disk of radius $r(p)$ around it. The disk graph that corresponds to $V$ and $r(\cdot)$ is a \emph{directed} graph $I(V,E,r)$, whose vertices are the points of $V$ and whose edge set includes a directed edge from $p$ to $q$ if $\delta(p,q)\leq r(p)$. In~\cite{PeRo08} we presented an algorithm for constructing a $(1+\eps)$-spanner of size $O(n/\eps^d \log M)$, where $M$ is the maximal radius $r(p)$. The current paper presents two results. The first shows that the spanner of~\cite{PeRo08} is essentially optimal, i.e., for metrics of constant doubling dimension it is not possible to guarantee a spanner whose size is independent of $M$. The second result shows that by slightly relaxing the requirements and allowing a small perturbation of the radius assignment, considerably better spanners can be constructed. In particular, we show that if it is allowed to use edges of the disk graph $I(V,E,r_{1+\eps})$, where $r_{1+\eps}(p) = (1+\eps)\cdot r(p)$ for every $p\in V$, then it is possible to get a $(1+\eps)$-spanner of size $O(n/\eps^d)$ for $I(V,E,r)$. Our algorithm is simple and can be implemented efficiently.

This paper concerns graph spanners that are resistant to vertex or edge failures. In the failure-free setting, it is known how to efficiently construct a $(2k-1)$-spanner of size $O(n^{1+1/k})$, and this size-stretch trade-off is conjectured to be tight. The notion of fault tolerant spanners was introduced a decade ago in the geometric setting [C. Levcopoulos, G. Narasimhan, and M. Smid, in Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 186–195]. A subgraph H is an f-vertex fault tolerant k-spanner of the graph G if for any set $F\subseteq V$ of size at most f and any pair of vertices $u,v\in V\setminus F$, the distances in H satisfy $\delta_{H\setminus F}(u,v)\leq k\cdot\delta_{G\setminus F}(u,v)$. A fault tolerant geometric spanner with optimal maximum degree and total weight was presented in [A. Czumaj and H. Zhao, Discrete Comput. Geom., 32 (2004), pp. 207–230]. This paper also raised as an open problem the question of whether it is possible to obtain a fault tolerant spanner for an arbitrary undirected weighted graph. The current paper answers this question in the affirmative, presenting an f-vertex fault tolerant $(2k-1)$-spanner of size $O(f^{2}k^{f+1}\cdot n^{1+1/k}\log^{1-1/k}n)$. Interestingly, the stretch of the spanner remains unchanged, while the size of the spanner increases only by a factor that depends on the stretch k, on the number of potential faults f, and on logarithmic terms in n. In addition, we consider the simpler setting of f-edge fault tolerant spanners (defined analogously). We present an f-edge fault tolerant $(2k-1)$-spanner with edge set of size $O(f\cdot n^{1+1/k})$ (only f times larger than standard spanners). For both edge and vertex faults, our results are shown to hold when the given graph G is weighted.

Let ( G = ( V(G) , E(G) )) be a directed graph with nonnegative edge lengths and let P be a shortest path from s to t in G . In the replacement paths problem we are required to compute for every edge e in P , the length of a shortest path from s to t that avoids e . The fastest known algorithm for solving the problem in weighted directed graphs is the trivial one: each edge in P is removed from the graph in its turn and the distance from s to t in the modified graph is computed. The running time of this algorithm is O ( m n + n 2 log n ), where n = | V(G) | and m = | E(G) |. The replacement paths problem is strongly motivated by two different applications. First, the fastest algorithm to compute the k simple shortest paths from s to t in directed graphs [Yen 1971; Lawler 1972] repeatedly computes the replacement paths from s to t . Its running time is O ( kn ( m + n log n )). Second, the computation of Vickrey pricing of edges in distributed networks can be reduced to the replacement paths problem. An open question raised by Nisan and Ronen [2001] asks whether it is possible to compute the Vickrey pricing faster than the trivial algorithm described in the previous paragraph. In this article we present a near-linear time algorithm for computing replacement paths in weighted planar directed graphs. In particular, the algorithm computes the lengths of the replacement paths in O ( n log 3 n ) time (recall that in planar graphs m = O ( n )). This result immediately improves the running time of the two applications mentioned before by almost a linear factor. Our algorithm is obtained by combining several new ideas with a data structure of Klein [2005] that supports multisource shortest paths queries in planar directed graphs in logarithmic time. Our algorithm can be adapted to address the variant of the problem in which one is interested in the replacement path itself (rather than the length of the path). In that case the algorithm is executed in a preprocessing stage constructing a data structure that supports replacement path queries in time Õ ( h ), where h is the number of hops in the replacement path. In addition, we can handle the variant in which vertices should be avoided instead of edges.

This article presents an algorithm for constructing a spanner for ad hoc networks whose nodes have variable transmission range. Almost all previous spanner constructions for ad hoc networks assumed that all nodes in the network have the same transmission range. This allowed a succinct representation of the network as a unit disk graph, serving as the basis for the construction. In contrast, when nodes have variable transmission range, the ad hoc network must be modeled by a general disk graph. Whereas unit disk graphs are undirected, general disk graphs are directed. This complicates the construction of a spanner for the network, since currently there are no efficient constructions of low-stretch spanners for general directed graphs. Nevertheless, in this article it is shown that the class of disk graphs enjoys (efficiently constructible) spanners of quality similar to that of unit disk graph spanners. Moreover, it is shown that the new construction can be performed in a localized fashion. Our results use only simple packing arguments, hence all algorithms work for every metric space of constant doubling dimension.

The rules governing the availability and quality of connections in a wireless network are described by physical models such as the signal-to-interference & noise ratio (SINR) model. For a collection of simultaneously transmitting stations in the plane, it is possible to identify a reception zone for each station, consisting of the points where its transmission is received correctly. The resulting SINR diagram partitions the plane into a reception zone per station and the remaining plane where no station can be heard.

The paper concerns graph spanners that are resistant to vertex or edge failures. Given a weighted undirected n-vertex graph G=(V,E) and an integer k ≥ 1, the subgraph H=(V,E'), E'⊆ E, is a spanner of stretch k (or, a k-spanner) of G if δH(u,v) ≤ k· δG(u,v) for every u,v ∈ V, where δG'(u,v) denotes the distance between u and v in G'. Graph spanners were extensively studied since their introduction over two decades ago. It is known how to efficiently construct a (2k-1)-spanner of size O(n1+1/k), and this size-stretch tradeoff is conjectured to be tight.

We prove that every unweighted series-parallel graph can be probabilistically embedded into its spanning trees with logarithmic distortion. This is tight due to an $\Omega(\log n)$ lower bound established by Gupta, Newman, Rabinovich, and Sinclair on the distortion required to probabilistically embed the n-vertex diamond graph into a collection of dominating trees. Our upper bound is gained by presenting a polynomial time probabilistic algorithm that constructs spanning trees with low expected stretch. This probabilistic algorithm can be derandomized to yield a deterministic polynomial time algorithm for constructing a spanning tree of a given (unweighted) series-parallel graph G, whose communication cost is at most $O(\log n)$ times larger than that of G.

The paper presents a deterministic distributed algorithm that, given k ≥ 1, constructs in k rounds a (2k-1,0)-spanner of O(k n1+1/k) edges for every n-node unweighted graph. (If n is not available to the nodes, then our algorithm executes in 3k-2 rounds, and still returns a (2k-1,0)-spanner with O(k n1+1/k) edges.) Previous distributed solutions achieving such optimal stretch-size trade-off either make use of randomization providing performance guarantees in expectation only, or perform in logΩ(1)n rounds, and all require a priori knowledge of n. Based on this algorithm, we propose a second deterministic distributed algorithm that, for every ε > 0, constructs a (1+ε,2)-spanner of O(ε-1 n3/2) edges in O(ε-1) rounds, without any prior knowledge on the graph.

The paper studies broadcasting in radio networks whose stations are represented by points in the Euclidean plane. In any given time step, a station can either receive or transmit. A message transmitted from station (v) is delivered to every station (u) at distance at most (1) from (v), but (u) successfully hears the message if and only if (v) is the only station at distance at most (1) from (u) that transmitted in this time step. A designated source station has a message that should be disseminated throughout the network. All stations other than the source are initially idle and wake up upon the first time they hear the source message.

A number of recent studies concern algorithms for distributed control and coordination in systems of autonomous mobile robots. The common theoretical model adopted in these studies assumes that the positional input of the robots is obtained by perfectly accurate visual sensors, that robot movements are accurate, and that internal calculations performed by the robots on (real) coordinates are perfectly accurate as well. The current paper concentrates on the effect of weakening this rather strong set of assumptions and replacing it with the more realistic assumption that the robot sensors, movement, and internal calculations may have slight inaccuracies. Specifically, the paper concentrates on the ability of robot systems with inaccurate sensors, movements, and calculations to carry out the task of convergence. The paper presents several impossibility theorems, limiting the inaccuracy levels that still allow convergence, and prohibiting a general algorithm for gathering, namely, meeting at a point, in a finite number of steps. The main positive result is an algorithm for convergence under bounded measurement, movement, and calculation errors.

Given a graph \(G\) and a spanning tree \(T\) of \(G\), we say that \(T\) is a tree \(t\)-spanner of \(G\) if the distance between every pair of vertices in \(T\) is at most \(t\) times their distance in \(G\). The problem of finding a tree \(t\)-spanner minimizing \(t\) is referred to as the Minimum Max-Stretch spanning Tree (MMST) problem. This paper concerns the MMST problem on unweighted graphs. The problem is known to be NP-hard, and the paper presents an \(O(\log n)\)-approximation algorithm for it. Furthermore, it is established that unless \(\mathrm{P}=\mathrm{NP}\), the problem cannot be approximated additively by any \(o(n)\) term.

A finite automaton, simply referred to as a robot , has to explore a graph, that is, visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph, nor of its size. It is known that for any k -state robot, there exists a graph of maximum degree 3 that the robot cannot explore. This article considers the effects of allowing the system designer to add short labels to the graph nodes in a preprocessing stage, for helping the exploration by the robot. We describe an exploration algorithm that, given appropriate 2-bit labels (in fact, only 3-valued labels), allows a robot to explore all graphs. Furthermore, we describe a suitable labeling algorithm for generating the required labels in linear time. We also show how to modify our labeling scheme so that a robot can explore all graphs of bounded degree, given appropriate 1-bit labels. In other words, although there is no robot able to explore all graphs of maximum degree 3, there is a robot R, and a way to color in black or white the nodes of any bounded-degree graph G , so that R can explore the colored graph G . Finally, we give impossibility results regarding graph exploration by a robot with no internal memory (i.e., a single-state automaton).

This article studies approximate distributed routing schemes on dynamic communication networks. The work focuses on dynamic weighted general graphs where the vertices of the graph are fixed, but the weights of the edges may change. Our main contribution concerns bounding the cost of adapting to dynamic changes. The update efficiency of a routing scheme is measured by the time needed in order to update the routing scheme following a weight change. A naive dynamic routing scheme, which updates all vertices following a weight change, requires Ω( Diam ) time in order to perform the updates after every weight change, where Diam is the diameter of the underlying graph. In contrast, this article presents approximate dynamic routing schemes with average time complexity Θ˜( D ) per topological change, where D is the local density parameter of the underlying graph. Following a weight change, our scheme never incurs more than Diam time; thus, our scheme is particularly efficient on graphs which have low local density and large diameter. The article also establishes upper and lower bounds on the size of the databases required by the scheme at each site.

We consider broadcasting in radio networks, modeled as unit disk graphs (UDG). Such networks occur in wireless communication between sites (e.g., stations or sensors) situated in a terrain. Network stations are represented by points in the Euclidean plane, where a station is connected to all stations at distance at most 1 from it. A message transmitted by a station reaches all its neighbors, but a station hears a message (receives the message correctly) only if exactly one of its neighbors transmits at a given time step. One station of the network, called the source, has a message which has to be disseminated to all other stations. Stations are unaware of the network topology. Two broadcasting models are considered. In the conditional wake up model, the stations other than the source are initially idle and cannot transmit until they hear a message for the first time.In the spontaneous wake up model, all stations are awake (and may transmit messages) from the beginning.

Consider a website containing a collection of webpages with data such as in Yahoo or the Open Directory project. Each page is associated with a weight representing the frequency with which that page is accessed by users. In the tree hierarchy representation, accessing each page requires the user to travel along the path leading to it from the root. By enhancing the index tree with additional edges (hotlinks) one may reduce the access cost of the system. In other words, the hotlinks reduce the expected number of steps needed to reach a leaf page from the tree root, assuming that the user knows which hotlinks to take. The hotlink enhancement problem involves finding a set of hotlinks minimizing this cost. This article proposes the first exact algorithm for the hotlink enhancement problem. This algorithm runs in polynomial time for trees with logarithmic depth. Experiments conducted with real data show that significant improvement in the expected number of accesses per search can be achieved in websites using this algorithm. These experiments also suggest that the simple and much faster heuristic proposed previously by Czyzowicz et al. [2003] creates hotlinks that are nearly optimal in the time savings they provide to the user. The version of the hotlink enhancement problem in which the weight distribution on the leaves is unknown is discussed as well. We present a polynomial-time algorithm that is optimal for any tree for any depth.

This paper studies fault-tolerant algorithms for the problem of gathering N autonomous mobile robots. A gathering algorithm, executed independently by each robot, must ensure that all robots are gathered at one point within finite time. In a failure-prone system, a gathering algorithm is required to successfully gather the nonfaulty robots, independently of the behavior of the faulty ones. Both crash and Byzantine faults are considered. It is first observed that most existing algorithms fail to operate correctly in a setting allowing crash failures. Subsequently, an algorithm tolerant against one crash-faulty robot in a system of three or more robots is presented. It is then observed that all known algorithms fail to operate correctly in a system prone to Byzantine faults, even in the presence of a single fault. Moreover, it is shown that in an asynchronous environment it is impossible to perform a successful gathering in a 3-robot system, even if at most one of them might fail in a Byzantine manner. Thus, the problem is studied in a fully synchronous system. An algorithm is provided in this model for gathering $N \geq 3$ robots with at most a single faulty robot, and a more general gathering algorithm is given in an N-robot system with up to f faults, where $N \geq 3f+1$.

We consider a simple model for reputation systems such as the one used by eBay. In the model there are n players, some of which may exhibit arbitrarily malicious (Byzantine) behavior, and there are m objects, some of which are bad. The goal of the honest players is to find a good object. To facilitate collaboration, the system maintains a shared billboard. A basic step of a player consists of consulting the billboard, probing an object to learn its true value, and posting the result on the billboard for the benefit of others. Probing an object incurs a unit cost to the player, and consulting the billboard is free. The dilemma of an honest player is how to balance between the desire to reduce its cost by taking advantage of the reports posted by honest peers, and the fear of being exploited by adopting reports posted by malicious players. In prior work, the authors presented an algorithm solving this problem in an asynchronous model, and the total cost of the probes made by honest players during the algorithm was analyzed. In this paper, the focus is on the individual cost, and a synchronous model in which each player takes a step in each round was considered. The prior algorithm has individual cost O(1/alphalog n) in this model, assuming that an alpha fraction of players are honest. In this paper, it is proven that no algorithm could guarantee individual cost of less than Omega(1/alpha), which is essentially constant if there are enough honest players. The main result is a new algorithm that achieves O(1) individual cost when there are many honest players, and achieves individual cost O((1/alpha)(log n/ log log n)) even when there are not. It is also shown that this algorithm generalizes to other interesting scenarios

This paper concerns the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication) in radio networks with known topology, i.e., where for each primitive the schedule of transmissions is precomputed based on full knowledge about the size and the topology of the network.The first part of the paper examines the two communication primitives in general graphs. In particular, it proposes a new (efficiently computable) deterministic schedule that uses O(D+Δ log n) time units to complete the gossiping task in any radio network with size n, diameter D and max-degree Δ. Our new schedule improves and simplifies the currently best known gossiping schedule, requiring time O(D+√[i+2]DΔ logi+1 n), for any network with the diameter D=Ω(logi+4n), where i is an arbitrary integer constant i ≥ 0, see [17]. For the broadcast task we deliver two new results: a deterministic efficient algorithm for computing a radio schedule of length D+O(log3 n), and a randomized algorithm for computing a radio schedule of length D+O(log2 n). These results improve on the best currently known D+O(log4 n) time schedule due to Elkin and Kortsarz [12].The second part of the paper focuses on radio communication in planar graphs, devising a new broadcasting schedule using fewer than 3D time slots. This result improves, for small values of D, on currently best known D+O(log3n) time schedule proposed by Elkin and Kortsarz in [12]. Our new algorithm should be also seen as the separation result between the planar and the general graphs with a small diameter due to the polylogarithmic inapproximability result in general graphs due to Elkin and Kortsarz, see [11].

This paper addresses the problem of locally verifying global properties. Several natural questions are studied, such as "how expensive is local verification?" and more specifically "how expensive is local verification compared to computation?" A suitable model is introduced in which these questions are studied in terms of the number of bits a node needs to communicate. In particular, it is shown that the cost of verification is sometimes rather high, even higher than the number of bits needed for a computation. On the other hand, approaches are presented for the efficient construction of schemes, and upper and lower bounds are established on the cost of schemes for multiple basic problems. The paper also studies the role and cost of unique identities in terms of impossibility and complexity.Previous studies on related questions deal with distributed algorithms that simultaneously compute a configuration and verify that this configuration has a certain desired property. It turns out that this combined approach enables verification to be less costly, since the configuration is typically generated so as to be easily verifiable. In contrast, our approach separates the configuration design from the verification. That is, it first generates the desired configuration without bothering with the need to verify, and then handles the task of constructing a suitable verification scheme. Our approach thus allows for a more modular design of algorithms, and has the potential to aid in verifying properties even when the original design of the structures for maintaining them was done without verification in mind.

We consider fault-tolerant broadcasting in the message passing and radio models under a probabilistic failure model. At each step, the transmitter of each node may fail independently with fixed probability p<1. We study both omission and Byzantine transmission failures. Our goal is to establish conditions on feasibility and to estimate the complexity of almost-safe broadcasting (i.e., broadcasting which is correct with probability at least 1-1/n on n-node graphs for sufficiently large n) under these scenarios. If only omission failures are assumed, almost-safe broadcasting is feasible for any p<1, in both communication models. For Byzantine faults, almost-safe broadcasting is feasible in the message passing model iff p<1/2 and in the radio model iff p<(1-p)Δ+1, where Δ is the maximum degree of the network. For the time complexity of almost-safe broadcasting, we give the following upper and lower bounds. Consider an n-node graph G with a given source s, and denote by D the radius of G w.r.t. s (namely, the largest distance from s to any node in G). Then for the message passing model we show that assuming omission faults, the optimal almost-safe broadcasting time is Θ (D + log n). Assuming Byzantine faults, almost-safe broadcasting is possible in time O(D+log α n), for any constant α > 1. For the radio model we show that almost-safe broadcasting in time O (opt + log n) (where opt is the optimal fault-free broadcasting time) is impossible for some graphs, even with omission failures, and we give an almost-safe broadcasting algorithm of time O(opt • log n) for any graph, for both types of failures.

This paper considers the convergence problem in autonomous mobile robot systems. A natural algorithm for the problem requires the robots to move towards their center of gravity. This paper proves the correctness of the gravitational algorithm in the fully asynchronous model. It also analyzes its convergence rate and establishes its convergence in the presence of crash faults.

We consider a simple model for overlay networks, where all n processes are connected to all other processes, and each message contains at most O(log n) bits. For this model, we present a distributed algorithm which constructs a minimum-weight spanning tree in O(log log n) communication rounds, where in each round any process can send a message to every other process. If message size is $\Theta(n^\epsilon)$ for some $\epsilon>0$, then the number of communication rounds is $O(\log{1\over\epsilon})$.

Electronic commerce engines like eBay depend heavily on reputation systems to improve customer confidence that electronic transactions will be successful, and to limit the economic damage done by disreputable peers defrauding others. In a reputation system, participant spost information about every transaction,and routinely check the posted information before taking any action to avoid other participants with a bad history.In this paper, we introduce a framework for optimizing reputation systems for objects.We study reputation systems in an asynchronous setting, and in the context of restricted access to the objects. Specifically, we study the cases where access may be restricted in time (objects arrive and depart from system) and inspace (each peer has access to only a subset of the objects).

An {\em $(\alpha,\beta)$-spanner} of a graph G is a subgraph H such that $\mathit{dist}_H(u,w)\le \alpha\cdot \mathit{dist}t_G(u,w)+\beta$ for every pair of vertices u,w, where dist G' (u,w) denotes the distance between two vertices u and v in G'. It is known that every graph G has a polynomially constructible $(2\kappa-1,0)$-spanner (also known as multiplicative $(2\kappa-1)$-spanner) of size $O(n^{1+1/\kappa})$ for every integer $\kappa\ge 1$, and a polynomially constructible (1,2)-spanner (also known as additive 2-spanner) of size ${\tilde O}(n^{3/2})$. This paper explores hybrid spanner constructions (involving both multiplicative and additive factors) for general graphs and shows that the multiplicative factor can be made arbitrarily close to 1 while keeping the spanner size arbitrarily close to O(n), at the cost of allowing the additive term to be a sufficiently large constant. More formally, we show that for any constant $\epsilon, \lambda > 0$ there exists a constant $\beta = \beta(\epsilon, \lambda)$ such that for every n-vertex graph G there is an efficiently constructible $(1+ \epsilon, \beta)$-spanner of size $O(n^{1 + \lambda})$.

This paper studies labeling schemes for flow and connectivity functions. A flow labeling scheme using $O(\log n\cdot\log {\hat{\omega}}+\log^2n)$-bit labels is presented for general n-vertex graphs with maximum (integral) capacity ${\hat{\omega}}$. This is shown to be asymptotically optimal. For edge-connectivity, this yields a tight bound of $\Theta(\log^2 n)$ bits. A k-vertex connectivity labeling scheme is then given for general n-vertex graphs using at most 3 log n bits for k = 2, 5 log n bits for k = 3, and 2 k log n bits for k > 3. Finally, a lower bound of $\Omega (k\log n)$ is established for k -vertex connectivity on n-vertex graphs, where k is polylogarithmic in n.

We consider a simple model for overlay networks, where all n processes are connected to all other processes, and each message contains at most O(log n) bits. For this model, we present a distributed algorithm that constructs a minimum-weight spanning tree in O(log log n) communication rounds, where in each round any process can send a message to each other process. This result is the first to break the ω(log n) parallel time complexity barrier with small message sizes.

The resource discovery problem arises in the context of peer to peer (P2P) networks, where at any point of time a peer may be placed at or removed from any location over a general purpose network (e.g., an Internet site). A vertex (peer) can communicate with another vertex directly if and only if it knows a certain routing information to that other vertex. Hence, it is critical for peers to convey this routing information to each other. The problem was formalized by Harchol-Balter et al. (1999). The routing information needed for a vertex to reach another peer is that peer's identifier (e.g., IP address). A logical directed edge represents the fact that the peer at the tail of the edge knows the IP address of the one at its head. A number of algorithms were developed by Harchol-Balter et al. for this problem in the model of a synchronous network over a weakly connected directed graph. The best of these algorithms was randomized. Subsequently, a deterministic algorithm for the problem on synchronous networks with improved complexity was presented by Kutten et al. (2001). The current paper extends this deterministic algorithm to the environment of asynchronous networks, maintaining similar complexities (translated to the asynchronous model). These are lower than the complexities that would be needed to synchronize the system. The main technical difficulty in a directed, weakly connected system is to ensure that vertices take consistent steps, even if their knowledge about each other is not symmetric, and even if there is no timeout mechanism (which does exist in synchronous systems) to assist in that.

A quorum system is a collection of sets (quorums) every two of which intersect. Quorum systems have been used for many applications in the area of distributed systems, including mutual exclusion, data replication, and dissemination of information. When the elements may fail, a user of a distributed protocol needs to quickly find a quorum all of whose elements are alive or evidence that no such quorum exists. This is done by probing the system elements, one at a time, to determine if they are alive or dead. This paper studies the probe complexity $\cal{PC(S)}$ of a quorum system $\cal{S}$, defined as the worst case number of probes required to find a live quorum or to show its nonexistence in $\cal{S}$, using the best probing strategy. We show that for large classes of quorum systems, all n elements must be probed in the worst case. Such systems are called evasive. However, not all quorum systems are evasive; we demonstrate a system where O(log n) probes always suffice. Then we prove two lower bounds on the probe complexity in terms of the minimal quorum cardinality $c \cal{(S)}$ and the number of minimal quorums $m\cal{(S)}$. Finally, we show a universal probe strategy which never makes more than $c {\cal(S)}^2 - c{\cal(S)}+ 1$ probes; thus any system with $c{\cal(S)}\le\sqrt n $ is nonevasive.

This paper discusses the probe complexity of randomized algorithms and the deterministic average case probe complexity for some classes of non-dominated coteries, including majority, crumbling walls, tree, wheel and hierarchical quorum systems, and presents upper and lower bounds for the probe complexity of quorum systems in these classes.

This paper considers the problem of distributively constructing a minimum-weight spanning tree (MST) for graphs of constant diameter in the bounded-messages model, where each message can contain at most B bits for some parameter B. It is shown that the time required to compute an MST for graphs of diameter 4 or 3 can be as high as Ω(3√n/B) and Ω(4√n/2√B), respectively. The lower bound holds even if the algorithm is allowed to be randomized. On the other hand, it is shown that O(log n) time units suffice to compute an MST deterministically for graphs with diameter 2, when B = O(log n). These results complement a previously known lower bound of Ω(2√n/B) for graphs of diameter Ω(log n).

The resource discovery problem was introduced by Harchol-Balter, Leigh ton and Lewin. They developed a number of algorithms for the problem in the weakly connected directed graph model. This model is a directed logical graph, that represents the vertices' “knowledge” about the topology of the underlying communication network.

An (α,Β)-spanner of a graph G is a subgraph H such that d_H(u,w)\le α\cdot d_G(u,w)+Β for every pair of vertices u,w, where d_{G'}(u,w) denotes the distance between two vertices u and v in G'. It is known that every graph G has a polynomially constructible (2κ-1,0)-spanner (a.k.a. multiplicative (2κ-1)-spanner) of size O(n^{1+1/κ}) for every integer κ\ge 1, and a polynomially constructible (1,2)-spanner (a.k.a. additive 2-spanner) of size \tO(n^{3/2}). This paper explores hybrid spanner constructions (involving both multiplicative and additive factors) for general graphs and shows that the multiplicative factor can be made arbitrarily close to 1 while keeping the spanner size arbitrarily close to O(n), at the cost of allowing the additive term to be a sufficiently large constant. More formally, we show that for any constant ε, δ > 0 there exists a constant Β = Β(ε, δ) such that for every n-vertex graph G there is an efficiently constructible (1+ ε, Β)-spanner of size O(n^{1 + δ}). It follows that for any constant ε, δ > 0 there exists a constant Β(ε, δ) such that for any n-vertex graph G = (V,E) there exists an efficiently constructible subgraph (V,H) with O(n^{1 +δ}) edges such that d_H(u,w) \le (1 + ε) d_G(u,w) for every pair of vertices.

Interval routing is a compact way of representing routing tables on a graph. It is based on grouping together, in each node, destination addresses that use the same outgoing edge in the routing table. Such groups of addresses are represented by some intervals of consecutive integers. We show that almost all the graphs, i.e., a fraction of at least 1-1/n 2 of all the n-node graphs, support a shortest path interval routing with three intervals per outgoing edge, even if the addresses of the nodes are arbitrarily fixed in advance and cannot be chosen by the designer of the routing scheme. In case the addresses are initialized randomly, we show that two intervals per outgoing edge suffice, and, conversely, that two intervals are required for almost all graphs. Finally, if the node addresses can be chosen as desired, we show how to design in polynomial time a shortest path interval routing with a single interval per outgoing edge for all but at most O(log 3 n ) outgoing edges in each node. It follows that almost all graphs support a shortest path routing scheme which requires at most n+O(log 4 n ) bits of routing information per node, improving on the previous upper bound.

This paper studies the differences between two levels of synchronization in a distributed broadcast system (or a multiple-access channel). In the globally synchronous model, all processors have access to a global clock. In the locally synchronous model, processors have local clocks ticking at the same rate, but each clock starts individually when the processor wakes up. We consider the fundamental problem of waking up all n processors of a completely connected broadcast system. Some processors wake up spontaneously, while others have to be woken up. Only awake processors can send messages; a sleeping processor is woken up upon hearing a message. The processors hear a message in a given round if and only if exactly one processor sends a message in that round. Our goal is to wake up all processors as fast as possible in the worst case, assuming an adversary controls which processors wake up and when. We analyze the problem in both the globally synchronous and locally synchronous models with or without the assumption that n is known to the processors. We propose randomized and deterministic algorithms for the problem, as well as lower bounds in some of the cases. These bounds establish a gap between the globally synchronous and locally synchronous models.

We consider the task of distributedly assigning distinct labels to nodes of an unknown anonymous network. A priori, nodes do not have any identities (anonymous network) and do not know the topology or the size of the network (unknown network). They execute identical algorithms, apart from a distinguished node, called the source, which starts the labeling process. Our goal is to assign short labels, as fast as possible. The quality of a labeling algorithm is measured by the range from which the algorithm picks the labels, or alternatively, the length of the assigned labels. Natural efficiency measures are the time, i.e., the number of rounds required for the label assignment, and the message and bit complexities of the label assignment protocol, i.e., the total number of messages (resp., bits) circulating in the network. We present label assignment algorithms whose time and message complexity are asymptotically optimal and which assign short labels. On the other hand, we establish inherent trade-offs between quality and efficiency for labeling algorithms.

This paper studies the differences between two levels of synchronization in a distributed broadcast system (or a multiple access channel). In the globally synchronous model, all processors have access to a global clock. In the locally synchronous model, processors have local clocks ticking at the same rate, but each clock starts individually, when the processor wakes up.

Traditional approaches to network design separate the issues of designing the network itself and designing its management and control subsystems. This paper proposes an approach termed routing-oriented network design, which is based on designing the network topology and its routing scheme together, attempting to optimize some of the relevant parameters of both simultaneously.

The resource discovery problem was introduced by Harchol-Balter, Leighton and Lewin in [HLL99], as a part of their work on web caching. They developed a randomized algorithm for the problem in the weakly connected directed graph model, that was implemented within LCS at MIT, and then licensed to Akamai Technologies.

This paper lays a theoretical foundation for scaling fault tolerant tasks to large and diversified networks such as the Internet. In such networks, there are always parts of the network that fail. On the other hand, various subtasks interest only parts of the network, and it is desirable that those parts, if nonfaulty, do not suffer from faults in other parts. Our approach is to refine the previously suggested notion of fault local algorithms (that was best suited for global tasks) for which the complexity of recovering was proportional to the number of faults. We refine this notion by introducing the concept of tight fault locality to deal with problems whose complexity (in the absence of faults) is sublinear in the size of the network. For a problem whose time complexity on an n-node network is T(n) (where possibly T(n)= o(n)), a tightly fault local algorithm recovers a legal global state in O(T(x)) time when the (unknown) number of faults is x. This concept is illustrated by presenting a general transformation for maximal independent set (MIS) algorithms to make them tightly fault local. In particular, our transformation yields an O(log x) randomized mending algorithm and an $\exp(O(\sqrt{\log x}))$ deterministic mending algorithm for MIS. The methods used in the transformation may be of interest by themselves.

This paper presents a lower bound of $\Omega(D+\sqrt n/\log n)$ on the time required for the distributed construction of a minimum-weight spanning tree (MST) in weighted n-vertex networks of diameter $D=\Omega(\log n)$, in the bounded message model. This establishes the asymptotic near-optimality of existing time-efficient distributed algorithms for the problem, whose complexity is $O(D + \sqrt n \log^* n)$.

This paper presents a lower bound of /spl Omega/~(D+/spl radic/n) on the time required for the distributed construction of a minimum-weight spanning tree (MST) in n-vertex networks of diameter D=/spl Omega/(log n), in the bounded message model. This establishes the asymptotic near-optimality of existing time-efficient distributed algorithms for the problem, whose complexity is O(D+/spl radic/nlog* n).

This paper presents the first dynamic routing scheme for high-speed networks. The scheme is based on a hierarchical bubbles partition of the underlying communication graph. Dynamic routing schemes are ranked by their adaptability, i.e., the maximum number of sites to be updated upon a topology change. An advantage of our scheme is that it implies a small number of updates upon a topology change. In particular, for the case of a bounded degree network it is proved that our scheme is optimal in its adaptability by presenting a matching tight lower bound. Our bubble routing scheme is a combination of a distributed routing database, a routing strategy, and a routing database update. It is shown how to perform the routing database update on a dynamic network in a distributed manner.

The compactness of a graph measures the space complexity of its shortest path routing tables. Each outgoing edge of a node x is assigned a (pairwise disjoint) set of addresses, such that the unique outgoing edge containing the address of a node y is the first edge of a shortest path from x to y. The complexity measure used in the context of interval routing is the minimum number of intervals of consecutive addresses needed to represent each such set, minimized over all possible choices of addresses and all choices of shortest paths. This paper establishes asymptotically tight bounds of n/4on the compactness of an n-node graph. More specifically, it is shown that every n-node graph has compactness at most n/4+o(n), and conversely, there exists an n-node graph whose compactness is n/4 - o(n). Both bounds improve upon known results. (A preliminary version of the lower bound has been partially published in Proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Comput. Sci. 1300, pp. 259--268, 1997.)

This paper presents a routing strategy called Pivot Interval Routing (PIR), which allows inessage routing on every weighted n-node network along paths whose stretch (namely, the ratio between their length and the distance between their endpoints) is at most five, and whose average stretch is at inost three, with routing tables of size O(n3/" log3/' n) bits in total.A similar routing strategy for unweighted networks which guarantees the same bounds on the stretch factor and in addition a bound of r1.501 on the route lengths, where D is the dianreter of the network, is also presented.Moreover, it is shown that the PIR strategy can be implemented so that the generated scheme is in the forin of an interval routing scheme (IRS), using at most 2dm intervals per link in the first case and 3,/m in the second case.As a result, the scheines are siinpler than previous ones and they imply that paths of messages are loop-free.Finally, it is showu that there is no loop-free routing strategy guaranteeing a inemory bound of J5i bits per router for all networks, regardless of the route lengths.

This paper introduces a near-linear time sequential algorithm for constructing a sparse neighborhood cover. This implies analogous improvements (from quadratic to near-linear time) for any problem whose solution relies on network decompositions, including small edge cuts in planar graphs, approximate shortest paths, and weight- and distance-preserving graph spanners. In particular, an O(log n) approximation to the k-shortest paths problem on an n-vertex, E-edge graph is obtained that runs in $\soh{n + E + k}$ time.

This work is concerned with the problem of broadcasting a large message efficiently when each processor has partial prior knowledge about the contents of the broadcast message. The partial information held by the processors might be out of date or otherwise erroneous, and consequently, different processors may hold conflicting information. Tight bounds are established for broadcast under such conditions, and applications of the broadcast protocol to other distributed computing problems are discussed.

This paper considers the question of identifying the parameters governing the behavior of fundamental global network problems. Many papers on distributed network algorithms consider the task of optimizing the running time successful when an O(n) bound is achieved on an n-vertex network. We propose that a more sensitive parameter is the network's diameter $\Diam$. This is demonstrated in the paper by providing a distributed minimum-weight spanning tree algorithm whose time complexity is sublinear in n, but linear in $\Diam$ (specifically, $O(\Diam + n^\varepsilon \cdot \log^* n)$ for $\varepsilon = \frac{\ln 3}{\ln 6} = 0.6131...$). Our result is achieved through the application of graph decomposition and edge-elimination-by-pipelining techniques that may be of independent interest.

A k-spanner of a connected (undirected unweighted) graph G=(V,E) is a subgraph G' consisting of all the vertices of V and a subset of the edges, with the additional property that the distance between any two vertices in G' is larger than that distance in G by no more than a factor of k. This paper is concerned with approximating the problem of finding a 2-spanner in a given graph, with minimum maximum degree. We first show that the problem is at least as hard to approximate as set cover. Then a randomized approximation algorithm is provided for this problem, with approximation ratio of $\tilde O(\Delta^{1/4})$. We then present a probabilistic algorithm that is more efficient for sparse graphs. Our algorithms are converted into deterministic ones using derandomization.

This paper introduces and studies the question of balancing the load on processors participating in a given quorum system. Our proposed measure for the degree of balancing is the ratio between the load on the least frequently referenced element and on the most frequently used one. We give some simple sufficient and necessary conditions for perfect balancing. We then look at the balancing properties of the common class of voting systems and prove that every voting system with odd total weight is perfectly balanced. (This holds, in fact, for the more general class of ordered systems.) We also give some characterizations for the balancing ratio in the worst case. It is shown that for any quorum system with a universe of size n, the balancing ratio is no smaller than $1/(n-1)$, and this bound is the best possible. When restricting attention to nondominated coteries (NDCs), the bound becomes $2/\bigl(n-\log_2 n+o(\log n)\bigr)$, and there exists an NDC with ratio $2/\bigl(n-\log_2 n-o(\log n)\bigr)$. Next, we study the interrelations between the two basic parameters of load balancing and quorum size. It turns out that the two size parameters suitable for our investigation are the size of the largest quorum and the optimally weighted average quorum size(OWAQS) of the system. For the class of ordered NDCs (for which perfect balancing is guaranteed), it is shown that over a universe of size n, some quorums of size $\lceil(n+1)/2\rceil$ or more must exist (and this bound is the best possible). A similar lower bound holds for the OWAQS measure if we restrict attention to voting systems. For nonordered systems, perfect balancing can sometimes be achieved with much smaller quorums. A lower bound of $\Omega(\sqrt{n})$ is established for the maximal quorum size and the OWAQS of any perfectly balanced quorum system over n elements, and this bound is the best possible. Finally, we turn to quorum systems that cannot be perfectly balanced, but have some balancing ratio $0 < \rho < 1$. For such systems we study the trade-offs between the required balancing ratio $\rho$ and the quorum size it admits in the best case. It is easy to get an analogue of the result for perfect balancing, yielding a lower bound of $\sqrt{n\rho}$. We actually get a better estimate by a refinement of the argument.

No abstract available.

Article How to be an efficient snoop, or the probe complexity of quorum systems (extended abstract) Share on Authors: David Peleg Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, Israel Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, IsraelView Profile , Avishai Wool Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, Israel Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, IsraelView Profile Authors Info & Claims PODC '96: Proceedings of the fifteenth annual ACM symposium on Principles of distributed computingMay 1996 Pages 290–299https://doi.org/10.1145/248052.248112Online:01 May 1996Publication History 15citation207DownloadsMetricsTotal Citations15Total Downloads207Last 12 Months2Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper presents deterministic sublinear-time distributed algorithms for network decomposition and for constructing a sparse neighborhood cover of a network. The latter construction leads to improved distributed preprocessing time for a number of distributed algorithms, including all-pairs shortest paths computation, load balancing, broadcast, and bandwidth management.

The notion of fault local mending was suggested as a paradigm for designing fault tolerant algorithms that scale to large networks. For such algorithms the complexity of recovering is proportional to the number of faults. We refine this notion by introducing the concept of tight fault locality to deal with problems whose complexity (in the absence of faults) is sublinear in the size of the network. For a function whose complexity on an n-node network is f(n), a tightly fault local algorithm recovers a legal global state in O(f(x)) time when the (unknown) number of faults is x. We illustrate this concept by presenting a general transformation for MIS algorithms to make them fault local. In particular, our transformation yields an O(logx) randomized mending algorithm and a 2/sup /spl radic//spl beta/logx/ deterministic mending algorithm for MIS. Similar results are obtained for other local functions such as a /spl Delta/+1 coloring. We also present the first tight fault local mending algorithm for global functions, using our results for MIS. This improves (by a logarithmic factor) the complexity of a previous fault-local mending algorithm for global functions.

As communication networks grow, existing fault handling tools that involve global measures such as global time-outs or reset procedures become increasingly unaffordable, since their cost grows with the size of the network. Rather, for a fault handling mechanism to scale to large networks, its cost must depend only on the number of failed nodes (which, thanks to today’s technology, grows much slower than the net works). Moreover, it should allow the non-faulty regions of the networks to continue their operation even during the recovery of the faulty parts. This abstract introduces the concepts fault locality, and of fault-locally mendable problems, which are problems for which there exist correction algorithms (applied after faults) whose cost depends only on the (unknown) number of faults. We show that any problem is fault locally mendable. The solution involves a novel technique combining data structures and “local votes ” among nodes, that may be of interest in itself.

Article Fast distributed construction of k-dominating sets and applications Share on Authors: Shay Kutten I.B.M. T.J. Watson Research Center, P.O. Box 704, Yorktown, Heights, New York I.B.M. T.J. Watson Research Center, P.O. Box 704, Yorktown, Heights, New YorkView Profile , David Peleg Department of Applied Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, 76100 Israel Department of Applied Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, 76100 IsraelView Profile Authors Info & Claims PODC '95: Proceedings of the fourteenth annual ACM symposium on Principles of distributed computingAugust 1995 Pages 238–251https://doi.org/10.1145/224964.224990Published:20 August 1995 48citation737DownloadsMetricsTotal Citations48Total Downloads737Last 12 Months10Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Article Crumbling walls: a class of practical and efficient quorum systems Share on Authors: David Peleg Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, Israel Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, IsraelView Profile , Avishai Wool Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, Israel Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, IsraelView Profile Authors Info & Claims PODC '95: Proceedings of the fourteenth annual ACM symposium on Principles of distributed computingAugust 1995 Pages 120–129https://doi.org/10.1145/224964.224978Online:20 August 1995Publication History 23citation309DownloadsMetricsTotal Citations23Total Downloads309Last 12 Months2Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper presents the first dynamic routing scheme for high-speed networks.The scheme is based on a hierarchical bubbles partition of the underlying communithat copym IS by perrmsslon of the Association of Computing Machinery.o cop otherwise, or to republish, requires y r a fee ancflor speci IC permission.

This paper deals with the problem of maintaining a distributed directory server, that enables us to keep track of mobile users in a distributed network. The paper introduces the graph-theoretic concept ofregional matching, and demonstrates how finding a regional matching with certain parameters enables efficient tracking. The communication overhead of our tracking mechanism is within a polylogarithmic factor of the lower bound.

This paper investigates a zero-sum game played on a weighted connected graph G between two players, the tree player and the edge player. At each play, the tree player chooses a spanning tree T and the edge player chooses an edge e. The payoff to the edge player is $\textit{cost} (T, e)$, defined as follows: If e lies in the tree T then $\textit{cost}(T, e) = 0$; if e does not lie in the tree then $\textit{cost}(T, e) = cycle(T, e)/w(e)$, where $w(e)$ is the weight of edge e and $\textit{cycle}(T, e)$ is the weight of the unique cycle formed when edge e is added to the tree T. The main result is that the value of the game on any n-vertex graph is bounded above by $\exp(O(\sqrt{\log n \log \log n}))$. It is conjectured that the value of the game is $O(\log n)$. The game arises in connection with the k-server problem on a road network; i.e., a metric space that can be represented as a multigraph G in which each edge e represents a road of length $w(e)$. It is shown that, if the value of the game on G is $\textit{Val}(G, w)$, then there is a randomized strategy that achieves a competitive ratio of $k(1 + \textit{Val}(G, w))$ against any oblivious adversary. Thus, on any n-vertex road network, there is a randomized algorithm for the k-server problem that is $k \cdot \exp(O(\sqrt{\log n \log \log n}))$ competitive against oblivious adversaries. At the heart of the analysis of the game is an algorithm that provides an approximate solution for the simple network design problem. Specifically, for any n-vertex weighted, connected multigraph, the algorithm constructs a spanning tree T such that the average, over all edges e, of $\textit{cost}(T, e)$ is less than or equal to $\exp(O(\sqrt{\log n \log \log n}))$. This result has potential application to the design of communication networks. It also improves substantially known estimates concerning the existence of a sparse basis for the cycle space of a graph.

Scheduling packets to be forwarded over a link is an important subtask of the routing process in both parallel computing and in communication networks. This paper investigates the simple class of greedy scheduling algorithms, namely, algorithms that always forward a packet if they can. It is first proved that for various “natural” classes of routes, the time required to complete the transmission of a set of packets is bounded by the number of packets, k, and the maximal route length, d, for any greedy algorithm (including the arbitrary scheduling policy). Next, tight time bounds of $d+k-1$ are proved for a specific greedy algorithm on the class of shortest paths in n-vertex networks. Finally, it is shown that when the routes are arbitrary, the time achieved by various “natural” greedy algorithms can be as bad as $\Omega (d \sqrt {k} + k)$, for any k, and even for $d = \Omega (n)$.

This paper deals with the problem of broadcasting in minimum time in the telephone and message-passing models. Approximation algorithms are developed for arbitrary graphs as well as for several restricted graph classes. In particular, an $O( \sqrt{n} )$-additive approximation algorithm is given for broadcasting in general graphs, and an $O( \log n/\log \log n )$ (multiplicative) ratio approximation is given for broadcasting in the open-path model. This also results in an algorithm for broadcasting on random graphs (in the telephone and message-passing models) that yields an $O( \log n/\log \log n )$ approximation with high probability. In addition, the paper presents a broadcast algorithm for graph families with small separators (such as chordal, k-outerplanar, bounded-face planar, and series-parallel graphs), with approximation ratio proportional to the separator size times $\log n$. Finally, an efficient approximation algorithm is presented for the class of graphs representable as trees of cliques.

This paper studies the depth of noisy decision trees in which each node gives the wrong answer with some constant probability. In the noisy Boolean decision tree model, tight bounds are given on the number of queries to input variables required to compute threshold functions, the parity function and symmetric functions. In the noisy comparison tree model, tight bounds are given on the number of noisy comparisons for searching, sorting, selection and merging. The paper also studies parallel selection and sorting with noisy comparisons, giving tight bounds for several problems.

This article deals with store-and-forward deadlock prevention in communication networks. The approach we adopt is that of establishing buffer classes in order to prevent cyclic waiting chains. This type of solutions usually tends to require many buffers. The main contribution is in showing that the number of required buffers can be reduced considerably by employing a hierarchical organization of the network. It proposes a new hierarchical scheme for arbitrary networks, that features a tradeoff between the communication overhead and the buffer requirements of the routing. This tradeoff can be shown to be close to optimal.>

This paper introduces the first near-linear (specifically, O(Elog n+nlog/sup 2/ n)) time algorithm for constructing a sparse neighborhood cover in sequential and distributed environments. This automatically implies analogous improvements (from quadratic to near-linear) to all the results in the literature that rely on network decompositions, both in sequential and distributed domains, including adaptive routing schemes with O/spl tilde/(1) stretch and memory, small edge cuts in planar graphs, sequential algorithms for dynamic approximate shortest paths with O/spl tilde/(E) cost for edge insertion/deletion and O/spl tilde/(1) time to answer shortest-path queries, weight and distance-preserving graph spanners with O/spl tilde/(E) running time and space, and distributed asynchronous "from-scratch" breadth-first-search and network synchronizer constructions with O/spl tilde/(1) message and space overhead (down from O(n)).>

This paper considers the question of identifying the parameters governing the behavior of fundamental global network problems. Many papers on distributed network algorithms consider the task of optimizing the running time successful when an O(n) bound is achieved on an n-vertex network. We propose that a more sensitive parameter is the network's diameter Diam. This is demonstrated in the paper by providing a distributed minimum-weight spanning tree algorithm whose time complexity is sub-linear in n, but linear in Diam (specifically, O(Diam+n/sup 0.614/)). Our result is achieved through the application of graph decomposition and edge elimination techniques that may be of independent interest.>

This paper concerns the problem of computing the densest k-vertex subgraph of a given graph, namely, the subgraph with the most edges, or with the highest edges-to-vertices ratio. A sequence of approximation algorithms is developed for the problem, with each step yielding a better ratio at the cost of a more complicated solution. The approximation ratio of our final algorithm is O/spl tilde/(n/sup 0.3885/). We also present a method for converting an approximation algorithm for an unweighted graph problem (from a specific class of maximization problems) into one for the corresponding weighted problem, and apply it to the densest subgraph problem.>

This paper obtains the first deterministic sublinear-time algorithm ~1992

This paper examines the problem of balancing the job load in a network of processors, and introduces an online algorithm for scheduling a sequence of jobs in a competitive manner. The algorithm is shown to be polylog (n)-competitive according to a strict definition that forces the online algorithm to be competitive even when considering any bounded area of the network and bounded period of time.

The computational power of different communication models is a fundamental question in the theory of distributed computation. For example, in the synchronous model messages are assumed to be delivered within one time unit, whereas in the asynchronous model message delays may be arbitrary. Another important parameter of the model is the assumptions about the topology. In the dynamic topology model, links are assumed to crash and recover dynamically, but their status is known to the incident node processors. A meaningful computation can be carried out if the topology stabilizes for a sufficiently long period.

This paper presents a family of memory-balanced routing schemes that use relatively short paths while storing relatively little routing information. The quality of the routes provided by a scheme is measured in terms of their stretch, namely, the maximum ratio between the length of a route connecting some pair of processors and their distance. The hierarchical schemes$\mathcal{H}_k $ (for every integer $k\geqq 1$) presented in this paper guarantee a stretch factor of $O( k^2 )$ on the length of the routes and require storing at most $O( k \cdot n^{1/k} \cdot \log n\log D )$ bits of routing information per vertex in an n-processor network with diameter D. The schemes are name independent and applicable to general networks with arbitrary edge weights. This improves on previous designs whose stretch bound was exponential in k. The proposed schemes are based on a new efficient solution to a certain graph-theoretic problem concerning sparse graph covers. The new cover technique has already found several other applications in the area of distributed computing.

Store-and-forward deadlock prevention in communication networks is addressed. The approach adopted is that of establishing buffer classes in order to prevent cyclic waiting chains. This type of solution usually requires many buffers. The main contribution of the current study is in showing that the number of required buffers can be reduced considerably by using a hierarchical organization of the network. A novel hierarchical scheme for arbitrary networks is proposed, that features a trade-off between the communication overhead and the buffer requirements of the routing. This trade-off can be shown to be close to optimal.>

This work concerns the problem of broadcasting a large message efficiently when each processor has partial prior knowledge tocol to other distributed computing problems are discussed.

This paper deals with store-and-forward deadlocks in communication networks.The goal is to design deadlock-free routing schemes with small overhead in communication and space.Our main contribution is designing efficient protocols that are superior to existing ones in terms of their performance.

Article Free Access Share on Compact deterministic distributed dictionaries (extended abstract) Authors: Karni Gilon Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, Israel. Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, Israel.View Profile , David Peleg Department of Applied Mathematics and Computer, Science, The Weizmann Institute, Rehovot 76100, Israel. Department of Applied Mathematics and Computer, Science, The Weizmann Institute, Rehovot 76100, Israel.View Profile Authors Info & Claims PODC '91: Proceedings of the tenth annual ACM symposium on Principles of distributed computingJuly 1991 Pages 81–94https://doi.org/10.1145/112600.112609Published:01 July 1991Publication History 2citation178DownloadsMetricsTotal Citations2Total Downloads178Last 12 Months12Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper deals with the problem of maintaining a distributed directory server, that enables us to keep track of mobile users in a distributed network in the presence of concurrent requests. The paper uses the graph-theoretic concept of regional matching for implementing efficient tracking mechanisms. The communication overhead of our tracking mechanism is within a polylogarithmic factor of the lower bound. 1 Introduction Since the primary function of a communication network is to provide communication facilities between users and processes in the system, one of the key problems such a network faces is the need to be able to Department of Mathematics and Lab. for Computer Science, M.I.T., Cambridge, MA 02139, USA. E-mail: [email protected]. Supported by Air Force Contract TNDGAFOSR-86-0078, ARO contract DAAL03-86-K0171, NSF contract CCR8611442, DARPA contract N00014-89J -1988, and a special grant from IBM. y Departmentof Applied Mathematicsand Computer Science, The Weizm...

A broadcast graph is an n-vertex communication network that supports a broadcast from any one vertex to all other vertices in optimal time $\lceil \lg n\rceil$, given that each message transmission takes one time unit and a vertex participates in at most one transmission per time step. This paper establishes tight bounds for $B( n )$, the minimum number of edges of a broadcast graph, and $D( n )$, the minimum maxdegree of a broadcast graph. Let $L( n )$ denote the number of consecutive leading 1’s in the binary representation of integer $n - 1$. It is shown that $B( n ) = \Theta ( L( n )\cdot n )$ and $D( n ) = \Theta ( \lg \lg n + L ( n ) )$ and for every n we give a construction simultaneously within a constant factor of both lower bounds. For all n, graphs with $O( n )$ edges and $O( \lg \lg n )$ maxdegree requiring at most $\lceil \lg n \rceil + 1$ time units to broadcast are constructed. These broadcast protocols may be implemented with local control and $O( \lg \lg n )$ bits overhead per message.

Mesh-connected computers with multiple buses providing broadcast facilities along rows and columns are discussed. A tight bound of Theta (n/sup 1/8/) is established for the number of rounds required for semigroup computations on n values distributed on a two-dimensional rectangular mesh of size n with a bus on every row and column. The upper bound is obtained for a skewed rectangular mesh of dimensions n/sup 3/8/*n/sup 5/8/. This result is compared to the tight bound of Theta (n/sup 1/6/) for the same problem on the square (n/sup 1/2/*n/sup 1/2/) mesh. It is shown that in the presence of multiple buses, a skewed configuration may perform better than a square configuration for certain computational tasks. The result can be extended to the d-dimensional mesh, giving a lower bound of Omega (n/sup 1/d alpha /) and an upper bound of O(d2/sup d+1/ n/sup 1/d alpha /), where alpha =2/sup d/; these bounds are optimal within constant factors for any constant d. It is noted that for d>3, the results of are mostly of theoretical interest.>

A collection of clustering and decomposition techniques that make possible the construction of sparse and locality-preserving representations for arbitrary networks is presented. The representation method considered is based on breaking the network G(V,E) into connected regions, or clusters, thus obtaining a cover for the network, i.e. a collection of clusters that covers the entire set of vertices V. Several other graph-theoretic structures that are strongly related to covers are discussed. These include sparse spanners, tree covers of graphs and the concepts of regional matchings and diameter-based separators. All of these structures can be constructed by means of one of the clustering algorithms given, and each has proved a convenient representation for handling certain network applications.>

The synchronizer is a simulation methodology for simulating a synchronous network by an asynchronous one, thus enabling the execution of a synchronous algorithm on an asynchronous network. Previously known synchronizers require each processor in the network to participate in each pulse of the synchronization process. The resulting communication overhead depends linearly on the number n of network nodes. A synchronizer with overhead only polylogarithmically dependent on n is introduced. This synchronizer can also be realized with polylog(n) space. The polylog-overhead synchronizer is based on involving only the relevant portions of the network in the synchronization process.>

This paper introduces the notion of cost-sensitive communication complexity and exemplifies it on the following basic communication problems: computing a global function, network synchronization, clock synchronization, controlling protocols' worst-case execution, connected components, spanning tree, etc., constructing a minimum spanning tree, constructing a shortest path tree. IntroductionTraEic load is one of the major factors affecting the behavior of a communication network.This fact is well recognized, and is the reason why most

Article Free AccessComputing with unreliable information Authors: U. Feige The Weizmann Institute of Science, Rehovot, Israel and T.J. Watson and Almaden Research Centers The Weizmann Institute of Science, Rehovot, Israel and T.J. Watson and Almaden Research CentersView Profile , D. Peleg The Weizmann Institute of Science, Rehovot, Israel The Weizmann Institute of Science, Rehovot, IsraelView Profile , P. Raghavan IBM T.J. Watson Research Center, Yorktown Heights, NY IBM T.J. Watson Research Center, Yorktown Heights, NYView Profile , E. Upfal IBM Almaden Research Center, San Jose, CA, and The Weizmann Institute of Science, Rehovot, Israel IBM Almaden Research Center, San Jose, CA, and The Weizmann Institute of Science, Rehovot, IsraelView Profile Authors Info & Claims STOC '90: Proceedings of the twenty-second annual ACM symposium on Theory of ComputingApril 1990 Pages 128–137https://doi.org/10.1145/100216.100230Published:01 April 1990Publication History 46citation775DownloadsMetricsTotal Citations46Total Downloads775Last 12 Months69Last 6 weeks8 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper is concerned with the solvability of the problem of processor renaming in unreliable, completely asynchronous distributed systems. Fischer et al. prove in [8] that “nontrivial consensus” cannot be attained in such systems, even when only a single, benign processor failure is possible. In contrast, this paper shows that problems of processor renaming can be solved even in the presence of up tot

This paper concerns the message complexity of broadcast in arbitrary point-to-point communication networks.Broadcastis a task initiated by asingleprocessor that wishes to convey a message to all processors in the network. The widely accepted model of communication networks, in which each processor initially knows the identity of its neighbors but does not know the entire network topology, is assumed. Although it seems obvious that the number of messages required for broadcast in this model equals the number of links, no proof of this basic fact has been given before. It is shown that the message complexity of broadcast depends on the exact complexity measure. If messages of unbounded length are counted at unit cost, then broadcast requires Θ(↿V↾) messages, whereVis the set of processors in the network. It is proved that, if one counts messages ofbounded length, then broadcast requires Θ(↿E↾) messages, whereEis the set of edges in the network. Assuming an intermediate model in which each vertex knows the topology of the network in radiusρ≥ 1 from itself, matching upper and lower bounds of Θ(min{↿E↾, ↿V↾1+Θ(l)/ρ}) is proved on the number of messages of bounded length required for broadcast. Both the upper and lower bounds hold for both synchronous and asynchronous network models. The same results hold for the construction of spanning trees, and various other global tasks.

This note presents a simple time-optimal distributed algorithm for electing a leader in a general network. For several important classes of networks this algorithm is also message-optimal and thus performs better than previous algorithms for the problem.

Three parameters characterize the performance of a probabilistic algorithm: T, the run-time of the algorithm; Q, the probability that the algorithm fails to complete the computation in the first T steps; and R, the amount of randomness used by the algorithm, measured by the entropy of its random source. A tight trade-off between these three parameters for the problem of oblivious packet routing on N-vertex bounded-degree networks is presented. A $(1 - Q) \log ({N / T}) - \log Q - O(1)$ lower bound for the entropy of a random source of any oblivious packet routing algorithm that routes an arbitrary permutation in T steps with probability $1 - Q$ is proved. It is shown that this lower bound is almost optimal by proving the existence, for every $e^{3} \log N \leqq T \leqq N^{{1 / 2}}$, of an oblivious algorithm that terminates in T steps with probability $1 - Q$ and uses $(1- Q + o(1)) \log ({N / T}) - \log Q$ independent random bits. This result is complemented with an explicit construction of a family of oblivious algorithms that use less than a factor of $\log N$ more random bits than the optimal algorithm achieving the same run-time.

In this paper we consider mesh connected computers with multiple buses, providing broadcast facilities along rows and columns.A tight bound of O(n~) is established for the number of rounds required for semigroup computations on n values distributed on a 2-dimensional rectangular mesh of size n with a bus on every row and column.The upper bound is obtained for a skewed rectangular mesh of dinaensions n 3Is × n "5Is.This result is to be contrasted with the tight bound of @(n~) for the same problem on the square (n ~/2 x n ~/~') mesh [PR].This implies that in the presence of multiple buses, a skewed configuration may perform better than a square configuration for certain computationM tasks.Our result can be extended to the d-dimensional mesh, giving a lower bound of • 1 f 2 ( n ~' ) and an upper bound of O ( d 2 d + l n ~' ) .

A radio network is a synchronous network of processors that communicate by transmitting messages to their neighbors. A processor receives a message in a given step if and only if it is silent then and precisely one of its neighbors transmits. This stringent rule poses serious difficulties in performing even the simplest tasks. This is true even under the overly optimistic assumptions of centralized coordination and complete knowledge of the network topology. This paper is concerned with lower and upper bounds for the complexity of realizing various communication primitives for radio networks.

In designing a routing scheme for a communication network it is desirable to use as short as possible paths for routing messages, while keeping the routing information stored in the processors' local memory as succinct as possible. The efficiency of a routing scheme is measured in terms of its stretch factor - the maximum ratio between the cost of a route computed by the scheme and that of a cheapest path connecting the same pair of vertices.

Two conflicting goals play a crucial role in the design of routing schemes for communication networks. A routing scheme should use paths that are as short as possible for routing messages in the network, while keeping the routing information stored in the processors' local memory as succinct as possible. The efficiency of a routing scheme is measured in terms of its stretch factor -the maximum ratio between the length of a route computed by the scheme and that of a shortest path connecting the same pair of vertices. Most previous work has concentrated on finding good routing schemes (with a small fixed stretch factor) for special classes of network topologies. In this paper the problem for general networks is studied, and the entire range of possible stretch factors is examined. The results exhibit a trade-off between the efficiency of a routing scheme and its space requirements. Almost tight upper and lower bounds for this trade-off are presented. Specifically, it is proved that any routing scheme for general n -vertex networks that achieves a stretch factor k ≥ 1 must use a total of Ω( n 1+1/(2 k +4) ) bits of routing information in the networks. This lower bound is complemented by a family K ( k ) of hierarchical routing schemes (for every k ≥ l) for unit-cost general networks, which guarantee a stretch factor of O ( k ), require storing a total of O ( k 3 n 1+(1/h) log n )- bits of routing information in the network, name the vertices with O (log 2 n )-bit names and use O (log n )-bit headers.

Abstract The balanced packet distribution problem on a ring of n processors requires that randomly arriving packets be stored at nodes as evenly as possible by passing packets (and other messages) around the ring. We give a protocol to achieve balanced distribution with an average message complexity of √n per packet and to show that the protocol is optimal, up to lower order terms, for unidirectional rings.

Abstract Broadcasting is the process by which a message originated at one vertex is delivered to all other vertices of a network, subject to the restriction that a vertex may participate in only one message transfer during a given time unit. A k fault‐tolerant broadcasting scheme is a calling scheme that gurantees the completion of the broadcast in the presence of up to k link failures. Let T k (n) denote the minimum time required for k fault‐tolerant broadcasting in an n ‐vertex network. Liestman [ Networks 15 (1985) 159–171] showed that for every n and k such that n − 2 ≥ k ≥ 1, T k (n) ⩾ [log n ]+ k . This paper establishes a matching upper bound, showing that for such n and k , T k (n) ϵ O (log n + k ). In particular, we present various efficient broadcasting schemes achieving almost optimal multiplicative constants. Our best upper bound uses new partial results on a tree‐packing problem that may be of independent interest.

A solution to the following fundamental communication problem is presented. Suppose that n tokens are arbitrarily distributed among n processors with no processor having more than K tokens. The problem is to specify a bounded-degree network topology and an algorithm that can distribute the tokens uniformly among the processors. The first result is a tight $\Theta (K + \log n)$ bound on the complexity of this problem. It is also shown that an approximate version of this problem can be solved deterministically in $O(K + \log n)$ on any expander graph with sufficiently large expansion factor. In the second part of this work, it is shown how to extend the solution for the approximate distribution problem to an optimal probabilistic algorithm for the exact distribution problem on a similar class of expander graphs. Note that communication through an expander graph is a necessary condition for an $O(K + \log n)$ solution of the problem. These results have direct applications to the efficient implementation of many-to-one and one-to-many communication requests, as well as to the solution of load-balancing problems in distributed systems.

The synchronizer is a simulation methodology introduced by Awerbuch [J. Assoc. Comput. Math., 32 (1985), pp. 804–823] for simulating a synchronous network by an asynchronous one, thus enabling the execution of a synchronous algorithm on an asynchronous network. In this paper a novel technique for constructing network synchronizers is presented. This technique is developed from some basic relationships between synchronizers and the structure of a t-spanning subgraph over the network. As a special result, a synchronizer for the hypercube with optimal time and communication complexities is obtained.

Three parameters characterize the performance of a probabilistic algorithm: T, the runtime of the algorithm; Q, the probability that the algorithm fails to complete the computation in the first T steps and R, the amount of randomness used by the algorithm, measured by the entropy of its random source.We present a tight tradeoff between these three parameters for the problem of oblivious packet routing on N-vertex bounded-degree networks. We prove a (1 - Q) log N/T - log Q - O(1) lower bound for the entropy of a random source of any oblivious packet routing algorithm that routes an arbitrary permutation in T steps with probability 1 - Q. We show that this lower bound is almost optimal by proving the existence, for every e3 log N ≤ T ≤ N1/2, of an oblivious algorithm that terminates in T steps with probability 1 - Q and uses (1-Q+o(1))logN/T-logQ independent random bits.We complement this result with an explicit construction of a family of oblivious algorithms that use less than a factor of log N more random bits than the optimal algorithm achieving the same run-time.

Two conflicting goals play a crucial role in the design of routing schemes for communication networks. A routing scheme should use as short as possible paths for routing messages in the network, while keeping the routing information stored in the processors' local memory as succinct as possible. The efficiency of a routing scheme is measured in terms of its stretch factor - the maximum ratio between the length of a route computed by the scheme and that of a shortest path connecting the same pair of vertices.

Achieving processor cooperation in the presence of faults is a major problem in distributed systems. Popular paradigms such as Byzantine agreement have been studied principally in the context of a complete network. Indeed, Dolev [J. Algorithms, 3 (1982), pp. 14–30] and Hadzilacos [Issues of Fault Tolerance in Concurrent Computations, Ph.D. thesis, Harvard University, Cambridge, MA, 1984] have shown that $\Omega (t)$ connectivity is necessary if the requirement is that all nonfaulty processors decide unanimously, where t is the number of faults to be tolerated. We believe that in forseeable technologies the number of faults will grow with the size of the network while the degree will remain practically fixed. We therefore raise the question whether it is possible to avoid the connectivity requirements by slightly lowering our expectations. In many practical situations we may be willing to “lose” some correct processors and settle for cooperation between the vast majority of the processors. Thus motivated, we present a general simulation technique by which vertices (processors) in almost any network of bounded degree can simulate an algorithm designed for the complete network. The simulation has the property that although some correct processors may be cut off from the majority of the network by faulty processors, the vast majority of the correct processors will be able to communicate among themselves undisturbed by the (arbitrary) behavior of the faulty nodes. We define a new paradigm for distributed computing, almost-everywhere agreement, in which we require only that almost all correct processors reach consensus. Unlike the traditional Byzantine agreement problem, almost-everywhere agreement can be solved on networks of bounded degree. Specifically, we can simulate any sufficiently resilient Byzantine agreement algorithm on a network of bounded degree using our communication scheme described above. Although we “lose” some correct processors, effectively treating them as faulty, the vast majority of correct processors decide on a common value.

The paper deals with achievability of fault tolerant goals in a completely asynchronous distributed system. Fischer, Lynch, and Paterson [FLP] proved that in such a system "nontrivial agreement" cannot be achieved even in the (possible) presence of a single "benign" fault. In contrast, we exhibit two pairs of goals that are achievable even in the presence of up to t ≪ n/2 faulty processors, contradicting the widely held assumption that no nontrivial goals are attainable in such a system. The first pair deals with renaming processors so as to reduce the size of the initial name space. When only uniqueness is required of the new names, we present a lower bound of n + 1 on the size of the new name space, and a renaming algorithm which establishes an upper bound of n + t. In case the new names are required also to preserve the original order, a tight bound of 2t(n- t + 1) - 1 is obtained. The second pair of goals deals with the multi-slot critical section problem. We present algorithms for controlled access to a critical section. As for the number of slots required, a tight bound of t + 1 is proved in case the slots are identical. In the case of distinct slots the upper bound is 2t + 1.

Article Free Access Share on An optimal synchronizer for the hypercube Authors: David Peleg Department of Computer Science, Stanford University, Stanford, California Department of Computer Science, Stanford University, Stanford, CaliforniaView Profile , Jeffrey D. Ullman Department of Computer Science, Stanford University, Stanford, California Department of Computer Science, Stanford University, Stanford, CaliforniaView Profile Authors Info & Claims PODC '87: Proceedings of the sixth annual ACM Symposium on Principles of distributed computingDecember 1987 Pages 77–85https://doi.org/10.1145/41840.41847Published:01 December 1987Publication History 61citation491DownloadsMetricsTotal Citations61Total Downloads491Last 12 Months42Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In a typical parallel or distributed computation model processors are connected by a sparse interconnection network. To establish open-line communication between pairs of processors that wish to communicate interactively, a set of disjoint paths has to be constructed on the network. Since communication needs vary in time, paths have to be dynamically constructed and destroyed.

In this paper concurrent dynamic logic (CDL) is introduced as an extension of dynamic logic tailored toward handling concurrent programs. Properties of CDL are discussed, both on the propositional and first-order level, and the extension is shown to possess most of the desirable properties of DL. Its relationships with the μ-calculus, game logic, DL with recursive procedures, and PTIME are further explored, revealing natural connections between concurrency, recursion, and alternation.

The problem of efficient packet routing is central to the area of communication networks. The special case of permutation packet routing has been extensively studied in the past. While optimal algorithms for permutation routing exist, they do not ‘scale up’ to give optimal solutions for the general case. Using a novel technique we obtain an optimal algorithm for the general packet routing problem. The core of our solution is an algorithm for a generalized version of the token distribution problem. This result has direct applications to the solution of the load balancing problem in distributed systems.

A solution to the following fundamental communication problem is presented. Suppose that n tokens are arbitrarily distributed among n processors with no processor having more than K tokens. The problem is to specify a bounded-degree network topology and an algorithm that can distribute the tokens uniformly among the processors.The first result is a tight $\Theta (K + \log n)$ bound on the complexity of this problem. It is also shown that an approximate version of this problem can be solved deterministically in $O(K + \log n)$ on any expander graph with sufficiently large expansion factor.In the second part of this work, it is shown how to extend the solution for the approximate distribution problem to an optimal probabilistic algorithm for the exact distribution problem on a similar class of expander graphs. Note that communication through an expander graph is a necessary condition for an $O(K + \log n)$ solution of the problem.These results have direct applications to the efficient implementation of many...

We construct fault tolerant routings for several families of graphs, including all graphs of maximal degree less than cnl/3 for some c > 0. With these routings, the diameter of the survival graph is bounded by a constant (e.g., 4 or 6), so long as the number of faults is less than the connectivity of the graph.This result partially confirms a conjecture of Dolev et.al. [DHSS].

Article Fault tolerance in networks of bounded degree Share on Authors: C Dwork IBM Almaden Research Center, San-Jose, California IBM Almaden Research Center, San-Jose, CaliforniaView Profile , D Peleg IBM Almaden Research Center, San-Jose, California IBM Almaden Research Center, San-Jose, CaliforniaView Profile , N Pippenger IBM Almaden Research Center, San-Jose, California IBM Almaden Research Center, San-Jose, CaliforniaView Profile , E Upfal IBM Almaden Research Center, San-Jose, California IBM Almaden Research Center, San-Jose, CaliforniaView Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 370–379https://doi.org/10.1145/12130.12169Online:01 November 1986Publication History 35citation451DownloadsMetricsTotal Citations35Total Downloads451Last 12 Months18Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In this paper we investigate extensions of dynamic logic tailored towards handling concurrent programs, with or without communication. The basic version of concurrent dynamic logic, CDL, is a natural extension of regular DL, and is shown to possess most desirable properties of DL. We further explore its relationships with the μ-calculus, DL with recursive procedures and PTIME, strengthening natural connections between concurrency, recursion and alternation.