Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDistributed Distance Approximation
181
0
0.0
(
0
)
Added by
Yuval Efron
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Diameter, radius and eccentricities are fundamental graph parameters, which are extensively studied in various computational settings. Typically, computing approximate answers can be much more efficient compared with computing exact solutions. In this paper, we give a near complete characterization of the trade-offs between approximation ratios and round complexity of distributed algorithms for approximating these parameters, with a focus on the weighted and directed variants. Furthermore, we study emph{bi-chromatic} variants of these parameters defined on a graph whose vertices are colored either red or blue, and one focuses only on distances for pairs of vertices that are colored differently. Motivated by applications in computational geometry, bi-chromatic diameter, radius and eccentricities have been recently studied in the sequential setting [Backurs et al. STOC18, Dalirrooyfard et al. ICALP19]. We provide the first distributed upper and lower bounds for such problems. Our technical contributions include introducing the notion of emph{approximate pseudo-center}, which extends the emph{pseudo-centers} of [Choudhary and Gold SODA20], and presenting an efficient distributed algorithm for computing approximate pseudo-centers. On the lower bound side, our constructions introduce the usage of new functions into the framework of reductions from 2-party communication complexity to distributed algorithms.
rate research
Read More
We give a new, simple distributed algorithm for graph colouring in paths and cycles. Our algorithm is fast and self-contained, it does not need any globally consistent orientation, and it reduces the number of colours from $10^{100}$ to $3$ in three iterations.
In this paper we study fractional coloring from the angle of distributed computing. Fractional coloring is the linear relaxation of the classical notion of coloring, and has many applications, in particular in scheduling. It was proved by Hasemann, Hirvonen, Rybicki and Suomela (2016) that for every real $alpha>1$ and integer $Delta$, a fractional coloring of total weight at most $alpha(Delta+1)$ can be obtained deterministically in a single round in graphs of maximum degree $Delta$, in the LOCAL model of computation. However, a major issue of this result is that the output of each vertex has unbounded size. Here we prove that even if we impose the more realistic assumption that the output of each vertex has constant size, we can find fractional colorings of total weight arbitrarily close to known tight bounds for the fractional chromatic number in several cases of interest. More precisely, we show that for any fixed $epsilon > 0$ and $Delta$, a fractional coloring of total weight at most $Delta+epsilon$ can be found in $O(log^*n)$ rounds in graphs of maximum degree $Delta$ with no $K_{Delta+1}$, while finding a fractional coloring of total weight at most $Delta$ in this case requires $Omega(log log n)$ rounds for randomized algorithms and $Omega( log n)$ rounds for deterministic algorithms. We also show how to obtain fractional colorings of total weight at most $2+epsilon$ in grids of any fixed dimension, for any $epsilon>0$, in $O(log^*n)$ rounds. Finally, we prove that in sparse graphs of large girth from any proper minor-closed family we can find a fractional coloring of total weight at most $2+epsilon$, for any $epsilon>0$, in $O(log n)$ rounds.
This paper introduces a new resource allocation problem in distributed computing called distributed serving with mobile servers (DSMS). In DSMS, there are $k$ identical mobile servers residing at the processors of a network. At arbitrary points of time, any subset of processors can invoke one or more requests. To serve a request, one of the servers must move to the processor that invoked the request. Resource allocation is performed in a distributed manner since only the processor that invoked the request initially knows about it. All processors cooperate by passing messages to achieve correct resource allocation. They do this with the goal to minimize the communication cost. Routing servers in large-scale distributed systems requires a scalable location service. We introduce the distributed protocol GNN that solves the DSMS problem on overlay trees. We prove that GNN is starvation-free and correctly integrates locating the servers and synchronizing the concurrent access to servers despite asynchrony, even when the requests are invoked over time. Further, we analyze GNN for one-shot executions, i.e., all requests are invoked simultaneously. We prove that when running GNN on top of a special family of tree topologies---known as hierarchically well-separated trees (HSTs)---we obtain a randomized distributed protocol with an expected competitive ratio of $O(log n)$ on general network topologies with $n$ processors. From a technical point of view, our main result is that GNN optimally solves the DSMS problem on HSTs for one-shot executions, even if communication is asynchronous. Further, we present a lower bound of $Omega(max{k, log n/loglog n})$ on the competitive ratio for DSMS. The lower bound even holds when communication is synchronous and requests are invoked sequentially.
Naor, Parter, and Yogev (SODA 2020) have recently demonstrated the existence of a emph{distributed interactive proof} for planarity (i.e., for certifying that a network is planar), using a sophisticated generic technique for constructing distributed IP protocols based on sequential IP protocols. The interactive proof for planarity is based on a distributed certification of the correct execution of any given sequential linear-time algorithm for planarity testing. It involves three interactions between the prover and the randomized distributed verifier (i.e., it is a dMAM/ protocol), and uses small certificates, on $O(log n)$ bits in $n$-node networks. We show that a single interaction from the prover suffices, and randomization is unecessary, by providing an explicit description of a emph{proof-labeling scheme} for planarity, still using certificates on just $O(log n)$ bits. We also show that there are no proof-labeling schemes -- in fact, even no emph{locally checkable proofs} -- for planarity using certificates on $o(log n)$ bits.
We study the maximum cardinality matching problem in a standard distributed setting, where the nodes $V$ of a given $n$-node network graph $G=(V,E)$ communicate over the edges $E$ in synchronous rounds. More specifically, we consider the distributed CONGEST model, where in each round, each node of $G$ can send an $O(log n)$-bit message to each of its neighbors. We show that for every graph $G$ and a matching $M$ of $G$, there is a randomized CONGEST algorithm to verify $M$ being a maximum matching of $G$ in time $O(|M|)$ and disprove it in time $O(D + ell)$, where $D$ is the diameter of $G$ and $ell$ is the length of a shortest augmenting path. We hope that our algorithm constitutes a significant step towards developing a CONGEST algorithm to compute a maximum matching in time $tilde{O}(s^*)$, where $s^*$ is the size of a maximum matching.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
