Zvi Lotker

TCS Journal 2023 Journal Article

Lower and upper bounds for deterministic convergecast with labeling schemes

• Gewu Bu
• Zvi Lotker
• Maria Potop-Butucaru
• Mikaël Rabie

In wireless networks, broadcast and convergecast are the two most used communication primitives. Broadcast instructs a specific sink (or root) node to send a message to each node in the network. Convergecast instructs each node in the network to send a message to the sink. Due to the collision, without labels, deterministic convergecast is impossible even in a three-node network. Therefore, networking solutions for convergecast are based on probabilistic approaches or use underlying probabilistic medium access protocols such as CSMA/CA or CSMA/CD. In this paper, we focus on deterministic convergecast algorithms enhanced with labeling schemes for wireless networks in collision-presence environment. We investigate two communication modes: half-duplex (nodes either transmit or receive but not both at the same time) and full-duplex (nodes can transmit and receive data at the same time). For these two modes we investigate lower and upper bounds for the time and size of labeling. Even though broadcast and convergecast are similar, we prove that, contrary to broadcast, deterministic convergecast cannot be solved with short labels for some topologies. That is, Ω ( log ⁡ ( Δ ) ) bits are necessary to solve deterministically convergecast where Δ is the maximal degree of a node in the network. We also prove that Ω ( n ) communication time slots are required, where n is the size of network. We provide solutions that are optimal in terms of time (transmission rounds), and by far, the closest to the lower bound in terms of space (message size) for arbitrary scenarios.

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.

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 2021 Journal Article

Selected articles from the 25th International Colloquium on Structural Information and Communication Complexity

• Zvi Lotker
• Boaz Patt-Shamir

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.

SODA Conference 2016 Conference Paper

Distance in the Forest Fire Model How far are you from Eve?

• Varun Kanade
• Reut Levi
• Zvi Lotker
• Frederik Mallmann-Trenn
• Claire Mathieu

TCS Journal 2015 Journal Article

Probabilistic connectivity threshold for directional antenna widths

• Hadassa Daltrophe
• Shlomi Dolev
• Zvi Lotker

Consider the task of maintaining connectivity in a wireless network where the network nodes are equipped with directional antennas. Nodes correspond to points on the unit disk and each uses a directional antenna covering a sector of a given angle α. The width required for a connectivity problem is to find out the necessary and sufficient conditions of α that guarantee connectivity when an antenna's location is uniformly distributed and the orientation of the antenna's sector is either random or fixed. We show that when the number of network nodes is big enough, the required α ˇ approaches zero. Specifically, on the unit disk, assuming uniform orientation, it holds with high probability that the threshold for connectivity is α ˇ = Θ ( log ⁡ n n 4 ). This is shown by the use of Poisson approximation and geometrical considerations. Moreover, when the model is relaxed, assuming that the antenna's orientation is directed towards the center of the disk, we demonstrate that α ˇ = Θ ( log ⁡ n n ) is a necessary and sufficient condition.

TCS Journal 2015 Journal Article

Self-adjusting grid networks to minimize expected path length

• Chen Avin
• Michael Borokhovich
• Bernhard Haeupler
• Zvi Lotker

Given a network infrastructure (e. g. , data-center or on-chip-network) and a distribution on the source-destination requests, the expected path (route) length is an important measure for the performance, efficiency and power consumption of the network. In this work we initiate a study on self-adjusting networks: networks that use local-distributed mechanisms to adjust the position of the nodes (e. g. , virtual machines) in the network to best fit the route requests distribution. Finding the optimal placement of nodes is defined as the minimum expected path length (MEPL) problem. This is a generalization of the minimum linear arrangement (MLA) problem where the network infrastructure is a line and the computation is done centrally. In contrast to previous work, we study the distributed version and give efficient and simple approximation algorithms for interesting and practically relevant special cases of the problem. In particular, we consider grid networks in which the distribution of requests is a symmetric product distribution. In this setting, we show that a simple greedy policy of position switching between neighboring nodes to locally minimize an objective function achieves good approximation ratios. We are able to prove this result using the useful notions of expected rank of the distribution and the expected distance to the center of the graph.

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

TCS Journal 2012 Journal Article

A note on uniform power connectivity in the physical signal to interference plus noise (SINR) model

• Chen Avin
• Zvi Lotker
• Francesco Pasquale
• Yvonne-Anne Pignolet

In this paper, we study the connectivity problem for wireless networks under the physical signal to interference plus noise ratio (SINR) model. Given a set of radio transmitters distributed in some area, we seek to build a directed strongly connected communication graph, and compute an edge coloring of this graph such that the transmitter–receiver pairs in each color class can communicate simultaneously. Depending on the interference model, more or fewer colors, corresponding to the number of frequencies or time slots, are necessary. We consider the interference model that compares the received power of a signal at a receiver to the sum of the strength of other signals plus ambient noise. The strength of a signal is assumed to fade polynomially with the distance from the sender, depending on the so-called path-loss exponent α. We show that, when all transmitters use the same power, the number of colors needed is constant in one-dimensional grids if α > 1 as well as in two-dimensional grids if α > 2. For smaller path-loss exponents and two-dimensional grids we prove upper and lower bounds in the order of O ( log n ) and Ω ( log n / log log n ) for α = 2 and Θ ( n 2 / α − 1 ) for α < 2, respectively. If nodes are distributed uniformly at random on the interval [ 0, 1 ], a regular coloring of O ( log n ) colors guarantees connectivity, while Ω ( log log n ) colors are required for any coloring.

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

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.

TCS Journal 2010 Journal Article

Recovering the long-range links in augmented graphs

• Pierre Fraigniaud
• Emmanuelle Lebhar
• Zvi Lotker

