David Peleg

TCS Journal 2025 Journal Article

On the role of the equal partition in degree realization by a bipartite graph

• Amotz Bar-Noy
• Toni Böhnlein
• David Peleg
• Dror Rawitz

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.

TCS Journal 2024 Journal Article

Graph realization of distance sets

• Amotz Bar-Noy
• David Peleg
• Mor Perry
• Dror Rawitz

The Distance Realization problem is defined as follows. Given an n × n matrix D of nonnegative integers, interpreted as inter-vertex distances, find an n-vertex weighted or unweighted graph G realizing D, i. e. , whose inter-vertex distances satisfy d i s t G ( i, j ) = D i, j for every 1 ≤ i < j ≤ n, or decide that no such realizing graph exists. The problem was studied for general weighted and unweighted graphs, as well as for cases where the realizing graph is restricted to a specific family of graphs (e. g. , trees or bipartite graphs). An extension of Distance Realization that was studied in the past is where each entry in the matrix D may contain a range of consecutive permissible values. We refer to this extension as Range Distance Realization (or Range-DR). Restricting each range to at most k values yields the problem k-Range Distance Realization (or k-Range-DR). The current paper introduces a new extension of Distance Realization, in which each entry D i, j of the matrix may contain an arbitrary set of acceptable values for the distance between i and j, for every 1 ≤ i < j ≤ n. We refer to this extension as Set Distance Realization (Set-DR), and to the restricted problem where each entry may contain at most k values as k-Set Distance Realization (or k-Set-DR). We first show that 2-Range-DR is NP-hard for unweighted graphs (implying the same for 2-Set-DR). Next we prove that 2-Set-DR is NP-hard for unweighted and weighted trees. Finally, we explore Set-DR where the realization is restricted to the families of stars, paths, cycles, or caterpillars. For the weighted case, our positive results are that there exist polynomial time algorithms for the 2-Set-DR problem on stars, paths and cycles, and for the 1-Set-DR problem on caterpillars. On the hardness side, we prove that 6-Set-DR is NP-hard for stars and 5-Set-DR is NP-hard for paths, cycles and caterpillars. For the unweighted case, our results are the same, except for the case of unweighted stars, for which k-Set-DR is polynomially solvable for any k.

MFCS Conference 2024 Conference Paper

On Key Parameters Affecting the Realizability of Degree Sequences (Invited Paper)

• Amotz Bar-Noy
• Toni Böhnlein
• David Peleg
• Yingli Ran
• Dror Rawitz

Call a sequence d = (d_1, d_2, …, d_n) of positive integers graphic, planaric, outer-planaric, or forestic if it is the degree sequence of some arbitrary, planar, outer-planar, or cycle-free graph G, respectively. The two extreme classes of graphic and forestic sequences were given full characterizations. (The latter has a particularly simple criterion: d is forestic if and only if its volume, ∑ d ≡ ∑_i d_i, satisfies ∑ d ≤ 2n - 2.) In contrast, the problems of fully characterizing planaric and outer-planaric degree sequences are still open. In this paper, we discuss the parameters affecting the realizability of degree sequences by restricted classes of sparse graph, including planar graphs, outerplanar graphs, and some of their subclasses (e. g. , 2-trees and cactus graphs). A key parameter is the volume of the sequence d, namely, ∑ d which is twice the number of edges in the realizing graph. For planar graphs, for example, an obvious consequence of Euler’s theorem is that an n-element sequence d satisfying ∑ d > 4n-6 cannot be planaric. Hence, ∑ d ≤ 4n-6 is a necessary condition for d to be planaric. What about the opposite direction? Is there an upper bound on ∑ d that guarantees that if d is graphic then it is also planaric. Does the answer depend on additional parameters? The same questions apply also to sub-classes of the planar graphs. A concrete example that is illustrated in the technical part of the paper is the class of outer-planaric degree sequences. Denoting the number of 1’s in d by ω₁, we show that for a graphic sequence d, if ω₁ = 0 then d is outer-planaric when ∑ d ≤ 3n-3, and if ω₁ > 0 then d is outer-planaric when ∑ d ≤ 3n-ω₁-2. Conversely, we show that there are graphic sequences that are not outer-planaric with ω₁ = 0 and ∑ d = 3n-2, as well as ones with ω₁ > 0 and ∑ d = 3n-ω₁-1.

MFCS Conference 2024 Conference Paper

Sparse Graphic Degree Sequences Have Planar Realizations

• Amotz Bar-Noy
• Toni Böhnlein
• David Peleg
• Yingli Ran
• Dror Rawitz

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.

MFCS Conference 2022 Conference Paper

Graph Realization of Distance Sets

• Amotz Bar-Noy
• David Peleg
• Mor Perry
• Dror Rawitz

The Distance Realization problem is defined as follows. Given an n × n matrix D of nonnegative integers, interpreted as inter-vertex distances, find an n-vertex weighted or unweighted graph G realizing D, i. e. , whose inter-vertex distances satisfy dist_G(i, j) = D_{i, j} for every 1 ≤ i < j ≤ n, or decide that no such realizing graph exists. The problem was studied for general weighted and unweighted graphs, as well as for cases where the realizing graph is restricted to a specific family of graphs (e. g. , trees or bipartite graphs). An extension of Distance Realization that was studied in the past is where each entry in the matrix D may contain a range of consecutive permissible values. We refer to this extension as Range Distance Realization (or Range-DR). Restricting each range to at most k values yields the problem k-Range Distance Realization (or k-Range-DR). The current paper introduces a new extension of Distance Realization, in which each entry D_{i, j} of the matrix may contain an arbitrary set of acceptable values for the distance between i and j, for every 1 ≤ i < j ≤ n. We refer to this extension as Set Distance Realization (Set-DR), and to the restricted problem where each entry may contain at most k values as k-Set Distance Realization (or k-Set-DR). We first show that 2-Range-DR is NP-hard for unweighted graphs (implying the same for 2-Set-DR). Next we prove that 2-Set-DR is NP-hard for unweighted and weighted trees. We then explore Set-DR where the realization is restricted to the families of stars, paths, or cycles. For the weighted case, our positive results are that for each of these families there exists a polynomial time algorithm for 2-Set-DR. On the hardness side, we prove that 6-Set-DR is NP-hard for stars and 5-Set-DR is NP-hard for paths and cycles. For the unweighted case, our results are the same, except for the case of unweighted stars, for which k-Set-DR is polynomially solvable for any k.

