Reconfiguration schedules, i.e., sequences that gradually transform one solution of a problem to another while always maintaining feasibility, have been extensively studied. Most research has dealt with the decision problem of whether a reconfiguration schedule exists, and the complexity of finding one. A prime example is the reconfiguration of vertex covers. We initiate the study of batched vertex cover reconfiguration, which allows to reconfigure multiple vertices concurrently while requiring that any adversarial reconfiguration order within a batch maintains feasibility. The latter provides robustness, e.g., if the simultaneous reconfiguration of a batch cannot be guaranteed. The quality of a schedule is measured by the number of batches until all nodes are reconfigured, and its cost, i.e., the maximum size of an intermediate vertex cover. To set a baseline for batch reconfiguration, we show that for graphs belonging to one of the classes $\{\mathsf{cycles, trees, forests, chordal, cactus, even\text{-}hole\text{-}free, claw\text{-}free}\}$, there are schedules that use $O(\varepsilon^{-1})$ batches and incur only a $1+\varepsilon$ multiplicative increase in cost over the best sequential schedules. Our main contribution is to compute such batch schedules in $O(\varepsilon^{-1}\log^* n)$ distributed time, which we also show to be tight. Further, we show that once we step out of these graph classes we face a very different situation. There are graph classes on which no efficient distributed algorithm can obtain the best (or almost best) existing schedule. Moreover, there are classes of bounded degree graphs which do not admit any reconfiguration schedules without incurring a large multiplicative increase in the cost at all.

We present a new technique to efficiently sample and communicate a large number of elements from a distributed sampling space. When used in the context of a recent Local algorithm for (degree +1)-list-coloring (D1LC), this allows us to solve D1LC in O(log5 logn) Congest rounds, and in only O(log* n) rounds when the graph has minimum degree Ω(log7 n), w.h.p.

We present a new approach to randomized distributed graph coloring that is simpler and more efficient than previous ones. In particular, it allows us to tackle the (deg+1)-list-coloring (D1LC) problem, where each node v of degree dv is assigned a palette of dv+1 colors, and the objective is to find a proper coloring using these palettes. While for (Δ+1)-coloring (where Δ is the maximum degree), there is a fast randomized distributed O(log3logn)-round algorithm due to Chang, Li, and Pettie, no o(logn)-round algorithms are known for the D1LC problem.

Abstract Linial’s famous color reduction algorithm reduces a given m-coloring of a graph with maximum degree $$\varDelta $$ Δ to an $$O(\varDelta ^2\log m)$$ O ( Δ 2 log m ) -coloring, in a single round in the LOCAL model. We give a similar result when nodes are restricted to choose their color from a list of allowed colors: given an m-coloring in a directed graph of maximum outdegree $$\beta $$ β , if every node has a list of size $$\varOmega (\beta ^2 (\log \beta +\log \log m + \log \log |{\mathcal {C}}|))$$ Ω ( β 2 ( log β + log log m + log log | C | ) ) from a color space $${\mathcal {C}}$$ C then they can select a color in two rounds in the LOCAL model. Moreover, the communication of a node essentially consists of sending its list to the neighbors. This is obtained as part of a framework that also contains Linial’s color reduction (with an alternative proof) as a special case. Our result also leads to a defective list coloring algorithm. As a corollary, we improve the state-of-the-art truly local $$({\text {deg}}+1)$$ ( deg + 1 ) -list coloring algorithm from Barenboim et al. (PODC, pp 437–446, 2018) by slightly reducing the runtime to $$O(\sqrt{\varDelta \log \varDelta })+\log ^* n$$ O ( Δ log Δ ) + log ∗ n and significantly reducing the message size (from $$\varDelta ^{O(\log ^* \varDelta )}$$ Δ O ( log ∗ Δ ) to roughly $$\varDelta $$ Δ ). Our techniques are inspired by the local conflict coloring framework of Fraigniaud et al. (in: FOCS, pp 625–634, 2016).