The augmented graph model, as introduced in Kleinberg, STOC (2000) [23], is an appealing model for analyzing navigability in social networks. Informally, this model is defined by a pair ( H, φ ), where H is a graph in which inter-node distances are supposed to be easy to compute or at least easy to estimate. This graph is “augmented” by links, called long-range links, that are selected according to the probability distribution φ. The augmented graph model enables the analysis of greedy routing in augmented graphs G ∈ ( H, φ ). In greedy routing, each intermediate node handling a message for a target t selects among all its neighbors in G the one that is the closest to t in H and forwards the message to it. This paper addresses the problem of checking whether a given graph G is an augmented graph. It answers part of the questions raised by Kleinberg in his Problem 9 (Int. Congress of Math. 2006). More precisely, given G ∈ ( H, φ ), we aim at extracting the base graph H and the long-range links R out of G. We prove that if H has a high clustering coefficient and H has bounded doubling dimension, then a simple local maximum likelihood algorithm enables us to partition the edges of G into two sets H ′ and R ′ such that E ( H ) ⊆ H ′ and the edges in H ′ ∖ E ( H ) are of small stretch, i. e. , the map H is not perturbed too greatly by undetected long-range links remaining in H ′. The perturbation is actually so small that we can prove that the expected performances of greedy routing in G using the distances in H ′ are close to the expected performances of greedy routing using the distances in H. Although this latter result may appear intuitively straightforward, since H ′ ⊇ E ( H ), it is not, as we also show that routing with a map more precise than H may actually damage greedy routing significantly. Finally, we show that in the absence of a hypothesis regarding the high clustering coefficient, any local maximum likelihood algorithm extracting the long-range links can miss the detection of Ω ( n 5 ε / log n ) long-range links of stretch Ω ( n 1 / 5 − ε ) for any 0 < ε < 1 / 5, and thus the map H cannot be recovered with good accuracy.

TCS Journal 2009 Journal Article

Universal augmentation schemes for network navigability

• Pierre Fraigniaud
• Cyril Gavoille
• Adrian Kosowski
• Emmanuelle Lebhar
• Zvi Lotker

Augmented graphs were introduced for the purpose of analyzing the “six degrees of separation between individuals” observed experimentally by the sociologist Standley Milgram in the 60’s. We define an augmented graph as a pair ( G, M ) where G is an n -node graph with nodes labeled in { 1, …, n }, and M is an n × n stochastic matrix. Every node u ∈ V ( G ) is given an extra link, called a long range link, pointing to some node v, called the long range contact of u. The head v of this link is chosen at random by Pr { u → v } = M u, v. In augmented graphs, greedy routing is the oblivious routing process in which every intermediate node chooses from among all its neighbors (including its long range contact) the one that is closest to the target according to the distance measured in the underlying graph G, and forwards to it. The best augmentation scheme known so far ensures that, for any n -node graph G, greedy routing performs in O ( n ) expected number of steps. Our main result is the design of an augmentation scheme that overcomes the O ( n ) barrier. Precisely, we prove that for any n -node graph G whose nodes are arbitrarily labeled in { 1, …, n }, there exists a stochastic matrix M such that greedy routing in ( G, M ) performs in O ̃ ( n 1 / 3 ), where the O ̃ notation ignores the polylogarithmic factors. We prove additional results when the stochastic matrix M is universal to all graphs. In particular, we prove that the O ( n ) barrier can still be overcame for large graph classes even if the matrix M is universal. This however requires an appropriate labeling of the nodes. If the node labeling is arbitrary, then we prove that the O ( n ) barrier cannot be overcome with universal matrices.

FOCS Conference 2002 Conference Paper

Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks

• Guy Even
• Zvi Lotker
• Dana Ron
• Shakhar Smorodinsky

Motivated by a frequency assignment problem in cellular networks, we introduce and study a new coloring problem called minimum conflict-free coloring (min-CF-coloring). In its general form, the input of the min-CF-coloring problem is a set system (X, S), where each S /spl isin/ S is a subset of X. The output is a coloring X of the sets in S that satisfies the following constraint: for every x /spl isin/ X there exists a color i and a unique set S /spl isin/ S, such that x /spl isin/ S and /spl chi/(S) = i. The goal is to minimize the number of colors used by the coloring X. Min-CF-coloring of general set systems is not easier than the classic graph coloring problem. However, in view of our motivation, we consider set systems induced by simple geometric regions in the plane. In particular, we study disks (both congruent and non-congruent), axis-parallel rectangles (with a constant ratio between the smallest and largest rectangle) regular hexagons (with a constant ratio between the smallest and largest hexagon), and general congruent centrally-symmetric convex regions in the plane. In all cases we have coloring algorithms that use O(log n) colors (where n is the number of regions). For rectangles and hexagons we obtain a constant-ratio approximation algorithm when the ratio between the largest and smallest rectangle (hexagon) is a constant. We also show that, even in the case of unit disks, /spl Theta/(log n) colors may be necessary.

STOC Conference 2001 Conference Paper

Buffer overflow management in QoS switches

• Alexander Kesselman
• Zvi Lotker
• Yishay Mansour
• Boaz Patt-Shamir
• Baruch Schieber
• Maxim Sviridenko

We consider two types of buffering policies that are used in network switches supporting QoS (Quality of Service). In the FIFO type, packets must be released in the order they arrive; the difficulty in this case is the limited buffer space. In the bounded-delay type, each packet has a maximum delay time by which it must be released, or otherwise it is lost. We study the cases where the incoming streams overload the buffers, resulting in packet loss. In our model, each packet has an intrinsic value; the goal is to maximize the total value of packets transmitted