TCS Journal 2022 Journal Article

Hotelling games in fault-prone settings

• Chen Avin
• Avi Cohen
• Zvi Lotker
• David Peleg

The n-player Hotelling game calls for each player to choose a point on the line segment, so as to maximize the size of his Voronoi cell. This paper studies the Hotelling game in fault-prone settings. Two fault models are studied: line faults and player faults. The first model assumes that the environment is prone to failure: with some probability, a disconnection occurs at a random point on the line, splitting it into two separate segments and modifying each player's Voronoi cell accordingly. A complete characterization of the Nash equilibria of this variant is provided for every n. Additionally, a one to one correspondence is shown between equilibria of this variant and of the Hotelling game with no faults. The second fault model assumes the players are prone to failure: each player is removed from the game with some probability, changing the payoffs of the remaining players accordingly. It is shown that for n ≥ 3 this variant of the game has no Nash equilibria.

MFCS Conference 2022 Conference Paper

On the Role of the High-Low Partition in Realizing a Degree Sequence by a Bipartite Graph

• Amotz Bar-Noy
• Toni Böhnlein
• David Peleg
• Dror Rawitz

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 a complete characterization has been established over 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, analysing 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.

TCS Journal 2022 Journal Article

On vertex-weighted realizations of acyclic and general graphs

• Amotz Bar-Noy
• Toni Böhnlein
• David Peleg
• Dror Rawitz

Consider the following natural variation of the degree realization problem. Let G = ( V, E ) be a simple undirected graph of order n. Let f ∈ R ≥ 0 n be a vector of vertex requirements, and let w ∈ R ≥ 0 n be a vector of provided services at the vertices. Then w satisfies f on G if the constraints ∑ j ∈ N ( i ) w j = f i are satisfied for all i ∈ V, where N ( i ) denotes the neighbourhood of vector i. Given a requirements vector f, the Vertex-Weighted Graph Realization problem asks for a suitable graph G and a vector w of provided services that satisfy f on G. In this paper, we consider two avenues. We initiate a study that focuses on weighted realizations where the graph is required to be of a specific class by providing a full characterization of realizable requirement vectors for paths and acyclic graphs. However, checking the respective criteria is shown to be NP-hard. In the second part, we advance the study in general graphs which was started in [2]. For the unsolved cases, the question of whether a vector f is realizable can be formulated as whether its largest requirement lies within certain intervals. We describe several new, realizable intervals and show the existence of an interval that cannot be realized. The complete classification for general graphs is an open problem.

MFCS Conference 2021 Conference Paper

Budgeted Dominating Sets in Uncertain Graphs

• Keerti Choudhary
• Avi Cohen
• N. S. Narayanaswamy
• David Peleg
• R. Vijayaragunathan

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.

TCS Journal 2021 Journal Article

Nonuniform SINR+Voronoi diagrams are effectively uniform

• Erez Kantor
• Zvi Lotker
• Merav Parter
• David Peleg

This paper concerns the behavior of an SINR diagram of wireless systems, composed of a set S of n stations embedded in R d, when restricted to the corresponding Voronoi diagram imposed on S. The diagram obtained by restricting the SINR zones to their corresponding Voronoi cells is referred to hereafter as an SINR+Voronoi diagram. Uniform SINR diagrams, where all stations transmit with the same power, are simple and nicely structured, e. g. , the station reception zones are convex and “fat”. In contrast, nonuniform SINR diagrams might be complex; the reception zones might be fractured and their boundaries might contain many singular points. In this paper, we establish the perhaps surprising fact that a nonuniform SINR+Voronoi diagram is topologically almost as nice as a uniform SINR diagram. In particular, it is convex and effectively 5 fat. This holds for every power assignment, every path-loss parameter α and every dimension d ≥ 1. The convexity property also holds for every SINR threshold β > 0, and the effective fatness property holds for any β > 1. These fundamental properties provide a theoretical justification to engineering practices basing zonal tessellations on the Voronoi diagram, and help to explain the soundness and efficacy of such practices. We also consider two algorithmic applications. The first concerns the Power Control with Voronoi Diagram (PCVD) problem, where given n stations embedded in some polygon P, it is required to find the power assignment that optimizes the SINR threshold of the transmission station s i for any given reception point p ∈ P in its Voronoi cell Image 1. The second application is approximate point location; we show that for SINR+Voronoi zones, this task can be solved considerably more efficiently than in the general non-uniform case.

TCS Journal 2020 Journal Article

Message lower bounds via efficient network synchronization

• Gopal Pandurangan
• David Peleg
• Michele Scquizzato

We present a uniform approach to derive message-time tradeoffs and message lower bounds for synchronous distributed computations using results from communication complexity theory. Since the models used in the classical theory of communication complexity are inherently asynchronous, lower bounds do not directly apply in a synchronous setting. To address this issue, we show a general result called Synchronous Simulation Theorem (SST) which allows to obtain message lower bounds for synchronous distributed computations by leveraging lower bounds on communication complexity. The SST is a by-product of a new efficient synchronizer for complete networks, called σ, which has simulation overheads that are only logarithmic in the number of synchronous rounds with respect to both time and message complexity, even in networks with limited bandwidth. Synchronizer σ is particularly efficient in simulating synchronous algorithms which employ silence, a situation that occurs when in some round no processor sends any message. In particular, a curious property of this synchronizer, which sets it apart from its predecessors, is that it is time-compressing, and hence in some cases it may result in a simulation that is faster than the original execution. While the SST gives near-optimal message lower bounds up to large values of the number of allowed synchronous rounds r (usually polynomial in the size of the input), it fails to provide meaningful bounds when the synchronous algorithm to be simulated may comprise a very large number of rounds. To complement the bounds provided by the SST, we then derive message lower bounds for the synchronous message-passing model that are unconditional, that is, independent of r, by establishing novel lower bounds for multi-party synchronous communication complexity. We apply our approach to show (almost) tight message-time tradeoffs and message lower bounds for several fundamental problems in the synchronous message-passing model of distributed computation. These include sorting, matrix multiplication, and several graph problems. All these lower bounds hold for any distributed algorithms, including randomized Monte Carlo algorithms.

