Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRadio Network Lower Bounds Made Easy
133
0
0.0
(
0
)
Added by
Calvin Newport
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Authors
Calvin Newport
Ask ChatGPT about the research
No Arabic abstract
Theoreticians have studied distributed algorithms in the radio network model for close to three decades. A significant fraction of this work focuses on lower bounds for basic communication problems such as wake-up (symmetry breaking among an unknown set of nodes) and broadcast (message dissemination through an unknown network topology). In this paper, we introduce a new technique for proving this type of bound, based on reduction from a probabilistic hitting game, that simplifies and strengthens much of this existing work. In more detail, in this single paper we prove new expected time and high probability lower bounds for wake-up and global broadcast in single and multichann
rate research
Read More
Linials seminal result shows that any deterministic distributed algorithm that finds a $3$-colouring of an $n$-cycle requires at least $log^*(n)/2 - 1$ communication rounds. We give a new simpler proof of this theorem.
One of the first and easy to use techniques for proving run time bounds for evolutionary algorithms is the so-called method of fitness levels by Wegener. It uses a partition of the search space into a sequence of levels which are traversed by the algorithm in increasing order, possibly skipping levels. An easy, but often strong upper bound for the run time can then be derived by adding the reciprocals of the probabilities to leave the levels (or upper bounds for these). Unfortunately, a similarly effective method for proving lower bounds has not yet been established. The strongest such method, proposed by Sudholt (2013), requires a careful choice of the viscosity parameters $gamma_{i,j}$, $0 le i < j le n$. In this paper we present two new variants of the method, one for upper and one for lower bounds. Besides the level leaving probabilities, they only rely on the probabilities that levels are visited at all. We show that these can be computed or estimated without greater difficulties and apply our method to reprove the following known results in an easy and natural way. (i) The precise run time of the (1+1) EA on textsc{LeadingOnes}. (ii) A lower bound for the run time of the (1+1) EA on textsc{OneMax}, tight apart from an $O(n)$ term. (iii) A lower bound for the run time of the (1+1) EA on long $k$-paths. We also prove a tighter lower bound for the run time of the (1+1) EA on jump functions by showing that, regardless of the jump size, only with probability $O(2^{-n})$ the algorithm can avoid to jump over the valley of low fitness.
This paper proves strong lower bounds for distributed computing in the CONGEST model, by presenting the bit-gadget: a new technique for constructing graphs with small cuts. The contribution of bit-gadgets is twofold. First, developing careful sparse graph constructions with small cuts extends known techniques to show a near-linear lower bound for computing the diameter, a result previously known only for dense graphs. Moreover, the sparseness of the construction plays a crucial role in applying it to approximations of various distance computation problems, drastically improving over what can be obtained when using dense graphs. Second, small cuts are essential for proving super-linear lower bounds, none of which were known prior to this work. In fact, they allow us to show near-quadratic lower bounds for several problems, such as exact minimum vertex cover or maximum independent set, as well as for coloring a graph with its chromatic number. Such strong lower bounds are not limited to NP-hard problems, as given by two simple graph problems in P which are shown to require a quadratic and near-quadratic number of rounds. All of the above are optimal up to logarithmic factors. In addition, in this context, the complexity of the all-pairs-shortest-paths problem is discussed. Finally, it is shown that graph constructions for CONGEST lower bounds translate to lower bounds for the semi-streaming model, despite being very different in its nature.
In this paper, we study lower bounds for randomized solutions to the maximal independent set (MIS) and connected dominating set (CDS) problems in the dual graph model of radio networks---a generalization of the standard graph-based model that now includes unreliable links controlled by an adversary. We begin by proving that a natural geographic constraint on the network topology is required to solve these problems efficiently (i.e., in time polylogarthmic in the network size). We then prove the importance of the assumption that nodes are provided advance knowledge of their reliable neighbors (i.e, neighbors connected by reliable links). Combined, these results answer an open question by proving that the efficient MIS and CDS algorithms from [Censor-Hillel, PODC 2011] are optimal with respect to their dual graph model assumptions. They also provide insight into what properties of an unreliable network enable efficient local computation.
Given a graph $G = (V,E)$, an $(alpha, beta)$-ruling set is a subset $S subseteq V$ such that the distance between any two vertices in $S$ is at least $alpha$, and the distance between any vertex in $V$ and the closest vertex in $S$ is at most $beta$. We present lower bounds for distributedly computing ruling sets. More precisely, for the problem of computing a $(2, beta)$-ruling set in the LOCAL model, we show the following, where $n$ denotes the number of vertices, $Delta$ the maximum degree, and $c$ is some universal constant independent of $n$ and $Delta$. $bullet$ Any deterministic algorithm requires $Omegaleft(min left{ frac{log Delta}{beta log log Delta} , log_Delta n right} right)$ rounds, for all $beta le c cdot minleft{ sqrt{frac{log Delta}{log log Delta}} , log_Delta n right}$. By optimizing $Delta$, this implies a deterministic lower bound of $Omegaleft(sqrt{frac{log n}{beta log log n}}right)$ for all $beta le c sqrt[3]{frac{log n}{log log n}}$. $bullet$ Any randomized algorithm requires $Omegaleft(min left{ frac{log Delta}{beta log log Delta} , log_Delta log n right} right)$ rounds, for all $beta le c cdot minleft{ sqrt{frac{log Delta}{log log Delta}} , log_Delta log n right}$. By optimizing $Delta$, this implies a randomized lower bound of $Omegaleft(sqrt{frac{log log n}{beta log log log n}}right)$ for all $beta le c sqrt[3]{frac{log log n}{log log log n}}$. For $beta > 1$, this improves on the previously best lower bound of $Omega(log^* n)$ rounds that follows from the 30-year-old bounds of Linial [FOCS87] and Naor [J.Disc.Math.91]. For $beta = 1$, i.e., for the problem of computing a maximal independent set, our results improve on the previously best lower bound of $Omega(log^* n)$ on trees, as our bounds already hold on trees.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
