Mohsen Ghaffari

A fundamental result by Karger [SODA 1994] states that for any $k$-edge connected graph with $n$ nodes, independently sampling each edge with probability $p = \Omega(\log n / k)$ results in a graph that has edge connectivity $\Omega(kp),ƒhƒ‹ with high probability. This paper proves the analogous result for vertex connectivity when independently sampling vertices.

We show that for any $k$-vertex-connected graph $G$ with $n$ nodes, if each node is independently sampled with probability $p=\Omega(\sqrt{\log n / k}),ƒhƒ‹ then the subgraph induced by the sampled nodes has vertex connectivity $\Omega(kp^2),ƒhƒ‹ with high probability. These bounds are existentially optimal and they improve upon the recent results of Censor-Hillel et al. [SODA 2014].

Tree embeddings are a powerful tool in the area of graph approximation algorithms. Roughly speaking, they transform problems on general graphs into much easier ones on trees. Fakcharoenphol, Rao, and Talwar (FRT) [STOC'04] present a probabilistic tree embedding that transforms $n$-node metrics into (probability distributions over) trees, while stretching each pairwise distance by at most an $O(\log n)$ factor in expectation. This $O(\log n)$ stretch is optimal.

Khan et al. [PODC'08] present a distributed algorithm that implements FRT in $O(\SPD \log n)$ rounds, where $\SPD$ is the shortest-path-diameter of the weighted graph, and they explain how to use this embedding for various distributed approximation problems. Note that $\SPD$ can be as large as $\Theta(n),ƒhƒ‹ even in graphs where the hop-diameter $D$ is a constant. Khan et al. noted that it would be interesting to improve this complexity. We show that this is indeed possible.

More precisely, we present a distributed algorithm that constructs a tree embedding that is essentially as good as FRT in $\tilde{O}(\min\{n^{0.5+\eps},\SPD\}+D)$ rounds, for any constant $\eps>0$. A lower bound of $\tilde{\Omega}(\min\{n^{0.5},\SPD\}+D)$ rounds follows from Das Sarma et al. [STOC'11], rendering our round complexity near-optimal.

All consensus hierarchies in the literature assume that we have, in addition to copies of a given object, an unbounded number of registers. But why do we really need these registers? This paper considers what would happen if one attempts to solve consensus using various objects but without any registers. We show that under a reasonable assumption, objects like queues and stacks cannot emulate the missing registers. We also show that, perhaps surprisingly, initialization, shown to have no computational consequences when registers are readily available, is crucial in determining the synchronization power of objects when no registers are allowed. Finally, we show that without registers, the number of available objects affects the level of consensus that can be solved. Our work thus raises the question of whether consensus hierarchies which assume an unbounded number of registers truly capture synchronization power, and begins a line of research aimed at better understanding the interaction between read-write memory and the powerful synchronization opera- tions available on modern architectures.

We study coding schemes for error correction in interactive communications. Such interactive coding schemes simulate any $n$-round interactive protocol using $N$ rounds over an adversarial channel that corrupts up to $\rho N$ transmissions. Important performance measures for a coding scheme are its maximum tolerable error rate $\rho,ƒhƒ‹ communication complexity $N,ƒhƒ‹ and computational complexity.

We give the first coding scheme for the standard setting which performs optimally in all three measures: Our randomized non-adaptive coding scheme has a near-linear computational complexity and tolerates any error rate $\delta < 1/4$ with a linear $N = \Theta(n)$ communication complexity. This improves over prior results [Braverman-Rao STOC'11; Brakerski-Kalai FOCS'12; Brakerski-Naor SODA'13; Ghaffari-Haeupler-Sudan STOC'14} which each performed well in two of these measures.

We also give results for other settings of interest, namely, the first computationally and communication efficient schemes that tolerate $\rho < \frac{2}{7}$ adaptively, $\rho < \frac{1}{3}$ if only one party is required to decode, and $\rho < \frac{1}{2}$ if list decoding is allowed. These are the optimal tolerable error rates for the respective settings. These coding schemes also have near linear computational and communication complexity.

These results are obtained via two techniques: We give a \emph{general black-box reduction} which reduces unique decoding, in various settings, to list decoding. We also show how to boost the computational and communication efficiency of any list decoder to become near linear.

We study the multi-message broadcast problem using abstract MAC layer models of wireless networks. These models capture the key guarantees of existing MAC layers while abstracting away low-level details such as signal propagation and contention. We begin by studying upper and lower bounds for this problem in a {\em standard abstract MAC layer model}---identifying an interesting dependence between the structure of unreliable links and achievable time complexity. In more detail, given a restriction that devices connected directly by an unreliable link are not too far from each other in the reliable link topology, we can (almost) match the efficiency of the reliable case. For the related restriction, however, that two devices connected by an unreliable link are not too far from each other in geographic distance, we prove a new lower bound that shows that this efficiency is impossible.

We then investigate how much extra power must be added to the model to enable solutions of a new order of magnitude of efficiency. We describe a new enhanced abstract MAC layer model and present a new multi-message broadcast algorithm that (under certain natural assumptions) solves the problem faster than any known solutions in an abstract MAC layer setting.

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 $\Omega(\frac{k}{\log n}),ƒhƒ‹ in $\widetilde{O}(D+\sqrt{n})$ rounds.

(II) A decomposition of each undirected graph with edge-connectivity $\lambda$ into (fractionally) edge-disjoint weighted spanning trees with total weight $\lceil\frac{\lambda-1}{2}\rceil(1-\varepsilon),ƒhƒ‹ in $\widetilde{O}(D+\sqrt{n\lambda})$ rounds.

We also show round complexity lower bounds of $\tilde{\Omega}(D+\sqrt{\frac{n}{k}})$ and $\tilde{\Omega}(D+\sqrt{\frac{n}{\lambda}})$ 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.

This paper presents a near-optimal distributed approximation algorithm for the minimum-weight connected dominating set (MCDS) problem in the CONGEST model, where in each round each node can send $\mathcal{O}(\log n)$ bits to each neighbor. The presented algorithm finds an $O(\log n)$ approximation in $\tilde{O}(D+\sqrt{n})$ rounds, where $D$ is the network diameter and $n$ is the number of nodes.

MCDS is a classical NP-hard problem and the achieved approximation factor $O(\log n)$ is known to be optimal up to a constant factor, unless $P=NP$. Furthermore, the $\tilde{O}(D+\sqrt{n})$ round complexity is known to be optimal modulo logarithmic factors (for any approximation), following [Das Sarma et al.---STOC'11].

We consider the task of interactive communication in the presence of adversarial errors and present tight bounds on the tolerable error-rates in a number of different settings. Most significantly, we explore adaptive interactive communication where the communicating parties decide who should speak next based on the history of the interaction. Braverman and Rao [STOC'11] show that non-adaptively one can code for any constant error rate below 1/4 but not more. They asked whether this bound could be improved using adaptivity. We answer this open question in the affirmative (with a slightly different collection of resources): Our adaptive coding scheme tolerates any error rate below 2/7 and we show that tolerating a higher error rate is impossible. We also show that in the setting of Franklin et al. [CRYPTO'13], where parties share randomness not known to the adversary, adaptivity increases the tolerable error rate from 1/2 to 2/3. For list-decodable interactive communications, where each party outputs a constant size list of possible outcomes, the tight tolerable error rate is 1/2.

Our negative results hold even if the communication and computation are unbounded, whereas for our positive results communication and computation are polynomially bounded. Most prior work considered coding schemes with linear amount of communication, while allowing unbounded computations. We argue that studying tolerable error rates in this relaxed context helps to identify a setting's intrinsic optimal error rate. We set forward a strong working hypothesis which stipulates that for any setting the maximum tolerable error rate is independent of many computational and communication complexity measures. We believe this hypothesis to be a powerful guideline for the design of simple, natural, and efficient coding schemes and for understanding the (im)possibilities of coding for interactive communications.

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 the classical results of Tutte and Nash-Williams from 1961 which show that a $\lambda$-edge-connected graph contains $\ceil{(\lambda-1)/2}$ edge-disjoint spanning trees.

We argue that connected dominating set partitions and packings are the natural analogues of edge-disjoint spanning trees in the context of vertex connectivity and we use them to obtain structural results about vertex connectivity in the spirit of those for edge connectivity.

More specifically, connected dominating set (CDS) partitions and packings are counterparts of edge-disjoint spanning trees, focusing on vertex-disjointness rather than edge-disjointness, and their sizes are always upper bounded by the vertex connectivity $k$. We constructively show that every $k$-vertex-connected graph with $n$ nodes has CDS packings and partitions with sizes, respectively, $\Omega(k/\log n)$ and $\Omega(k/\log^5 n ),ƒhƒ‹ and we prove that the former bound is existentially optimal.

Beautiful results by Karger show that when edges of a $\lambda$-edge-connected graph are independently sampled with probability $p,ƒhƒ‹ the sampled graph has edge connectivity $\tilde{\Omega}(\lambda p)$. Obtaining such a result for vertex sampling remained open. We illustrate the strength of our approach by proving that when vertices of a $k$-vertex-connected graph are independently sampled with probability $p,ƒhƒ‹ the graph induced by the sampled vertices has vertex connectivity $\tilde{\Omega}(kp^2)$. This bound is optimal up to poly-log factors and is proven by building an $\tilde{\Omega}(kp^2)$ size CDS packing on the sampled vertices while sampling happens.

As an additional important application, we show CDS packings to be tightly related to the throughput of routing-based algorithms and use our new toolbox to yield a routing-based broadcast algorithm with optimal throughput $\Omega(k/\log n + 1),ƒhƒ‹ improving the (previously best-known) trivial throughput of $\Theta(1)$.

The broadcast throughput in a network is defined as the average number of messages that can be transmitted per unit time from a given source to all other nodes when time goes to infinity.

Classical broadcast algorithms treat messages as atomic tokens and route them from the source to the receivers by making intermediate nodes store and forward messages. The more recent network coding approach, in contrast, prompts intermediate nodes to mix and code together messages. It has been shown that certain wired networks have an asymptotic network coding gap, that is, they have asymptotically higher broadcast throughput when using network coding compared to routing. Whether such a gap exists for wireless networks has been an open question of great interest. We approach this question by studying the broadcast throughput of the radio network model which has been a standard mathematical model to study wireless communication.

We show that there is a family of radio networks with a tight $\Theta(\log \log n)$ network coding gap, that is, networks in which the asymptotic throughput achievable via routing messages is a $\Theta(\log \log n)$ factor smaller than that of the optimal network coding algorithm. We also provide new tight upper and lower bounds that show that the asymptotic worst-case broadcast throughput over all networks with $n$ nodes is $\Theta(1 / \log n)$ messages-per-round for both routing and network coding.

We study the problem of computing approximate minimum edge cuts by distributed algorithms. We present two randomized approximation algorithms that both run in a standard synchronous message passing model where in each round, $O(log n)$ bits can be transmitted over every edge (a.k.a. the CONGEST model). The first algorithm is based on a simple and new approach for analyzing random edge sampling, which we call random layering technique. For any weighted graph and any $\epsilon \in (0, 1),ƒhƒ‹ the algorithm finds a cut of size at most $O(\epsilon^{-1}\lambda)$ in $O(D) + \tilde{O}(n^{1/2 + \epsilon})$ rounds, where $\lambda,ƒhƒ‹ D and n are respectively the minimum-cut size, the diameter and the number of nodes of the network. The $\tilde{O}$-notation hides poly-logarithmic factors in n. In addition, using the outline of a centralized algorithm due to Matula [SODA '93], we present a randomized algorithm to compute a cut of size at most $(2+\epsilon)\lambda$ in $\tilde{O}((D+\sqrt{n})/\epsilon^5)$ rounds for any $\epsilon>0$. The time complexities of our algorithms almost match the $\tilde{\Omega}(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].

To complement our upper bound results, we also strengthen the $\tilde{\Omega}(D + \sqrt{n})$ 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$). For unweighted simple graphs, we show that computing an $\alpha$-approximate minimum cut requires time at least $\tilde{\Omega}(D + \sqrt{n}/\alpha^{1/4})$.

We introduce collision free layerings as a powerful way to structure distributed radio networks. These layerings can replace hard-to-compute BFS-trees in many contexts while having an efficient randomized construction. We demonstrate their versatility by using them to provide near optimal distributed algorithms for several multi-message communication primitives.

Designing efficient communication primitives for radio networks has a rich history that began 25 years ago when Bar-Yehuda et al. introduced fast randomized algorithms for broadcasting and for constructing a BFS-tree. Their BFS-tree construction time was $O(D \log^2 n)$ rounds, where $D$ is the network diameter and $n$ is the number of nodes. Since then, the complexity of a broadcast has been resolved to be $T_{BC} = \Theta(D \log \frac{n}{D} + \log^2 n)$ rounds. On the other hand, BFS-trees have been used as a crucial building block for many communication primitives and the BFS-tree construction time remained a bottleneck for these primitives.

We introduce collision free layerings that can be used in place of BFS-trees and we give a randomized construction of these layerings that runs in nearly broadcast time, that is, whp in $T_{Lay} = O(D \log \frac{n}{D} + \log^{2+\eps} n)$ rounds for any constant $\eps>0$. We then use these layerings to obtain: (1) A randomized $k$-message broadcast running whp in $O(T_{Lay} + k \log n)$ rounds. (2) A randomized algorithm for gathering $k$ messages running whp in $O(T_{Lay} + k)$ rounds. These algorithms are optimal up to the small difference in the additive poly-logarithmic term between $T_{BC}$ and $T_{Lay}$. Moreover, they imply the first optimal $O(n \log n)$ round randomized gossip algorithm.

We present a randomized distributed algorithm that in radio networks with collision detection broadcasts a single message in $O(D + \log^6 n)$ rounds, with high probability\footnote{We use the phrase ``high probability" to indicate a probability at least 1ƒhƒ‹- \frac{1}{n^c},ƒhƒ‹ for a constant $c\geq 1,ƒhƒ‹ and where $n$ is the network size.}. This time complexity is most interesting because of its optimal additive dependence on the network diameter $D$. It improves over the currently best known $O(D\log\frac{n}{D},‰~+,‰~\log^2 n)$ algorithms, due to Czumaj and Rytter [FOCS 2003], and Kowalski and Pelc [PODC 2003]. These algorithms where designed for the model without collision detection and are optimal in that model. However, as explicitly stated by Peleg in his 2007 survey on broadcast in radio networks, it had remained an open question whether the bound can be improved with collision detection.

We also study distributed algorithms for broadcasting $k$ messages from a single source to all nodes. This problem is a natural and important generalization of the single-message broadcast problem, but is in fact considerably more challenging and less understood. We show the following results: If the network topology is known to all nodes, then a $k$-message broadcast can be performed in $O(D + k\log n + \log^2 n)$ rounds, with high probability. If the topology is not known, but collision detection is available, then a $k$-message broadcast can be performed in $O(D + k\log n + \log^6 n)$ rounds, with high probability. The first bound is optimal and the second is optimal modulo the additive $O(\log^6 n)$ term.

We study upper and lower bounds for the global and local broadcast problems in the dual graph model combined with different strength adversaries. The dual graph model is a generalization of the standard graph-based radio network model that includes unreliable links controlled by an adversary. It is motivated by the ubiquity of unreliable links in real wireless networks. Existing results in this model assume an offline adaptive adversary—the strongest type of adversary considered in standard randomized analysis. In this paper, we study the two other standard types of adversaries: online adaptive and oblivious. Our goal is to find a model that captures the unpredictable behavior of real networks while still allowing for efficient broadcast solutions.

For the online adaptive dual graph model, we prove a lower bound that shows the existence of constant-diameter graphs in which both types of broadcast require $Omega(n/ \log n)$ rounds, for network size n. This result is within log-factors of the (near) tight upper bound for the of?ine adaptive setting. For the oblivious dual graph model, we describe a global broadcast algorithm that solves the problem in $O(D \log n + \log^2 n)$ rounds for network diameter D, but prove a lower bound of $\Omega(\sqrt{n}/ log n)$ rounds for local broadcast in this same setting. Finally, under the assumption of geographic constraints on the network graph, we describe a local broadcast algorithm that requires only $O(\log^2 n \log \Delta)$ rounds in the oblivious model, for maximum degree $\Delta$. In addition to the theoretical interest of these results, we argue that the oblivious model (with geographic constraints) captures enough behavior of real networks to render our efficient algorithms useful for real deployments.

We present new upper bounds for fundamental problems in multichannel wireless networks. These bounds address the benefits of dynamic spectrum access, i.e., to what extent multiple communication channels can be used to improve performance. In more detail, we study a multichannel generalization of the standard graph-based wireless model without collision detection, and assume the network topology satisfies polynomially bounded independence.

Our core technical result is an algorithm that constructs a maximal independent set (MIS) in $O(\frac{\log^2 n}{F})+\softO(\log{n})$ rounds, in networks of size $n$ with $F$ channels, where the $\softO$-notation hides polynomial factors in $\log\log n$.

Moreover, we use this MIS algorithm as a subroutine to build a constant-degree connected dominating set in the same asymptotic time. Leveraging this structure, we are able to solve global broadcast and leader election within $O(D + \frac{\log^2 n}{F})+\softO(\log{n})$ rounds, where $D$ is the diameter of the graph, and $k$-message multi-message broadcast in $O(D + k + \frac{\log^2 n}{F})+\softO(\log n)$ rounds for unrestricted message size (with a slow down of only a $\log$ factor on the $k$ term under the assumption of restricted message size).

In all five cases above, we prove: (a) our results hold with high probability (i.e., at least 1ƒhƒ‹-1/n$); (b) our results are within $\poly{\log\log{n}}$-factors of the relevant lower bounds for multichannel networks; and (c) our results beat the relevant lower bounds for single channel networks. These new (near) optimal algorithms significantly expand the number of problems now known to be solvable faster in multichannel versus single channel wireless networks.

We design leader election protocols for multi-hop radio networks that elect a leader in almost the same time $T_{BC}$ that it takes for broadcasting one message (one ID). For the setting without collision detection our algorithm runs whp. in $O(D \log \frac{n}{D} + \log^3 n) \cdot \min\{\log\log n,\log \frac{n}{D}\}$ rounds on any $n$-node network with diameter $D$. Since $T_{BC} = \Theta(D \log \frac{n}{D} + \log^2 n)$ is a lower bound, our upper bound is optimal up to a factor of at most $\log \log n$ and the extra $\log n$ factor on the additive term. Our algorithm is furthermore the first $O(n)$ time algorithm for this setting.

Our algorithm improves over a 23 year old simulation approach of Bar-Yehuda, Goldreich and Itai with a $O(T_{BC} \log n)$ running time: In 1987 they designed a fast broadcast protocol and subsequently in 1989 they showed how it can be used to simulate one round of a single-hop network that has collision detection in $T_{BC}$ time. The prime application of this simulation was to simulate Willards single-hop leader election protocol, which elects a leader in $O(\log n)$ rounds whp. and $O(\log \log n)$ rounds in expectation. While it was subsequently shown that Willards bounds are tight, it was unclear whether the simulation approach is optimal. Our results break this barrier and essentially remove the logarithmic slowdown over the broadcast time $T_{BC}$. This is achieved by going away from the simulation approach.

We also give an $O(D + \log n \log \log n) \cdot \min\{\log \log n, \log \frac{n}{D}\} = O(D + \log n) \cdot O(\log \log n)^2$ leader election algorithm for the setting with collision detection (even with single-bit messages). This is optimal up to $\log \log n$ factors and improves over a deterministic algorithm that requires $\Theta(n)$ rounds independently of D.

Our almost optimal leader election protocols are especially important because countless communication protocols in radio networks use leader election as a crucial first step to solve various, seemingly unrelated, communication primitives such as gathering, multiple unicasts or multiple broadcasts. Even though leader election seems easier than these tasks, its best-known $O(T_{BC} \log n)$ running time had become a bottleneck, preventing optimal algorithms. Breaking the simulation barrier for leader election in this paper has subsequently led to the development of near optimal protocols for these communication primitives.

The local broadcast problem assumes that processes in a wireless network are provided messages, one by one, that must be delivered to their neighbors. In this paper, we prove tight bounds for this problem in two well-studied wireless network models: the classical model, in which links are reliable and collisions consistent, and the more recent dual graph model, which introduces unreliable edges. Our results prove that the Decay strategy, commonly used for local broadcast in the classical setting, is optimal. They also establish a separation between the two models, proving that the dual graph setting is strictly harder than the classical setting, with respect to this primitive.

We consider the problem of leader election (LE) in singlehop radio networks with synchronized time slots for transmitting and receiving messages. We assume that the actual number n of processes is unknown, while the size u of the ID space is known, but possibly much larger. We consider two types of collision detection: strong (SCD), whereby all processes detect collisions, and weak (WCD), whereby only non-transmitting processes detect collisions.

We introduce loneliness detection (LD) as a key subproblem for solving LE in WCD systems. LD informs all processes whether the system contains exactly one process or more than one. We show that LD captures the difference in power between SCD and WCD, by providing an implementation of SCD over WCD and LD. We present two algorithms that solve deterministic and probabilistic LD in WCD systems with time costs of O(log u/n) and O(min(log u/n, log(1/epsilon)/n)), respectively, where epsilon is the error probability. We also provide matching lower bounds.

We present two algorithms that solve deterministic and probabilistic LE in SCD systems with time costs of O(log u) and O(min(log u, log log n+ log(1/epsilon))), respectively, where epsilon is the error probability. We provide matching lower bounds.

Contact Information:

Computer Science and Artificial Intelligence Lab (CSAIL)
Massachusetts Institute of Technology (MIT)
32 Vassar Street, Room 32-G618
Cambridge, MA, USA 02139

Phone: 001-617-715-4018
Email: my-last-name at mit.edu

Assistant: Nathan Higgins

For matters related to ETH Zurich, please contact my assistant Andrea Salow.

Accessibility

web stats