TCS Journal 2020 Journal Article

Mixed fault tolerance in server assignment: Combining reinforcement and backup

• Tal Navon
• David Peleg

We study the mixed approach to fault tolerance in the general context of server assignment in networks. The approach is based on mixing two different existing strategies, namely, reinforcement and backup. The former strategy protects clients by reinforcing the servers assigned to them and making them fault-resistant, possibly at a high cost, while the latter protects clients by assigning to them alternate low price backup servers that can replace their primary servers in case those fail. Applying the mixed approach to fault tolerance gives rise to new fault tolerant variations of known server assignment problems. We introduce several NP-hard problems of this type, including the mixed fault-tolerant dominating set problem, the mixed fault-tolerant centers problem, and the mixed fault-tolerant facility location problem, and present polynomial time approximation algorithms for them, demonstrating the viability of the mixed strategy for server assignment problems.

TCS Journal 2020 Journal Article

Vertex-weighted realizations of graphs

• Amotz Bar-Noy
• David Peleg
• Dror Rawitz

Given a degree sequence d ¯ of length n, the degree realization problem is to decide if d ¯ has a realization, namely, an n-vertex graph whose degree sequence is d ¯, and if so, to construct one such realization. The problem was well researched over the recent decades and plays an important role in the field of Social Networks. In this paper, we consider the following natural generalization of the problem: Let G = ( V, E ) be a simple undirected graph on V = { 1, 2, …, n }. Let f ¯ ∈ R + n be a vector of requirements of the vertices, and let w ¯ ∈ R + n be a vector of provided services at the vertices. The provided services vector w ¯ satisfies the requirements vector f ¯ on G if the constraints ∑ j ∈ Γ ( i ) w j = f i are satisfied for all i ∈ V, where Γ ( i ) denotes the neighborhood of i. We study the following weighted graph realization problem. Given a requirements vector f ¯, the goal is to find a suitable graph G and a vector w ¯ of provided services that satisfy f ¯ on G. In the original degree realization problem, all the provided services must be equal to one. For even n, we show that every requirement vector is realizable. For odd n, the picture is more complicated, as certain requirement vectors are non-realizable. We provide a complete characterization for n = 3 and n = 5, and give (non-matching but close) necessary and sufficient conditions for realizability for odd n ≥ 7. We provide a complete characterization for the variant in which the constraints that should be satisfied are: max j ∈ Γ ( i ) ⁡ w j = f i, for all i ∈ V. As before, we show that every requirement vector can be realized if n is even. For odd n, we show that a vector is realizable if and only if not all requirements are distinct.

TCS Journal 2018 Journal Article

The topology of wireless communication on a line

• Erez Kantor
• Zvi Lotker
• Merav Parter
• David Peleg

This note considers a 1-dimensional wireless network consisting of a set of n stations located on a line, in 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. The behavior of a multi-station network is described using the convenient representation of a reception diagram. 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. We use the minimum principle, recently shown to hold for the SINR function, to derive a tight bound on the number of connected components in 1-dimensional networks.

IJCAI Conference 2017 Conference Paper

Maintaining Communication in Multi-Robot Tree Coverage

• Mor Sinay
• Noa Agmon
• Oleg Maksimov
• Sarit Kraus
• David Peleg

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.

SODA Conference 2016 Conference Paper

Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach

• David Peleg
• Shay Solomon

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 arboricity 1 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.

SODA Conference 2016 Conference Paper

Local-on-Average Distributed Tasks

• Merav Parter
• David Peleg
• Shay Solomon

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 ).

I&C Journal 2015 Journal Article

40th international colloquium on automata, languages and programming

• Fedor V. Fomin
• Marta Kwiatkowska
• David Peleg

TCS Journal 2015 Journal Article

Fault tolerant additive and ( μ, α ) -spanners

• Gilad Braunschvig
• Shiri Chechik
• David Peleg
• Adam Sealfon