In this work, we initiate the study of fault tolerant Max Cut, where given an edge-weighted undirected graph $G=(V,E)$, the goal is to find a cut $S\subseteq V$ that maximizes the total weight of edges that cross $S$ even after an adversary removes $k$ vertices from $G$. We consider two types of adversaries: an adaptive adversary that sees the outcome of the random coin tosses used by the algorithm, and an oblivious adversary that does not. For any constant number of failures $k$ we present an approximation of $(0.878-ε)$ against an adaptive adversary and of $α_{GW}\approx 0.8786$ against an oblivious adversary (here $α_{GW}$ is the approximation achieved by the random hyperplane algorithm of [Goemans-Williamson J. ACM `95]). Additionally, we present a hardness of approximation of $α_{GW}$ against both types of adversaries, rendering our results (virtually) tight. The non-linear nature of the fault tolerant objective makes the design and analysis of algorithms harder when compared to the classic Max Cut. Hence, we employ approaches ranging from multi-objective optimization to LP duality and the ellipsoid algorithm to obtain our results.

Distributed vertex coloring is one of the classic problems and probably also the most widely studied problems in the area of distributed graph algorithms. We present a new randomized distributed vertex coloring algorithm for the standard CONGEST model, where the network is modeled as an n-node graph G, and where the nodes of G operate in synchronous communication rounds in which they can exchange O(logn)-bit messages over all the edges of G. For graphs with maximum degree Δ, we show that the (Δ+1)-list coloring problem (and therefore also the standard (Δ+1)-coloring problem) can be solved in O(log5logn) rounds. Previously such a result was only known for the significantly more powerful LOCAL model, where in each round, neighboring nodes can exchange messages of arbitrary size. The best previous (Δ+1)-coloring algorithm in the CONGEST model had a running time of O(logΔ + log6logn) rounds. As a function of n alone, the best previous algorithm therefore had a round complexity of O(logn), which is a bound that can also be achieved by a na'ive folklore algorithm. For large maximum degree Δ, our algorithm hence is an exponential improvement over the previous state of the art.

Abstract Jordan's classic theorem states that the center of every tree (the set of minimum eccentricity vertices) forms a complete subgraph. This property, which we refer to as the “Jordan property,” has been established for various definitions of eccentricity, the most popular being the maximum and average distances of a vertex to the others. In this note, we consider unimodal eccentricity functions, such that in every tree, the eccentricity strictly increases along every center‐to‐leaf path (whose second vertex is not in the center). Unimodal eccentricity implies the Jordan property. We prove that every function of distances with appropriate convexity and monotonicity is a unimodal eccentricity function. This covers many functions of distances that have been known to satisfy the Jordan property, and many others for which the Jordan property was not known prior to this work. Most of our results hold for trees with arbitrary positive weights on edges.

An overarching issue in resource management of wireless networks is assessing their capacity: How much communication can be achieved in a network, utilizing all the tools available: power control, scheduling, routing, channel assignment, and rate adjustment? We propose the first framework for approximation algorithms in the physical model of wireless interference that addresses these questions in full in interference-limited networks. The approximations obtained are at most doubly logarithmic in the link length and rate diversity. Where previous bounds are known, this gives an exponential improvement or better. The key insight is the discovery that a properly chosen power assignment infers a form of locality, or tolerance to the interference of both shorter and longer communication links. This allows us to simplify the complex interference relationship of the physical model into a new form of conflict graphs, at a small cost. We also show that the approximation obtained is provably the best possible for any conflict graph formulation.

We develop randomized distributed algorithms for many of the most fundamental communication problems in wireless networks under the Signal to Interference and Noise Ratio (SINR) model of communication, including (multi-message) broadcast, local broadcast, coloring, Maximal Independent Set, and aggregation. The complexity of our algorithms is optimal up to polylogarithmic preprocessing time. It shows—contrary to expectation—that the plain vanilla SINR model is just as powerful and fast (modulo the preprocessing) as various extensions studied, including power control, carrier sense, collision detection, free acknowledgements, and geolocation knowledge. Central to these results is an efficient construction of a constant-density backbone structure over the network, which is of independent interest. This is achieved using an indirect sensing technique, where message non-reception is used to deduce information about relative node-distances.

Linial's famous color reduction algorithm reduces a given $m$-coloring of a graph with maximum degree $Δ$ to a $O(Δ^2\log m)$-coloring, in a single round in the LOCAL model. We show a similar result when nodes are restricted to choose their color from a list of allowed colors: given an $m$-coloring in a directed graph of maximum outdegree $β$, if every node has a list of size $Ω(β^2 (\log β+\log\log m + \log \log |\mathcal{C}|))$ from a color space $\mathcal{C}$ then they can select a color in two rounds in the LOCAL model. Moreover, the communication of a node essentially consists of sending its list to the neighbors. This is obtained as part of a framework that also contains Linial's color reduction (with an alternative proof) as a special case. Our result also leads to a defective list coloring algorithm. As a corollary, we improve the state-of-the-art truly local $(deg+1)$-list coloring algorithm from Barenboim et al. [PODC'18] by slightly reducing the runtime to $O(\sqrt{Δ\logΔ})+\log^* n$ and significantly reducing the message size (from huge to roughly $Δ$). Our techniques are inspired by the local conflict coloring framework of Fraigniaud et al. [FOCS'16].

We develop randomized distributed algorithms for many of the most fundamental communication problems in the wireless SINR model, including (multi-message) broadcast, local broadcast, coloring, MIS, and aggregation. The complexity of the algorithms is optimal up to polylogarithmic preprocessing time. It shows -- contrary to expectation -- that the plain vanilla SINR model is just as powerful and fast (modulo the preprocessing) as various extensions studied, including power control, carrier sense, collision detection, free acknowledgements, and GPS location. A key component of the algorithms is an efficient simulation of CONGEST algorithms on a constant-density SINR backbone.

We study the effects of stochastic shadowing on scheduling in wireless networks. Previous work has generally assumed that shadowing affects different signals independently. Concentrating on “compact” networks, where very little or no spatial reuse is possible, such as in indoor environments, we form a model of correlation between the shadowing components for different signals. We analyze two fundamental measures: the maximum number of simultaneous transmitting links, and the fewest time/frequency slots or channels needed to schedule all the links. Based on the correlation model, we characterize (up to constant factors) how these measures scale with correlation strength and the number of links. We also give nearly optimal algorithms to compute such schedules, as well as to optimize the maximum weighted sum of simultaneously transmitting links. The latter can as well be extended to arbitrary sets of similar length links, under a suitable model of correlations, by partitioning them into compact subsets.

We introduce the problem of finding a spanning tree along with a partition of the tree edges into fewest number of feasible sets, where constraints on the edges define feasibility. The motivation comes from wireless networking, where we seek to model the irregularities seen in actual wireless environments. Not all node pairs may be able to communicate, even if geographically close --- thus, the available pairs are modeled with a link graph $\mathcal{L}=(V,E)$. Also, signal attenuation need not follow a nice geometric formulas --- hence, interference is modeled by a conflict (hyper)graph $\mathcal{C}=(E,F)$ on the links. The objective is to maximize the efficiency of the communication, or equivalently minimizing the length of a schedule of the tree edges in the form of a coloring. We find that in spite of all this generality, the problem can be approximated linearly in terms of a versatile parameter, the inductive independence of the interference graph. Specifically, we give a simple algorithm that attains a $O(ρ\log n)$-approximation, where $n$ is the number of nodes and $ρ$ is the inductive independence, and show that near-linear dependence on $ρ$ is also necessary. We also treat an extension to Steiner trees, modeling multicasting, and obtain a comparable result. Our results suggest that several canonical assumptions of geometry, regularity and "niceness" in wireless settings can sometimes be relaxed without a significant hit in algorithm performance.

One of the most fundamental tasks in sensor networks is the computation of a (compressible) aggregation function of the input measurements. What rate of computation can be maintained, by properly choosing the aggregation tree, the TDMA schedule of the tree edges, and the transmission powers? This can be viewed as the convergecast capacity of a wireless network. We show here that the optimal rate is effectively a constant. This holds even in arbitrary networks, under the physical model of interference. This compares with previous bounds that are logarithmic (e.g., Ω(1/log n)). Namely, we show that a rate of Ω(1/log* Δ) is possible, where Δ is the length diversity (ratio between the furthest to the shortest distance between nodes). It also implies that the scheduling complexity of wireless connectivity is O(log* Δ). This is achieved using the natural minimum spanning tree (MST). Our method crucially depends on choosing the appropriate power assignment for the instance at hand, since without power control, only a trivial O(1/n) rate can be guaranteed. We also show that there is a fixed power assignment that allows for a rate of Δ(1/log log Δ). Surprisingly, these bounds are essentially best possible. No aggregation network can guarantee a rate better than O(1/log log Δ) using fixed power assignment. Also, when using arbitrary power control, there are instances whose MSTs cannot be scheduled in fewer than Ω(1/log* Δ) slots.

The physical (or SINR) model of wireless communication is more intricate than radio networks and still not well understood. If two neighbors of a node are transmitting, the node may be able to decode one of the transmissions, depending on the relative nearness of the transmitters. Thus, even the lack of proper reception carries indirect information. We explore here the power of such indirect signaling to infer the approximate topology of the network. In particular, we obtain a polylogarithmic time algorithm to compute a backbone: a set of nodes of constant density that dominates every ε-neighborhood. A backbone has wide utility for information dissemination, functioning as a sparse spanner. It also leads to fast broadcast, running in O(Diameter) time after a polylogarithmic precomputation, which previously was only known when additional features such as carrier sense, collision detection, geometric coordinates, or power control were available.

Dynamic behavior is an essential part of wireless networking, due mobility, environmental changes or failures. We analyze a natural exponential backoff procedure to manage contention in a fading channel, in the presence of both node churn and link changes. We show that it attains a fast convergence, stabilizing contention from any state in logarithmic time. We use it to obtain optimal algorithm for Local Broadcast that even improves known results for the static case. The results illustrate the utility of carrier sensing, a stock feature of wireless nodes.

We consider the following basic link capacity (a.k.a., one-shot scheduling) problem in wireless networks: Given a set of communication links, find a maximum subset of links that can successfully transmit simultaneously. Good performance guarantees are known only for deterministic models, such as the physical model with geometric (log-distance) pathloss. We treat this problem under stochastic shadowing under general distributions, bound the effects of shadowing on optimal capacity, and derive constant approximation algorithms. We also consider temporal fading under Rayleigh distribution, and show that it affects non-fading solutions only by a constant-factor. These can be combined into a constant approximation link capacity algorithm under both time-invariant shadowing and temporal fading.

One of the most fundamental tasks in sensor networks is the computation of a (compressible) aggregation function of the input measurements. What rate of computation can be maintained, by properly choosing the aggregation tree, the TDMA schedule of the tree edges, and the transmission powers? We show here that the optimal rate is effectively a constant. This holds even in arbitrary networks, under the physical model of interference. Namely, we show that a rate of Ω(1/log* Δ) and Ω(1/log log Δ) is possible in the global power control and "oblivious" power control modes, respectively, where Δ is the length diversity (ratio between the furthest to the shortest distance between nodes), while without power control, only a trivial linear rate can be guaranteed.. We further show that these (worst-case) bounds are best possible.

announcement Share on Brief Announcement: Data Dissemination in Unified Dynamic Wireless Networks Authors: Magnus M. Halldórsson Reykjavik University, Reykjavik, Iceland Reykjavik University, Reykjavik, IcelandView Profile , Tigran Tonoyan Reykjavik University, Reykjavik, Iceland Reykjavik University, Reykjavik, IcelandView Profile , Yuexuan Wang Zhejiang University, Hangzhou, China Zhejiang University, Hangzhou, ChinaView Profile , Dongxiao Yu Huazhong University of Science and Technology, Wuhan, China Huazhong University of Science and Technology, Wuhan, ChinaView Profile Authors Info & Claims PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed ComputingJuly 2016 Pages 199–201https://doi.org/10.1145/2933057.2933065Published:25 July 2016Publication History 1citation132DownloadsMetricsTotal Citations1Total Downloads132Last 12 Months6Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We consider the problem of scheduling wireless links in the physical model, where we seek an assignment of power levels and a partition of the given set of links into the minimum number of subsets satisfying the signal-to-interference-and-noise-ratio (SINR) constraints. Specifically, we are interested in the efficiency of local power assignment schemes, or oblivious power schemes, in approximating wireless scheduling. Oblivious power schemes are motivated by networking scenarios when power levels must be decided in advance, and not as part of the scheduling computation. We present the first O(log log Delta)-approximation algorithm, which is known to be best possible (in terms of Delta) for oblivious power schemes, where Delta is the longest to shortest link length ratio. We achieve this by representing interference by a conflict graph, which allows the application of graph-theoretic results for a variety of related problems, including the weighted capacity problem. We explore further the contours of approximability and find the choice of power assignment matters; that not all metric spaces are equal; and that the presence of weak links makes the problem harder. Combined, our results resolve the price of local power for wireless scheduling, or the value of allowing unfettered power control.

Efficient use of a wireless network requires that transmissions be grouped into feasible sets, where feasibility means that each transmission can be successfully decoded in spite of the interference caused by simultaneous transmissions. Feasibility is most closely modeled by a signal-to-interference-plus-noise (SINR) formula, which unfortunately is conceptually complicated, being an asymmetric, cumulative, many-to-one relationship. We re-examine how well graphs can capture wireless receptions as encoded in SINR relationships, placing them in a framework in order to understand the limits of such modelling. We seek for each wireless instance a pair of graphs that provide upper and lower bounds on the feasibility relation, while aiming to minimize the gap between the two graphs. The cost of a graph formulation is the worst gap over all instances, and the price of (graph) abstraction is the smallest cost of a graph formulation. We propose a family of conflict graphs that is parameterized by a non-decreasing sub-linear function, and show that with a judicious choice of functions, the graphs can capture feasibility with a cost of O(log* Δ), where Δ is the ratio between the longest and the shortest link length. This holds on the plane and more generally in doubling metrics. We use this to give greatly improved O(log* Δ)-approximation for fundamental link scheduling problems with arbitrary power control. We also explore the limits of graph representations and find that our upper bound is tight: the price of graph abstraction is Ω(log* Δ). In addition, we give strong impossibility results for general metrics, and for approximations in terms of the number of links.