BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Fabian Kuhn

Fabian Kuhn appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Distributed, Parallel, and Cluster ComputingData Structures and AlgorithmsDiscrete Mathematicsmath.CO

Catalog footprint

What is connected

27works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

27 published item(s)

preprint2022arXiv

Distributed $Δ$-Coloring Plays Hide-and-Seek

We prove several new tight distributed lower bounds for classic symmetry breaking graph problems. As a basic tool, we first provide a new insightful proof that any deterministic distributed algorithm that computes a $Δ$-coloring on $Δ$-regular trees requires $Ω(\log_Δn)$ rounds and any randomized algorithm requires $Ω(\log_Δ\log n)$ rounds. We prove this result by showing that a natural relaxation of the $Δ$-coloring problem is a fixed point in the round elimination framework. As a first application, we show that our $Δ$-coloring lower bound proof directly extends to arbdefective colorings. We exactly characterize which variants of the arbdefective coloring problem are "easy", and which of them instead are "hard". As a second application, which we see as our main contribution, we use the structure of the fixed point as a building block to prove lower bounds as a function of $Δ$ for a large class of distributed symmetry breaking problems. For example, we obtain a tight lower bound for the fundamental problem of computing a $(2,β)$-ruling set. This is an exponential improvement over the best existing lower bound for the problem, which was proven in [FOCS '20]. Our lower bound even applies to a much more general family of problems that allows for almost arbitrary combinations of natural constraints from coloring problems, orientation problems, and independent set problems, and provides a single unified proof for known and new lower bound results for these types of problems. Our lower bounds as a function of $Δ$ also imply lower bounds as a function of $n$. We obtain, for example, that maximal independent set, on trees, requires $Ω(\log n / \log \log n)$ rounds for deterministic algorithms, which is tight.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Distributed Edge Coloring in Time Polylogarithmic in $Δ$

We provide new deterministic algorithms for the edge coloring problem, which is one of the classic and highly studied distributed local symmetry breaking problems. As our main result, we show that a $(2Δ-1)$-edge coloring can be computed in time $\mathrm{poly}\logΔ+ O(\log^* n)$ in the LOCAL model. This improves a result of Balliu, Kuhn, and Olivetti [PODC '20], who gave an algorithm with a quasi-polylogarithmic dependency on $Δ$. We further show that in the CONGEST model, an $(8+\varepsilon)Δ$-edge coloring can be computed in $\mathrm{poly}\logΔ+ O(\log^* n)$ rounds. The best previous $O(Δ)$-edge coloring algorithm that can be implemented in the CONGEST model is by Barenboim and Elkin [PODC '11] and it computes a $2^{O(1/\varepsilon)}Δ$-edge coloring in time $O(Δ^\varepsilon + \log^* n)$ for any $\varepsilon\in(0,1]$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Near-Shortest Path Routing in Hybrid Communication Networks

Hybrid networks, i.e., networks that leverage different means of communication, become ever more widespread. To allow theoretical study of such networks, [Augustine et al., SODA'20] introduced the $\mathsf{HYBRID}$ model, which is based on the concept of synchronous message passing and uses two fundamentally different principles of communication: a local mode, which allows every node to exchange one message per round with each neighbor in a local communication graph; and a global mode where any pair of nodes can exchange messages, but only few such exchanges can take place per round. A sizable portion of the previous research for the $\mathsf{HYBRID}$ model revolves around basic communication primitives and computing distances or shortest paths in networks. In this paper, we extend this study to a related fundamental problem of computing compact routing schemes for near-shortest paths in the local communication graph. We demonstrate that, for the case where the local communication graph is a unit-disc graph with $n$ nodes that is realized in the plane and has no radio holes, we can deterministically compute a routing scheme that has constant stretch and uses labels and local routing tables of size $O(\log n)$ bits in only $O(\log n)$ rounds.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Node and Edge Averaged Complexities of Local Graph Problems

The node-averaged complexity of a distributed algorithm running on a graph $G=(V,E)$ is the average over the times at which the nodes $V$ of $G$ finish their computation and commit to their outputs. We study the node-averaged complexity for some distributed symmetry breaking problems and provide the following results (among others): - The randomized node-averaged complexity of computing a maximal independent set (MIS) in $n$-node graphs of maximum degree $Δ$ is at least $Ω\big(\min\big\{\frac{\logΔ}{\log\logΔ},\sqrt{\frac{\log n}{\log\log n}}\big\}\big)$. This bound is obtained by a novel adaptation of the well-known KMW lower bound [JACM'16]. As a side result, we obtain the same lower bound for the worst-case randomized round complexity for computing an MIS in trees -- this essentially answers open problem 11.15 in the book of Barenboim and Elkin and resolves the complexity of MIS on trees up to an $O(\sqrt{\log\log n})$ factor. We also show that, $(2,2)$-ruling sets, which are a minimal relaxation of MIS, have $O(1)$ randomized node-averaged complexity. - For maximal matching, we show that while the randomized node-averaged complexity is $Ω\big(\min\big\{\frac{\logΔ}{\log\logΔ},\sqrt{\frac{\log n}{\log\log n}}\big\}\big)$, the randomized edge-averaged complexity is $O(1)$. Further, we show that the deterministic edge-averaged complexity of maximal matching is $O(\log^2Δ+ \log^* n)$ and the deterministic node-averaged complexity of maximal matching is $O(\log^3Δ+ \log^* n)$. - Finally, we consider the problem of computing a sinkless orientation of a graph. The deterministic worst-case complexity of the problem is known to be $Θ(\log n)$, even on bounded-degree graphs. We show that the problem can be solved deterministically with node-averaged complexity $O(\log^* n)$, while keeping the worst-case complexity in $O(\log n)$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Routing Schemes and Distance Oracles in the Hybrid Model

The $\mathsf{HYBRID}$ model was introduced as a means for theoretical study of distributed networks that use various communication modes. Conceptually, it is a synchronous message passing model with a local communication mode, where in each round each node can send large messages to all its neighbors in a local network (a graph), and a global communication mode, where each node is allotted limited (polylogarithmic) bandwidth per round which it can use to communicate with any node in the network. Prior work has often focused on shortest paths problems in the local network, as their global nature makes these an interesting case study how combining communication modes in the $\mathsf{HYBRID}$ model can overcome the individual lower bounds of either mode. In this work we consider a similar problem, namely computation of distance oracles and routing schemes. In the former, all nodes have to compute local tables, which allows them to look up the distance (estimates) to any target node in the local network when provided with the label of the target. In the latter, it suffices that nodes give the next node on an (approximately) shortest path to the target. Our goal is to compute these local tables as fast as possible with labels as small as possible. We show that this can be done exactly in $\widetilde O(n^{1/3})$ communication rounds and labels of size $Θ(n^{2/3})$ bits. For constant stretch approximations we achieve labels of size $O(\log n)$ in the same time. Further, as our main technical contribution, we provide computational lower bounds for a variety of problem parameters. For instance, we show that computing solutions with stretch below a certain constant takes $\widetilde Ω(n^{1/3})$ rounds even for labels of size $O(n^{2/3})$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Sinkless Orientation Made Simple

The sinkless orientation problem plays a key role in understanding the foundations of distributed computing. The problem can be used to separate two fundamental models of distributed graph algorithms, LOCAL and SLOCAL: the locality of sinkless orientation is $Ω(\log n)$ in the deterministic LOCAL model and $O(\log \log n)$ in the deterministic SLOCAL model. Both of these results are known by prior work, but here we give new simple, self-contained proofs for them.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Distance-2 Coloring in the CONGEST Model

We give efficient randomized and deterministic distributed algorithms for computing a distance-$2$ vertex coloring of a graph $G$ in the CONGEST model. In particular, if $Δ$ is the maximum degree of $G$, we show that there is a randomized CONGEST model algorithm to compute a distance-$2$ coloring of $G$ with $Δ^2+1$ colors in $O(\logΔ\cdot\log n)$ rounds. Further if the number of colors is slightly increased to $(1+ε)Δ^2$ for some $ε>1/{\rm polylog}(n)$, we show that it is even possible to compute a distance-$2$ coloring deterministically in polylog$(n)$ time in the CONGEST model. Finally, we give a $O(Δ^2 + \log^* n)$-round deterministic CONGEST algorithm to compute distance-$2$ coloring with $Δ^2+1$ colors.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta

The problem of coloring the edges of an $n$-node graph of maximum degree $Δ$ with $2Δ- 1$ colors is one of the key symmetry breaking problems in the area of distributed graph algorithms. While there has been a lot of progress towards the understanding of this problem, the dependency of the running time on $Δ$ has been a long-standing open question. Very recently, Kuhn [SODA '20] showed that the problem can be solved in time $2^{O(\sqrt{\logΔ})}+O(\log^* n)$. In this paper, we study the edge coloring problem in the distributed LOCAL model. We show that the $(\mathit{degree}+1)$-list edge coloring problem, and thus also the $(2Δ-1)$-edge coloring problem, can be solved deterministically in time $\log^{O(\log\logΔ)}Δ+ O(\log^* n)$. This is a significant improvement over the result of Kuhn [SODA '20].

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Distributed Maximum Matching Verification in CONGEST

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Efficient Deterministic Distributed Coloring with Small Bandwidth

We show that the $(degree+1)$-list coloring problem can be solved deterministically in $O(D \cdot \log n \cdot\log^2Δ)$ rounds in the \CONGEST model, where $D$ is the diameter of the graph, $n$ the number of nodes, and $Δ$ the maximum degree. Using the recent polylogarithmic-time deterministic network decomposition algorithm by Rozhoň and Ghaffari [STOC 2020], this implies the first efficient (i.e., $\poly\log n$-time) deterministic \CONGEST algorithm for the $(Δ+1)$-coloring and the $(\mathit{degree}+1)$-list coloring problem. Previously the best known algorithm required $2^{O(\sqrt{\log n})}$ rounds and was not based on network decompositions. Our techniques also lead to deterministic $(\mathit{degree}+1)$-list coloring algorithms for the congested clique and the massively parallel computation (MPC) model. For the congested clique, we obtain an algorithm with time complexity $O(\logΔ\cdot\log\logΔ)$, for the MPC model, we obtain algorithms with round complexity $O(\log^2Δ)$ for the linear-memory regime and $O(\log^2Δ+ \log n)$ for the sublinear memory regime.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Improved Distributed $Δ$-Coloring

We present a randomized distributed algorithm that computes a $Δ$-coloring in any non-complete graph with maximum degree $Δ\geq 4$ in $O(\log Δ) + 2^{O(\sqrt{\log\log n})}$ rounds, as well as a randomized algorithm that computes a $Δ$-coloring in $O((\log \log n)^2)$ rounds when $Δ\in [3, O(1)]$. Both these algorithms improve on an $O(\log^3 n/\log Δ)$-round algorithm of Panconesi and Srinivasan~[STOC'1993], which has remained the state of the art for the past 25 years. Moreover, the latter algorithm gets (exponentially) closer to an $Ω(\log\log n)$ round lower bound of Brandt et al.~[STOC'16].

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Latency, Capacity, and Distributed MST

We study the cost of distributed MST construction in the setting where each edge has a latency and a capacity, along with the weight. Edge latencies capture the delay on the links of the communication network, while capacity captures their throughput (in this case, the rate at which messages can be sent). Depending on how the edge latencies relate to the edge weights, we provide several tight bounds on the time and messages required to construct an MST. When edge weights exactly correspond with the latencies, we show that, perhaps interestingly, the bottleneck parameter in determining the running time of an algorithm is the total weight $W$ of the MST (rather than the total number of nodes $n$, as in the standard CONGEST model). That is, we show a tight bound of $\tildeΘ(D + \sqrt{W/c})$ rounds, where $D$ refers to the latency diameter of the graph, $W$ refers to the total weight of the constructed MST and edges have capacity $c$. The proposed algorithm sends $\tilde{O}(m+W)$ messages, where $m$, the total number of edges in the network graph under consideration, is a known lower bound on message complexity for MST construction. We also show that $Ω(W)$ is a lower bound for fast MST constructions. When the edge latencies and the corresponding edge weights are unrelated, and either can take arbitrary values, we show that (unlike the sub-linear time algorithms in the standard CONGEST model, on small diameter graphs), the best time complexity that can be achieved is $\tildeΘ(D+n/c)$. However, if we restrict all edges to have equal latency $\ell$ and capacity $c$ while having possibly different weights (weights could deviate arbitrarily from $\ell$), we give an algorithm that constructs an MST in $\tilde{O}(D + \sqrt{n\ell/c})$ time. In each case, we provide nearly matching upper and lower bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Local Computation: Lower and Upper Bounds

The question of what can be computed, and how efficiently, are at the core of computer science. Not surprisingly, in distributed systems and networking research, an equally fundamental question is what can be computed in a \emph{distributed} fashion. More precisely, if nodes of a network must base their decision on information in their local neighborhood only, how well can they compute or approximate a global (optimization) problem? In this paper we give the first poly-logarithmic lower bound on such local computation for (optimization) problems including minimum vertex cover, minimum (connected) dominating set, maximum matching, maximal independent set, and maximal matching. In addition we present a new distributed algorithm for solving general covering and packing linear programs. For some problems this algorithm is tight with the lower bounds, for others it is a distributed approximation scheme. Together, our lower and upper bounds establish the local computability and approximability of a large class of problems, characterizing how much local information is required to solve these tasks.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Multi-Message Broadcast in Dynamic Radio Networks

We continue the recent line of research studying information dissemination problems in adversarial dynamic radio networks. We give two generic algorithms which allow to transform generalized version of single-message broadcast algorithms into multi-message broadcast algorithms. Based on these generic algorithms, we obtain multi-message broadcast algorithms for dynamic radio networks for a number of different dynamic network settings. For one of the modeling assumptions, our algorithms are complemented by a lower bound which shows that the upper bound is close to optimal.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Polynomial Lower Bound for Distributed Graph Coloring in a Weak LOCAL Model

We show an $Ω\big(Δ^{\frac{1}{3}-\fracη{3}}\big)$ lower bound on the runtime of any deterministic distributed $\mathcal{O}\big(Δ^{1+η}\big)$-graph coloring algorithm in a weak variant of the \LOCAL\ model. In particular, given a network graph \mbox{$G=(V,E)$}, in the weak \LOCAL\ model nodes communicate in synchronous rounds and they can use unbounded local computation. We assume that the nodes have no identifiers, but that instead, the computation starts with an initial valid vertex coloring. A node can \textbf{broadcast} a \textbf{single} message of \textbf{unbounded} size to its neighbors and receives the \textbf{set of messages} sent to it by its neighbors. That is, if two neighbors of a node $v\in V$ send the same message to $v$, $v$ will receive this message only a single time; without any further knowledge, $v$ cannot know whether a received message was sent by only one or more than one neighbor. Neighborhood graphs have been essential in the proof of lower bounds for distributed coloring algorithms, e.g., \cite{linial92,Kuhn2006On}. Our proof analyzes the recursive structure of the neighborhood graph of the respective model to devise an $Ω\big(Δ^{\frac{1}{3}-\fracη{3}}\big)$ lower bound on the runtime for any deterministic distributed $\mathcal{O}\big(Δ^{1+η}\big)$-graph coloring algorithm. Furthermore, we hope that the proof technique improves the understanding of neighborhood graphs in general and that it will help towards finding a lower (runtime) bound for distributed graph coloring in the standard \LOCAL\ model. Our proof technique works for one-round algorithms in the standard \LOCAL\ model and provides a simpler and more intuitive proof for an existing $Ω(Δ^2)$ lower bound.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Cost of Global Broadcast in Dynamic Radio Networks

We study the single-message broadcast problem in dynamic radio networks. We show that the time complexity of the problem depends on the amount of stability and connectivity of the dynamic network topology and on the adaptiveness of the adversary providing the dynamic topology. More formally, we model communication using the standard graph-based radio network model. To model the dynamic network, we use a generalization of the synchronous dynamic graph model introduced in [Kuhn et al., STOC 2010]. For integer parameters $T\geq 1$ and $k\geq 1$, we call a dynamic graph $T$-interval $k$-connected if for every interval of $T$ consecutive rounds, there exists a $k$-vertex-connected stable subgraph. Further, for an integer parameter $τ\geq 0$, we say that the adversary providing the dynamic network is $τ$-oblivious if for constructing the graph of some round $t$, the adversary has access to all the randomness (and states) of the algorithm up to round $t-τ$. As our main result, we show that for any $T\geq 1$, any $k\geq 1$, and any $τ\geq 1$, for a $τ$-oblivious adversary, there is a distributed algorithm to broadcast a single message in time $O\big(\big(1+\frac{n}{k\cdot\min\left\{τ,T\right\}}\big)\cdot n\log^3 n\big)$. We further show that even for large interval $k$-connectivity, efficient broadcast is not possible for the usual adaptive adversaries. For a $1$-oblivious adversary, we show that even for any $T\leq (n/k)^{1-\varepsilon}$ (for any constant $\varepsilon>0$) and for any $k\geq 1$, global broadcast in $T$-interval $k$-connected networks requires at least $Ω(n^2/(k^2\log n))$ time. Further, for a $0$ oblivious adversary, broadcast cannot be solved in $T$-interval $k$-connected networks as long as $T<n-k$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Near-Optimal Distributed Maximum Flow

We present a near-optimal distributed algorithm for $(1+o(1))$-approximation of single-commodity maximum flow in undirected weighted networks that runs in $(D+ \sqrt{n})\cdot n^{o(1)}$ communication rounds in the \Congest model. Here, $n$ and $D$ denote the number of nodes and the network diameter, respectively. This is the first improvement over the trivial bound of $O(n^2)$, and it nearly matches the $\tildeΩ(D+ \sqrt{n})$ round complexity lower bound. The development of the algorithm contains two results of independent interest: (i) A $(D+\sqrt{n})\cdot n^{o(1)}$-round distributed construction of a spanning tree of average stretch $n^{o(1)}$. (ii) A $(D+\sqrt{n})\cdot n^{o(1)}$-round distributed construction of an $n^{o(1)}$-congestion approximator consisting of the cuts induced by $O(\log n)$ virtual trees. The distributed representation of the cut approximator allows for evaluation in $(D+\sqrt{n})\cdot n^{o(1)}$ rounds. All our algorithms make use of randomization and succeed with high probability.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Rumor Spreading with Bounded In-Degree

In the classic gossip-based model of communication for disseminating information in a network, in each time unit, every node $u$ is allowed to contact a single random neighbor $v$. If $u$ knows the data (rumor) to be disseminated, it disperses it to $v$ (known as PUSH) and if it does not, it requests it from $v$ (known as PULL). While in the classic gossip model, each node is only allowed to contact a single neighbor in each time unit, each node can possibly be contacted by many neighboring nodes. In the present paper, we consider a restricted model where at each node only one incoming request can be served. As long as only a single piece of information needs to be disseminated, this does not make a difference for push requests. It however has a significant effect on pull requests. In the paper, we therefore concentrate on this weaker pull version, which we call 'restricted pull'. We distinguish two versions of the restricted pull protocol depending on whether the request to be served among a set of pull requests at a given node is chosen adversarially or uniformly at random. As a first result, we prove an exponential separation between the two variants. We show that there are instances where if an adversary picks the request to be served, the restricted pull protocol requires a polynomial number of rounds whereas if the winning request is chosen uniformly at random, the restricted pull protocol only requires a polylogarithmic number of rounds to inform the whole network. Further, as the main technical contribution, we show that if the request to be served is chosen randomly, the slowdown of using restricted pull versus using the classic pull protocol can w.h.p. be upper bounded by $O(Δ/ δ\log n)$, where $Δ$ and $δ$ are the largest and smallest degree of the network.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Tight Bounds for MIS in Multichannel Radio Networks

Daum et al. [PODC'13] presented an algorithm that computes a maximal independent set (MIS) within $O(\log^2 n/F+\log n \mathrm{polyloglog} n)$ rounds in an $n$-node multichannel radio network with $F$ communication channels. The paper uses a multichannel variant of the standard graph-based radio network model without collision detection and it assumes that the network graph is a polynomially bounded independence graph (BIG), a natural combinatorial generalization of well-known geographic families. The upper bound of that paper is known to be optimal up to a polyloglog factor. In this paper, we adapt algorithm and analysis to improve the result in two ways. Mainly, we get rid of the polyloglog factor in the runtime and we thus obtain an asymptotically optimal multichannel radio network MIS algorithm. In addition, our new analysis allows to generalize the class of graphs from those with polynomially bounded local independence to graphs where the local independence is bounded by an arbitrary function of the neighborhood radius.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A New Perspective on Vertex Connectivity

Edge connectivity and vertex connectivity are two fundamental concepts in graph theory. Although by now there is a good understanding of the structure of graphs based on their edge connectivity, our knowledge in the case of vertex connectivity is much more limited. An essential tool in capturing edge connectivity are edge-disjoint spanning trees. The famous results of Tutte and Nash-Williams show that a graph with edge connectivity $λ$ contains $\floor{λ/2}$ edge-disjoint spanning trees. We present connected dominating set (CDS) partition and packing as tools that are analogous to edge-disjoint spanning trees and that help us to better grasp the structure of graphs based on their vertex connectivity. The objective of the CDS partition problem is to partition the nodes of a graph into as many connected dominating sets as possible. The CDS packing problem is the corresponding fractional relaxation, where CDSs are allowed to overlap as long as this is compensated by assigning appropriate weights. CDS partition and CDS packing can be viewed as the counterparts of the well-studied edge-disjoint spanning trees, focusing on vertex disjointedness rather than edge disjointness. We constructively show that every $k$-vertex-connected graph with $n$ nodes has a CDS packing of size $Ω(k/\log n)$ and a CDS partition of size $Ω(k/\log^5 n)$. We prove that the $Ω(k/\log n)$ CDS packing bound is existentially optimal. Using CDS packing, we show that if vertices of a $k$-vertex-connected graph are independently sampled with probability $p$, then the graph induced by the sampled vertices has vertex connectivity $\tildeΩ(kp^2)$. Moreover, using our $Ω(k/\log n)$ CDS packing, we get a store-and-forward broadcast algorithm with optimal throughput in the networking model where in each round, each node can send one bounded-size message to all its neighbors.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Distributed Connectivity Decomposition

We present time-efficient distributed algorithms for decomposing graphs with large edge or vertex connectivity into multiple spanning or dominating trees, respectively. As their primary applications, these decompositions allow us to achieve information flow with size close to the connectivity by parallelizing it along the trees. More specifically, our distributed decomposition algorithms are as follows: (I) A decomposition of each undirected graph with vertex-connectivity $k$ into (fractionally) vertex-disjoint weighted dominating trees with total weight $Ω(\frac{k}{\log n})$, in $\widetilde{O}(D+\sqrt{n})$ rounds. (II) A decomposition of each undirected graph with edge-connectivity $λ$ into (fractionally) edge-disjoint weighted spanning trees with total weight $\lceil\frac{λ-1}{2}\rceil(1-\varepsilon)$, in $\widetilde{O}(D+\sqrt{nλ})$ rounds. We also show round complexity lower bounds of $\tildeΩ(D+\sqrt{\frac{n}{k}})$ and $\tildeΩ(D+\sqrt{\frac{n}λ})$ for the above two decompositions, using techniques of [Das Sarma et al., STOC'11]. Moreover, our vertex-connectivity decomposition extends to centralized algorithms and improves the time complexity of [Censor-Hillel et al., SODA'14] from $O(n^3)$ to near-optimal $\tilde{O}(m)$. As corollaries, we also get distributed oblivious routing broadcast with $O(1)$-competitive edge-congestion and $O(\log n)$-competitive vertex-congestion. Furthermore, the vertex connectivity decomposition leads to near-time-optimal $O(\log n)$-approximation of vertex connectivity: centralized $\widetilde{O}(m)$ and distributed $\tilde{O}(D+\sqrt{n})$. The former moves toward the 1974 conjecture of Aho, Hopcroft, and Ullman postulating an $O(m)$ centralized exact algorithm while the latter is the first distributed vertex connectivity approximation.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Distributed Minimum Cut Approximation

We study the problem of computing approximate minimum edge cuts by distributed algorithms. We use a standard synchronous message passing model where in each round, $O(\log n)$ bits can be transmitted over each edge (a.k.a. the CONGEST model). We present a distributed algorithm that, for any weighted graph and any $ε\in (0, 1)$, with high probability finds a cut of size at most $O(ε^{-1}λ)$ in $O(D) + \tilde{O}(n^{1/2 + ε})$ rounds, where $λ$ is the size of the minimum cut. This algorithm is based on a simple approach for analyzing random edge sampling, which we call the random layering technique. In addition, we also present another distributed algorithm, which is based on a centralized algorithm due to Matula [SODA '93], that with high probability computes a cut of size at most $(2+ε)λ$ in $\tilde{O}((D+\sqrt{n})/ε^5)$ rounds for any $ε>0$. The time complexities of both of these algorithms almost match the $\tildeΩ(D + \sqrt{n})$ lower bound of Das Sarma et al. [STOC '11], thus leading to an answer to an open question raised by Elkin [SIGACT-News '04] and Das Sarma et al. [STOC '11]. Furthermore, we also strengthen the lower bound of Das Sarma et al. by extending it to unweighted graphs. We show that the same lower bound also holds for unweighted multigraphs (or equivalently for weighted graphs in which $O(w\log n)$ bits can be transmitted in each round over an edge of weight $w$), even if the diameter is $D=O(\log n)$. For unweighted simple graphs, we show that even for networks of diameter $\tilde{O}(\frac{1}λ\cdot \sqrt{\frac{n}{αλ}})$, finding an $α$-approximate minimum cut in networks of edge connectivity $λ$ or computing an $α$-approximation of the edge connectivity requires $\tildeΩ(D + \sqrt{\frac{n}{αλ}})$ rounds.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Beeping a Maximal Independent Set

We consider the problem of computing a maximal independent set (MIS) in an extremely harsh broadcast model that relies only on carrier sensing. The model consists of an anonymous broadcast network in which nodes have no knowledge about the topology of the network or even an upper bound on its size. Furthermore, it is assumed that an adversary chooses at which time slot each node wakes up. At each time slot a node can either beep, that is, emit a signal, or be silent. At a particular time slot, beeping nodes receive no feedback, while silent nodes can only differentiate between none of its neighbors beeping, or at least one of its neighbors beeping. We start by proving a lower bound that shows that in this model, it is not possible to locally converge to an MIS in sub-polynomial time. We then study four different relaxations of the model which allow us to circumvent the lower bound and find an MIS in polylogarithmic time. First, we show that if a polynomial upper bound on the network size is known, it is possible to find an MIS in O(log^3 n) time. Second, if we assume sleeping nodes are awoken by neighboring beeps, then we can also find an MIS in O(log^3 n) time. Third, if in addition to this wakeup assumption we allow sender-side collision detection, that is, beeping nodes can distinguish whether at least one neighboring node is beeping concurrently or not, we can find an MIS in O(log^2 n) time. Finally, if instead we endow nodes with synchronous clocks, it is also possible to find an MIS in O(log^2 n) time.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Lower Bounds on Information Dissemination in Dynamic Networks

We study lower bounds on information dissemination in adversarial dynamic networks. Initially, k pieces of information (henceforth called tokens) are distributed among n nodes. The tokens need to be broadcast to all nodes through a synchronous network in which the topology can change arbitrarily from round to round provided that some connectivity requirements are satisfied. If the network is guaranteed to be connected in every round and each node can broadcast a single token per round to its neighbors, there is a simple token dissemination algorithm that manages to deliver all k tokens to all the nodes in O(nk) rounds. Interestingly, in a recent paper, Dutta et al. proved an almost matching Omega(n + nk/log n) lower bound for deterministic token-forwarding algorithms that are not allowed to combine, split, or change tokens in any way. In the present paper, we extend this bound in different ways. If nodes are allowed to forward b < k tokens instead of only one token in every round, a straight-forward extension of the O(nk) algorithm disseminates all k tokens in time O(nk/b). We show that for any randomized token-forwarding algorithm, Omega(n + nk/(b^2 log n log log n)) rounds are necessary. If nodes can only send a single token per round, but we are guaranteed that the network graph is c-vertex connected in every round, we show a lower bound of Omega(nk/(c log^{3/2} n)), which almost matches the currently best O(nk/c) upper bound. Further, if the network is T-interval connected, a notion that captures connection stability over time, we prove that Omega(n + nk/(T^2 log n)) rounds are needed. The best known upper bound in this case manages to solve the problem in O(n + nk/T) rounds. Finally, we show that even if each node only needs to obtain a delta-fraction of all the tokens for some delta in [0,1], Omega(nk delta^3 log n) are still required.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Computing a Maximal Independent Set Using Beeps

We consider the problem of finding a maximal independent set (MIS) in the discrete beeping model. At each time, a node in the network can either beep (i.e., emit a signal) or be silent. Silent nodes can only differentiate between no neighbor beeping, or at least one neighbor beeping. This basic communication model relies only on carrier-sensing. Furthermore, we assume nothing about the underlying communication graph and allow nodes to wake up (and crash) arbitrarily. We show that if a polynomial upper bound on the size of the network n is known, then with high probability every node becomes stable in O(\log^3 n) time after it is woken up. To contrast this, we establish a polynomial lower bound when no a priori upper bound on the network size is known. This holds even in the much stronger model of local message broadcast with collision detection. Finally, if we assume nodes have access to synchronized clocks or we consider a somewhat restricted wake up, we can solve the MIS problem in O(\log^2 n) time without requiring an upper bound on the size of the network, thereby achieving the same bit complexity as Luby's MIS algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Deploying Wireless Networks with Beeps

We present the \emph{discrete beeping} communication model, which assumes nodes have minimal knowledge about their environment and severely limited communication capabilities. Specifically, nodes have no information regarding the local or global structure of the network, don't have access to synchronized clocks and are woken up by an adversary. Moreover, instead on communicating through messages they rely solely on carrier sensing to exchange information. We study the problem of \emph{interval coloring}, a variant of vertex coloring specially suited for the studied beeping model. Given a set of resources, the goal of interval coloring is to assign every node a large contiguous fraction of the resources, such that neighboring nodes share no resources. To highlight the importance of the discreteness of the model, we contrast it against a continuous variant described in [17]. We present an O(1$ time algorithm that terminates with probability 1 and assigns an interval of size $Ω(T/Δ)$ that repeats every $T$ time units to every node of the network. This improves an $O(\log n)$ time algorithm with the same guarantees presented in \cite{infocom09}, and accentuates the unrealistic assumptions of the continuous model. Under the more realistic discrete model, we present a Las Vegas algorithm that solves $Ω(T/Δ)$-interval coloring in $O(\log n)$ time with high probability and describe how to adapt the algorithm for dynamic networks where nodes may join or leave. For constant degree graphs we prove a lower bound of $Ω(\log n)$ on the time required to solve interval coloring for this model against randomized algorithms. This lower bound implies that our algorithm is asymptotically optimal for constant degree graphs.

0 citations0 reviewsNo code linkedOpen access