Graph spanners are sparse subgraphs that preserve the distances of the original graph up to some approximation ratio (the spanner's stretch). A number of algorithms are known for constructing sparse spanners with small multiplicative or additive stretch. Recently, algorithms were introduced for constructing fault-tolerant multiplicative spanners of general graphs. This paper addresses the analogous problem of constructing fault tolerant additive and ( μ, α ) -spanners for general graphs, and presents a number of (deterministic and randomized) construction algorithms for such spanners.

TCS Journal 2015 Journal Article

Sublinear bounds for randomized leader election

• Shay Kutten
• Gopal Pandurangan
• David Peleg
• Peter Robinson
• Amitabh Trehan

This paper concerns randomized leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete n-node networks that runs in O ( 1 ) rounds and (with high probability) uses only O ( n log 3 / 2 ⁡ n ) messages to elect a unique leader (with high probability). When considering the “explicit” variant of leader election where eventually every node knows the identity of the leader, our algorithm yields the asymptotically optimal bounds of O ( 1 ) rounds and O ( n ) messages. This algorithm is then extended to one solving leader election on any connected non-bipartite n-node graph G in O ( τ ( G ) ) time and O ( τ ( G ) n log 3 / 2 ⁡ n ) messages, where τ ( G ) is the mixing time of a random walk on G. The above result implies highly efficient (sublinear running time and messages) leader election algorithms for networks with small mixing times, such as expanders and hypercubes. In contrast, previous leader election algorithms had at least linear message complexity even in complete graphs. Moreover, super-linear message lower bounds are known for time-efficient deterministic leader election algorithms. Finally, we present an almost matching lower bound for randomized leader election, showing that Ω ( n ) messages are needed for any leader election algorithm that succeeds with probability at least 1 / e + ε, for any small constant ε > 0. We view our results as a step towards understanding the randomized complexity of leader election in distributed networks.

TCS Journal 2015 Journal Article

The fault-tolerant capacitated K-center problem

• Shiri Chechik
• David Peleg

The capacitated K-center (CKC) problem calls for locating K service centers in the vertices of a given weighted graph, and assigning each vertex as a client to one of the centers, where each service center has a limited service capacity and thus may be assigned at most L clients, so as to minimize the maximum distance from a vertex to its assigned service center. This paper studies the fault-tolerant version of this problem, where one or more service centers might fail simultaneously. We consider two variants of the problem. The first is the α-fault-tolerant capacitated K-center ( α - F T - C K C ) problem. In this version, after the failure of some centers, all nodes are allowed to be reassigned to alternate centers. The more conservative version of this problem, hereafter referred to as the α-fault-tolerant conservative capacitated K-center ( α - F T - C K C ) problem, is similar to the α - F T - C K C problem, except that after the failure of some centers, only the nodes that were assigned to those centers before the failure are allowed to be reassigned to other centers. We present polynomial time algorithms that yield 9-approximation for the α - F T - C K C problem and 17-approximation for the α - F T - C K C problem.

FOCS Conference 2015 Conference Paper

The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication

• Erez Kantor
• Zvi Lotker
• Merav Parter
• David Peleg

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.

SODA Conference 2014 Conference Paper

Fault Tolerant Approximate BFS Structures

• Merav Parter
• David Peleg

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 3 n edges (improving by an O (log n ) 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) log n ) 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 (log n )] there exists an n -vertex graph G with a source s for which any (1, β ) FT-ABFS structure rooted at s has Ω( n 1+∊( β ) ) edges, for some function ∊( β ) ∊ (0, 1). In particular, (1, 3) FT-ABFS structures admit a lower bound of Ω( n 5/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 ( n 4/3 ) edges.

TCS Journal 2014 Journal Article

Robust fault tolerant uncapacitated facility location

• Shiri Chechik
• David Peleg

In the 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 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 α facilities. We present a polynomial time algorithm that yields a 6. 464-approximation for this problem with at most one failure and a 1. 488 + 7. 464 α -approximation for the problem with at most α failures for a fixed α > 1. We also show that the RFTFL problem is NP-hard even on trees, and even in the case of a single failure.

SODA Conference 2013 Conference Paper

Generalized Perron-Frobenius Theorem for Multiple Choice Matrices, and Applications

• Chen Avin
• Michael Borokhovich
• Yoram Haddad 0001
• Erez Kantor
• Zvi Lotker
• Merav Parter
• David Peleg

SODA Conference 2012 Conference Paper

Gathering despite mischief

• Yoann Dieudonné
• Andrzej Pelc
• David Peleg

SODA Conference 2012 Conference Paper

SINR diagram with interference cancellation

• Chen Avin
• Asaf Cohen 0001
• Yoram Haddad 0001
• Erez Kantor
• Zvi Lotker
• Merav Parter
• David Peleg

I&C Journal 2012 Journal Article

Sparse reliable graph backbones

• Shiri Chechik
• Yuval Emek
• Boaz Patt-Shamir
• David Peleg

Given a connected graph G and a failure probability p ( e ) for each edge e in G, the reliability of G is the probability that G remains connected when each edge e is removed independently with probability p ( e ). In this paper it is shown that every n-vertex graph contains a sparse backbone, i. e. , a spanning subgraph with O ( n log n ) edges whose reliability is at least ( 1 − n − Ω ( 1 ) ) times that of G. Moreover, for any pair of vertices s, t in G, the ( s, t ) -reliability of the backbone, namely, the probability that s and t remain connected, is also at least ( 1 − n − Ω ( 1 ) ) times that of G. Our proof is based on a polynomial time randomized algorithm for constructing the backbone. In addition, it is shown that the constructed backbone has nearly the same Tutte polynomial as the original graph (in the quarter-plane x ⩾ 1, y > 1 ), and hence the graph and its backbone share many additional features encoded by the Tutte polynomial.

STOC Conference 2011 Conference Paper

Distributed verification and hardness of distributed approximation

• Atish Das Sarma
• Stephan Holzer
• Liah Kor
• Amos Korman
• Danupon Nanongkai
• Gopal Pandurangan
• David Peleg
• Roger Wattenhofer

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.

FOCS Conference 2011 Conference Paper

Local Distributed Decision

• Pierre Fraigniaud
• Amos Korman
• David Peleg

A central theme in distributed network algorithms concerns understanding and coping with the issue of {\em 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 \emph{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 $\cal{LOCAL}$ model of computation and define $LD(t)$ (for {\em 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\in (0, 1]$ such that $p^2+q\leq 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\in (0, 1]$ such that $p^2+q&gt, 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 \emph{all} languages \emph{in constant time}. Finally, we introduce the notion of local reduction, and establish some completeness results.

STOC Conference 2011 Conference Paper

The topology of wireless communication

• Erez Kantor
• Zvi Lotker
• Merav Parter
• David Peleg

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.

AIJ Journal 2009 Journal Article

Computing the fault tolerance of multi-agent deployment

• Yingqian Zhang
• Efrat Manisterski
• Sarit Kraus
• V.S. Subrahmanian
• David Peleg

A deployment of a multi-agent system on a network refers to the placement of one or more copies of each agent on network hosts, in such a manner that the memory constraints of each node are satisfied. Finding the deployment that is most likely to tolerate faults (i. e. have at least one copy of each agent functioning and in communication with other agents) is a challenge. In this paper, we address the problem of finding the probability of survival of a deployment (i. e. the probability that a deployment will tolerate faults), under the assumption that node failures are independent. We show that the problem of computing the survival probability of a deployment is at least NP-hard. Moreover, it is hard to approximate. We produce two algorithms to accurately compute the probability of survival of a deployment—these algorithms are expectedly exponential. We also produce five heuristic algorithms to estimate survival probabilities—these algorithms work in acceptable time frames. We report on a detailed set of experiments to determine the conditions under which some of these algorithms perform better than the others.

TCS Journal 2009 Journal Article

Distributed algorithms for partitioning a swarm of autonomous mobile robots

• Asaf Efrima
• David Peleg

A number of recent studies address systems of mobile autonomous robots from a distributed computing point of view. Although such systems employ robots that are relatively weak and simple (i. e. , dimensionless, oblivious and anonymous), they are nevertheless expected to have strong fault tolerance capabilities as a group. This paper studies the partitioning problem, where n robots must divide themselves into k size-balanced groups, and examines the impact of common orientation on the solvability of this problem. First, deterministic crash-fault-tolerant algorithms are given for the problem in the asynchronous full-compass and semi-synchronous half-compass models, and a randomized algorithm is given for the semi-synchronous no-compass model. Next, the role of common orientation shared by the robots is examined. Necessary and sufficient conditions for the partitioning problem to be solvable are given in the different timing models. Finally, the problem is proved to be unsolvable in the no-compass synchronous model.

STOC Conference 2009 Conference Paper

Fault-tolerant spanners for general graphs

• Shiri Chechik
• Michael Langberg
• David Peleg
• Liam Roditty

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(n 1+1/k ), and this size-stretch tradeoff is conjectured to be tight.

SODA Conference 2008 Conference Paper

A near-linear time algorithm for computing replacement paths in planar directed graphs

• Yuval Emek
• David Peleg
• Liam Roditty

TCS Journal 2008 Journal Article

Local spreading algorithms for autonomous robot systems

• Reuven Cohen
• David Peleg

This paper studies local algorithms for autonomous robot systems, namely, algorithms that use only information of the positions of a bounded number of their nearest neighbors. The paper focuses on the spreading problem. It defines measures for the quality of spreading, presents a local algorithm for the one-dimensional spreading problem, proves its convergence to the equally spaced configuration and discusses its convergence rate in the synchronous and semi-synchronous settings. It then presents a local algorithm achieving the exact equally spaced configuration in finite time in the synchronous setting, and proves it is time optimal for local algorithms. Finally, the paper also proposes a possible algorithm for the two-dimensional case and presents partial simulation results of its effectiveness.

TCS Journal 2007 Journal Article

Approximation algorithm for hotlink assignment in the greedy model

• Rachel Matichin
• David Peleg

Link-based information structures such as the web can be enhanced through the addition of hotlinks. Assume that each node in the information structure is associated with a weight representing the access frequency of the node by users. In order to access a particular node, the user must follow a path leading to it from the root. By adding new hotlinks to the tree, it may be possible to reduce the access cost of the system, namely, the expected number of steps needed to reach a leaf from the root, assuming the user can decide which hotlinks to follow in each step. The hotlink assignment problem involves finding a set of hotlinks (with at most K = O ( 1 ) hotlinks emanating from every node) maximizing the gain in the expected cost. The paper addresses this problem in two user models, namely, the traditional clairvoyant user model employed in [P. Bose, J. Czyzowicz, L. Gasieniec, E. Kranakis, D. Krizanc, A. Pelc, M. V. Martin, Strategies for hotlink assignments, in: Proc. 11th Symp. on Algorithms and Computation, 2000, pp. 23–34; E. Kranakis, D. Krizanc, S. Shende, Approximating hotlink assignments, in: Proc. 12th Symp. on Algorithms and Computation, 2001, pp. 756–767; P. Bose, D. Krizanc, S. Langerman, P. Morin, Asymmetrical communication protocols via hotlink assignments, in: Proc. 9th Colloq. on Structural Information and Communication Complexity, 2002, pp. 33–39; R. Matichin, D. Peleg, Approximation algorithm for hotlink assignments in web directories, in: Proc. Workshop on Algorithms and Data Structures, 2003, pp. 271–280] and the more realistic greedy user model recently introduced in [O. Gerstel, S. Kutten, R. Matichin, D. Peleg, Hotlink enhancement algorithms for web directories, in: Proc. 14th Symp. on Algorithms and Computation, 2003, pp. 68–77], and presents a polynomial time 2-approximation algorithm for the hotlink assignment problem on rooted directed trees.

TCS Journal 2007 Journal Article

Feasibility and complexity of broadcasting with random transmission failures

• Andrzej Pelc
• David Peleg

Fault-tolerant broadcasting in the message passing and radio models is considered under a probabilistic failure model. At each step, the transmitter of each node may fail with fixed constant probability p < 1, and failures are independent. Both node-omission and malicious transmission failures are studied. Our goal is to establish conditions on feasibility and to estimate the (synchronous) time complexity of almost-safe broadcasting (i. e. , broadcasting which is correct with probability at least 1 − 1 / n for n -node graphs and for sufficiently large n ) under these scenarios. If only node-omission failures are assumed, almost-safe broadcasting is feasible for any p < 1, in both communication models. For malicious transmission failures, almost-safe broadcasting in the message passing model is feasible iff p < 1 / 2, and in the radio model it is feasible iff p < ( 1 − p ) Δ + 1, where Δ is the maximum degree of the network. For the time complexity of almost-safe broadcasting, a number of upper and lower bounds are given in the various models.

I&C Journal 2007 Journal Article

Labeling schemes for weighted dynamic trees

• Amos Korman
• David Peleg

A Distance labeling scheme is a type of localized network representation in which short labels are assigned to the vertices, allowing one to infer the distance between any two vertices directly from their labels, without using any additional information sources. As most applications for network representations in general, and distance labeling schemes in particular, concern large and dynamically changing networks, it is of interest to focus on distributed dynamic labeling schemes. The paper considers dynamic weighted trees where the vertices of the trees are fixed but the (positive integral) weights of the edges may change. The two models considered are the edge-dynamic model, where from time to time some edge changes its weight by a fixed quanta, and the increasing-dynamic model in which edge weights can only grow. The paper presents distributed approximate distance labeling schemes for the two dynamic models, which are efficient in terms of the required label size and communication complexity involved in updating the labels following the weight changes.

TCS Journal 2007 Journal Article

Preface

• Andrzej Pelc
• David Peleg
• Michel Raynal

SODA Conference 2006 Conference Paper

A tight upper bound on the probabilistic embedding of series-parallel graphs

• Yuval Emek
• David Peleg

TCS Journal 2005 Journal Article

Approximating k-spanner problems for k > 2

• Michael Elkin
• David Peleg

Given a graph G = ( V, E ), a subgraph G ′ = ( V, H ), H ⊆ E is a k-spanner of G if for any pair of vertices u, w ∈ V it satisfies d H ( u, w ) ⩽ kd G ( u, w ). The basic k-spanner problem is to find a k-spanner of a given graph G with the smallest possible number of edges. This paper considers approximation algorithms for this and some related problems for k > 2, known to be Ω ( 2 log 1 - μ n ) -inapproximable. The basic k-spanner problem over undirected graphs with k > 2 has been given a sublinear ratio approximation algorithm (with ratio roughly O ( n 2 / ( k + 1 ) ) ), but no such algorithms were known for other variants of the problem, including the directed and the client–server variants, as well as for the related k-DSS problem. We present the first approximation algorithms for these problems with sublinear approximation ratio. The second contribution of this paper is in characterizing some wide families of graphs on which the problems do admit a logarithmic and a polylogarithmic approximation ratios. These families are characterized as containing graphs that have optimal or “near-optimal” spanners with certain desirable properties, such as being a tree, having low arboricity or having low girth. All our results generalize to the directed and the client–server variants of the problems. As a simple corollary, we present an algorithm that given a graph G builds a subgraph with O ˜ ( n ) edges and stretch bounded by the tree-stretch of G, namely the minimum maximal stretch of a spanning tree for G. The analysis of our algorithms involves the novel notion of edge-dominating systems developed in the paper. The technique introduced in the paper reduces the studied algorithmic approximability questions on k-spanners to purely graph-theoretical questions concerning the existence of certain combinatorial objects in families of graphs.

TCS Journal 2005 Journal Article

Graph exploration by a finite automaton

• Pierre Fraigniaud
• David Ilcinkas
• Guy Peer
• Andrzej Pelc
• David Peleg

A finite automaton, simply referred to as a robot, has to explore a graph whose nodes are unlabeled and whose edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the graph or of its size. Its task is to traverse all the edges of the graph. We first show that, for any K-state robot and any d ⩾ 3, there exists a planar graph of maximum degree d with at most K + 1 nodes that the robot cannot explore. This bound improves all previous bounds in the literature. More interestingly, we show that, in order to explore all graphs of diameter D and maximum degree d, a robot needs Ω ( D log d ) memory bits, even if we restrict the exploration to planar graphs. This latter bound is tight. Indeed, a simple DFS up to depth D + 1 enables a robot to explore any graph of diameter D and maximum degree d using a memory of size O ( D log d ) bits. We thus prove that the worst case space complexity of graph exploration is Θ ( D log d ) bits.

SODA Conference 2005 Conference Paper

Improved recommendation systems

• Baruch Awerbuch
• Boaz Patt-Shamir
• David Peleg
• Mark R. Tuttle

TCS Journal 2005 Journal Article

Informative labeling schemes for graphs

• David Peleg

This paper introduces the notion of informative labeling schemes for arbitrary graphs. Let f ( W ) be a function on subsets of vertices W. An f labeling scheme labels the vertices of a weighted graph G in such a way that f ( W ) can be inferred (or at least approximated) efficiently for any vertex subset W of G by merely inspecting the labels of the vertices of W, without having to use any additional information sources. A number of results illustrating this notion are presented in the paper. We begin by developing f labeling schemes for three functions f over the class of n-vertex trees. The first function, SepLevel, gives the separation level of any two vertices in the tree, namely, the depth of their least common ancestor. The second, LCA, provides the least common ancestor of any two vertices. The third, Center, yields the center of any three given vertices v 1, v 2, v 3 in the tree, namely, the unique vertex z connected to them by three edge-disjoint paths. All of these three labeling schemes use O ( log 2 n ) -bit labels, which is shown to be asymptotically optimal. Our main results concern the function Steiner ( W ), defined for weighted graphs. For any vertex subset W in the weighted graph G, Steiner ( W ) represents the weight of the Steiner tree spanning the vertices of W in G. Considering the class of n-vertex trees with M-bit edge weights, it is shown that for this class there exists a Steiner labeling scheme using O ( ( M + log n ) log n ) bit labels, which is asymptotically optimal. It is then shown that for the class of arbitrary n-vertex graphs with M-bit edge weights, there exists an approximate-Steiner labeling scheme, providing an estimate (up to a factor of O ( log n ) ) for the Steiner weight Steiner ( W ) of a given set of vertices W, using O ( ( M + log n ) log 2 n ) bit labels.

TCS Journal 2005 Journal Article

Preface

• David Peleg
• Jop Sibeyn

SODA Conference 2004 Conference Paper

Approximating Minimum Max-Stretch spanning Trees on unweighted graphs

• Yuval Emek
• David Peleg

SODA Conference 2004 Conference Paper

Fault-tolerant gathering algorithms for autonomous mobile robots

• Noa Agmon
• David Peleg

MFCS Conference 2004 Conference Paper

Graph Exploration by a Finite Automaton

• Pierre Fraigniaud
• David Ilcinkas
• Guy Peer
• Andrzej Pelc
• David Peleg

Abstract A finite automaton, simply referred to as a robot, has to explore a graph whose nodes are unlabeled and whose edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the graph or of its size. Its task is to traverse all the edges of the graph. We first show that, for any K -state robot and any d ≥ 3, there exists a planar graph of maximum degree d with at most K +1 nodes that the robot cannot explore. This bound improves all previous bounds in the literature. More interestingly, we show that, in order to explore all graphs of diameter D and maximum degree d, a robot needs Ω( D log d ) memory bits, even if we restrict the exploration to planar graphs. This latter bound is tight. Indeed, a simple DFS at depth D +1 enables a robot to explore any graph of diameter D and maximum degree d using a memory of size O ( D log d ) bits. We thus prove that the worst case space complexity of graph exploration is Θ( D log d ) bits.

TCS Journal 2003 Journal Article

Directed virtual path layouts in ATM networks

• Jean-Claude Bermond
• Nausica Marlin
• David Peleg
• Stéphane Perennes

Motivated by asynchronous transfer mode in telecommunication networks, we investigate the problem of designing a directed virtual topology on a directed physical topology, which consists in finding a set of directed virtual paths (VPs) satisfying some constraints in terms of load (the number of VPs sharing a physical link) and hop count (the number of VPs used to establish a connection). For both general and particular networks, such as paths, cycles, meshes, tori and trees, we derive tight bounds on the virtual diameter (the maximum hop count for a connection) as a function of the network capacity (the maximum load of a physical link).

TCS Journal 2002 Journal Article

Faster exact solutions for some NP-hard problems

• Limor Drori
• David Peleg

This paper considers a number of NP-complete problems, and provides faster algorithms for solving them. The solutions are based on a recursive partitioning of the problem domain, and careful elimination of some of the branches along the search without actually checking them. The time complexity of the proposed algorithms is of the form O(2εn) for constant 0<ε<1, where n is the output size of the problem. In particular, such algorithms are presented for the Exact SAT and Exact Hitting Set problems (with ε=0. 3212), and for the Exact 3SAT problem (with ε=0. 2072). Both algorithms improve on previous ones proposed in the literature.

SODA Conference 2002 Conference Paper

Labeling schemes for flow and connectivity

• Michal Katz
• Nir A. Katz
• Amos Korman
• David Peleg

TCS Journal 2002 Journal Article

Local majorities, coalitions and monopolies in graphs: a review

• David Peleg

This paper provides an overview of recent developments concerning the process of local majority voting in graphs, and its basic properties, from graph theoretic and algorithmic standpoints.

MFCS Conference 2002 Invited Paper

Low Stretch Spanning Trees

• David Peleg

Abstract The paper provides a brief review of problems and results concerning low stretch and low communication spanning trees for graphs.

STOC Conference 2001 Conference Paper

(1+epsilon, beta)-spanner constructions for general graphs

• Michael Elkin
• David Peleg

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.

SODA Conference 2001 Conference Paper

Distance labeling in graphs

• Cyril Gavoille
• David Peleg
• Stephane Perennes
• Ran Raz

I&C Journal 2001 Journal Article

Distributed Probabilistic Polling and Applications to Proportionate Agreement

• Yehuda Hassin
• David Peleg

This paper considers a probabilistic local polling process, examines its properties, and proposes its use in the context of distributed network protocols for achieving consensus. The resulting consensus algorithm is very simple and lightweight, yet it enjoys some desirable properties, such as proportionate agreement (namely, reaching a consensus value of one with probability proportional to the number of ones in the inputs), resilience against dynamic link failures and recoveries, and (weak) self-stabilization. The paper also investigates the maximum influence of small sets and establishes results analogous to those obtained for the problem in the deterministic polling model.

TCS Journal 2001 Journal Article

Generalized submodular cover problems and applications

• Judit Bar-Ilan
• Guy Kortsarz
• David Peleg

The greedy approach has been successfully applied in the past to produce logarithmic ratio approximations to NP-hard problems under certain conditions. The problems for which these conditions hold are known as submodular cover problems. The current paper 3 3 A preliminary version of this paper has appeared as an extended abstract in Proc. 4th Israel Symp. on the Theory of Computing and Systems, Jerusalem, Israel, June 1996. extends the applicability of the greedy approach to wider classes of problems. The usefulness of our extensions is illustrated by giving new approximate solutions for two different types of problems. The first problem is that of finding the spanning tree of minimum weight among those whose diameter is bounded by D. A logarithmic ratio approximation algorithm is given for the cases of D=4 and 5. This approximation ratio is also proved to be the best possible, unless P=NP. The second type involves some (known and new) center selection problems, for which new logarithmic ratio approximation algorithms are given. Again, it is shown that the ratio must be at least logarithmic unless P=NP.

MFCS Conference 2000 Conference Paper

Informative Labeling Schemes for Graphs

• David Peleg

Abstract This paper introduces and studies the notion of informative labeling schemes for arbitrary graphs. Let f(W) be a function on subsets of vertices W. An f labeling scheme labels the vertices of a weighted graph G in such a way that f(W) can be inferred efficiently for any vertex subset W of G by merely inspecting the labels of the vertices of W, without having to use any additional information sources. The paper develops f labeling schemes for some functions f over the class of n -vertex trees, including SepLevel, the separation level of any two vertices in the tree, LCA, the least common ancestor of any two vertices, and Center, the center of any three given vertices in the tree. These schemes use O(log 2 n)-bit labels, which is asymptotically optimal. We then turn to weighted graphs and consider the function Steiner (W), denoting the weight of the Steiner tree spanning the vertices of W in the graph. For n -vertex weighted trees with M-bit edge weights, it is shown that there exists a Steiner labeling scheme using O((M+log n) log n) bit labels, which is asymptotically optimal. In the full paper it is shown that for the class of arbitrary n -vertex graphs with M -bit edge weights, there exists an approximate- Steiner labeling scheme, providing an estimate (up to a logarithmic factor) for Steiner (W) using O((M + logn) log 2 n ) bit labels.

FOCS Conference 1999 Conference Paper

A Near-Tight Lower Bound on the Time Complexity of Distributed MST Construction

• David Peleg
• Vitaly Rubinovich

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).

TCS Journal 1998 Journal Article

Approximate maxima finding of continuous functions under restricted budget

• Evangelos Kranakis
• Danny Krizanc
• Andrzej Pelc
• David Peleg

A function is distributed among nodes of a graph in a “continuous” (or “slowly changing”) way, i. e. , such that the difference between values stored at adjacent nodes is small. The goal is to find a node of maximum value by probing some nodes under a restricted budget. Every node has an associated cost which has to be paid for probing it and a probe reveals the value of the node. If the total budget is too small to allow probing every node, it is impossible to find the maximum value in the worst case. Hence we seek an Approximate Maxima Finding (AMF) algorithm that offers the best worst-case guarantee g, i. e. , for any continuous distribution of values it finds a node whose value differs from the maximum value by at most g. AMF in graphs is related to a generalization of the multicenter problem and we get new results for this problem as well. For example, we give a polynomial algorithm to find a minimum cost solution for the multicenter problem on a tree, with arbitrary node costs.

SODA Conference 1997 Conference Paper

Approximating Shallow-Light Trees (Extended Abstract)

• Guy Kortsarz
• David Peleg

I&C Journal 1996 Journal Article

Scheduling Jobs Using Common Resources

• Judit Bar-Ilan
• David Peleg

This paper examines the problem of distributed resource allocation in different models of computation and communication in distributed systems, and presents a number of time optimal (randomized and deterministic) allocation algorithms. We consider the dining/drinking philosophers problem as presented in [B. Awerbuch and M. Saks, in“FOCS, ” pp. 65–74. IEEE, New York, 1990]. In the algorithm presented in that paper, the delay from the creation of a job to the time it started executing depends quadratically on the number of jobs conflicting with it. In this paper we improve this result by presenting an algorithm for which the dependence becomes linear, which is optimal.

STOC Conference 1995 Conference Paper

Bubbles: adaptive routing scheme for high-speed dynamic networks (Extended Abstract)

• Shlomi Dolev
• Evangelos Kranakis
• Danny Krizanc
• David Peleg

FOCS Conference 1995 Conference Paper

Tight Fault Locality (Extended Abstract)

• Shay Kutten
• David Peleg

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.

SODA Conference 1994 Conference Paper

Generating Low-Degree 2-Spanners

• Guy Kortsarz
• David Peleg

FOCS Conference 1993 Conference Paper

A Sub-Linear Time Distributed Algorithm for Minimum-Weight Spanning Trees (Extended Abstract)

• Juan A. Garay 0001
• Shay Kutten
• David Peleg

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. >

FOCS Conference 1993 Conference Paper

Near-Linear Cost Sequential and Distribured Constructions of Sparse Neighborhood Covers

• Baruch Awerbuch
• Bonnie Berger
• Lenore Cowen
• David Peleg

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)). >

FOCS Conference 1993 Conference Paper

On Choosing a Dense Subgraph (Extended Abstract)

• Guy Kortsarz
• David Peleg

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. >

TCS Journal 1993 Journal Article

Time-space tradeoffs for set operations

• Boaz Patt-Shamir
• David Peleg

This paper considers time-space tradeoffs for various set operations. Denoting the time requirement of an algorithm by T and its space requirement by S, it is shown that TS=Ω(n2) for set complementation and TS=Ω(n 3 2 ) for set intersection, in the R-way branching program model. In the more restricted model of comparison branching programs, the paper provides two additional types of results. A tradeoff of TS=Ω(n2-ε(n)), derived from Yao's lower bound for element distinctness, is shown for set disjointness, set union and set intersection [where ε(n)=O((logn)− 1 2 )]. A bound of TS=Ω(n 3 2 ) is shown for deciding set equality and set inclusion. Finally, a classification of set operations is presented, and it is shown that all problems of a large naturally arising class are as hard as the problems bounded in this paper.

STOC Conference 1992 Conference Paper

Adapting to Asynchronous Dynamic Networks (Extended Abstract)

• Baruch Awerbuch
• Boaz Patt-Shamir
• David Peleg
• Michael E. Saks

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.

STOC Conference 1992 Conference Paper

Competitive Distributed Job Scheduling (Extended Abstract)

• Baruch Awerbuch
• Shay Kutten
• David Peleg

I&C Journal 1991 Journal Article

Fault-tolerant critical section management in asynchronous environments

• Amotz Bar-Noy
• Danny Dolev
• Daphne Koller
• David Peleg

The paper deals with the problem of managing a fault-tolerant critical section in a completely asynchronous distributed network. The existence of a solution to this problem should be contrasted with a basic result of Fischer, Lynch, and Paterson, proving that in a completely asynchronous network, “nontrivial agreement” cannot be achieved even when only a single “benign” processor failure is possible. We present solutions to several versions of the critical section problem in this model. Denote by t the maximum number of possible faulty processors. Processors are allowed to fail while in the critical section, and therefore the critical section must have at least t + 1 slots. In the case where the slots are identical we present two algorithms which require t + 1 slots. The first is very simple, but requires every non-faulty processor to use the critical section infinitely often. The second solution allows non-faulty processors to quit. For distinct slots we present an algorithm that requires 2t + 1 slots.

STOC Conference 1990 Conference Paper

Computing with Unreliable Information (Preliminary Version)

• Uriel Feige
• David Peleg
• Prabhakar Raghavan
• Eli Upfal

FOCS Conference 1990 Conference Paper

Network Synchronization with Polylogarithmic Overhead

• Baruch Awerbuch
• David Peleg

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. >

FOCS Conference 1990 Conference Paper

Sparse Partitions (Extended Abstract)

• Baruch Awerbuch
• David Peleg

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. >

STOC Conference 1989 Conference Paper

Compact Distributed Data Structures for Adaptive Routing (Extended Abstract)

• Baruch Awerbuch
• Amotz Bar-Noy
• Nati Linial
• David Peleg

STOC Conference 1989 Conference Paper

On the Complexity of Radio Communication (Extended Abstract)

• Noga Alon
• Amotz Bar-Noy
• Nati Linial
• David Peleg

STOC Conference 1988 Conference Paper

A Time-Randomness Tradeoff for Oblivious Routing (Extended Abstract)

• Danny Krizanc
• David Peleg
• Eli Upfal

STOC Conference 1988 Conference Paper

A Tradeoff between Space and Efficiency for Routing Tables (Extended Abstract)

• David Peleg
• Eli Upfal

FOCS Conference 1987 Conference Paper

Achievable Cases in an Asynchronous Environment (Extended Abstract)

• Hagit Attiya
• Amotz Bar-Noy
• Danny Dolev
• Daphne Koller
• David Peleg
• Rüdiger Reischuk

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.

TCS Journal 1987 Journal Article

Concurrent program schemes and their logics

• David Peleg

We define and investigate several classes of concurrent program schemes, including goto schemes and two versions of structured schemes, based on extensions of the regular expressions to trees. The schemes are studied on the first-order, Boolean-variable and propositional levels. We also define and study the dynamic logics based on these classes of schemes, including issues of decidability and axiomatization.

STOC Conference 1987 Conference Paper

Constructing Disjoint Paths on Expander Graphs (Extended Abstract)

• David Peleg
• Eli Upfal

I&C Journal 1987 Journal Article

On fault tolerant routings in general networks

• David Peleg
• Barbara Simons

We construct fault-tolerant routings for several families of graphs, including all graphs of maximal degree less than cn 1 3 for some c>0. With these routings, the diameter of the surviving 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. (1984, in “Proceedings, 16th ACM Symp. on Theory of Comput. ,” pp. 526–535).

TCS Journal 1987 Journal Article

The generalized packet routing problem

• David Peleg
• Eli Upfal

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.

STOC Conference 1986 Conference Paper

Fault Tolerance in Networks of Bounded Degree (Preliminary Version)

• Cynthia Dwork
• David Peleg
• Nicholas Pippenger
• Eli Upfal

FOCS Conference 1986 Conference Paper

The Token Distribution Problem (Preliminary Version)

• David Peleg
• Eli Upfal

STOC Conference 1985 Conference Paper

Concurrent Dynamic Logic (Extended Abstract)

• David Peleg