Publications 
Manuela Fischer,
Mohsen Ghaffari, and Fabian Kuhn
Deterministic Distributed Edge Coloring via Hypergraph Maximal Matching
IEEE Symposium on Foundations of Computer Science (FOCS) 2017.
[Abstract]
[arXiv]
We present a deterministic distributed algorithm that computes a $(2\Delta1)$edgecoloring, or even listedgecoloring,
in any $n$node graph with maximum degree $\Delta$, in $O(\log^7 \Delta \cdot \log n)$ rounds. This answers one of the
longstanding open questions of distributed graph algorithms from the late 1980s, which asked for a polylogarithmictime algorithm.
See, e.g., Open Problem 4 in the Distributed Graph Coloring book of Barenboim and Elkin. The previous best round complexities were $2^{O(\sqrt{\log n})}$
by Panconesi and Srinivasan [STOC'92] and $\tilde{O}(\sqrt{\Delta}) + O(\log^* n)$ by Fraigniaud, Heinrich, and Kosowski [FOCS'16].
A corollary of our deterministic listedgecoloring also improves the randomized complexity of $(2\Delta1)$edgecoloring to $\poly(\log\log n)$ rounds.
The key technical ingredient is a deterministic distributed algorithm for hypergraph maximal matching, which we believe will be
of interest beyond this result. In any hypergraph of rank $r$  where each hyperedge has at most $r$ vertices  with $n$ nodes and
maximum degree $\Delta$, this algorithm computes a maximal matching in $O(r^5 \log^{6+\log r } \Delta \cdot \log n)$ rounds.
This hypergraph matching algorithm and its extensions also lead to a number of other results. In particular, we obtain a polylogarithmictime
deterministic distributed maximal independent set (MIS) algorithm for graphs with bounded neighborhood independence, hence answering Open Problem 5
of Barenboim and Elkin's book, a $\big((\log \Delta/\epsilon)^{O(\log 1/\epsilon)}\big)$round deterministic algorithm for $(1+\epsilon)$approximation of maximum matching,
and a quasipolylogarithmictime deterministic distributed algorithm for orienting $\lambda$arboricity graphs with outdegree at most $\ceil{(1+\epsilon)\lambda}$,
for any constant $\epsilon>0$, hence partially answering Open Problem 10 of Barenboim and Elkin's book.
Manuela Fischer and
Mohsen Ghaffari
Sublogarithmic Distributed Algorithms for Lovász Local Lemma, and the Complexity Hierarchy
International Symposium on DIStributed Computing (DISC) 2017.
[Abstract]
[arXiv]
Locally Checkable Labeling (LCL) problems include essentially all the classic problems of LOCAL distributed algorithms.
In a recent enlightening revelation, Chang and Pettie [FOCS'17] showed that any LCL (on bounded degree graphs) that
has an $o(\log n)$round randomized algorithm can be solved in $T_{LLL}(n)$ rounds, which is the randomized complexity
of solving (a relaxed variant of) the Lov\'{a}sz Local Lemma (LLL) on bounded degree $n$node graphs.
Currently, the best known upper bound on $T_{LLL}(n)$ is $O(\log n)$, by Chung, Pettie, and Su [PODC'14], while the best
known lower bound is $\Omega(\log\log n)$, by Brandt et al. [STOC'16]. Chang and Pettie conjectured that there should be an $O(\log\log n)$round algorithm.
Making the first step of progress towards this conjecture, and providing a significant improvement on the algorithm of Chung et al.
[PODC'14], we prove that $T_{LLL}(n)= 2^{O(\sqrt{\log\log n})}$. Thus, any $o(\log n)$round randomized distributed algorithm for
any LCL problem on bounded degree graphs can be automatically sped up to run in $2^{O(\sqrt{\log\log n})}$ rounds.
Using this improvement and a number of other ideas, we also improve the complexity of a number of graph coloring problems
(in arbitrary degree graphs) from the $O(\log n)$round results of Chung, Pettie and Su [PODC'14] to $2^{O(\sqrt{\log\log n})}$.
These problems include defective coloring, frugal coloring, and list vertexcoloring.
Mohsen Ghaffari and Christiana Lymouri
Simple and NearOptimal Distributed Coloring for Sparse Graphs
International Symposium on DIStributed Computing (DISC) 2017.
Mohsen Ghaffari and Merav Parter
NearOptimal Distributed DFS in Planar Graphs
International Symposium on DIStributed Computing (DISC) 2017.
Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, and Jara Uitto
Improved Distributed Degree Splitting and Edge Coloring
International Symposium on DIStributed Computing (DISC) 2017.
Best Paper Award at DISC'17.
[Abstract]
[arXiv]
The degree splitting problem requires coloring the edges of a graph red or blue such that each node has
almost the same number of edges in each color, up to a small additive discrepancy. The directed variant
of the problem requires orienting the edges such that each node has almost the same number of incoming
and outgoing edges, again up to a small additive discrepancy.
We present deterministic distributed algorithms for both variants, which improve on their counterparts
presented by Ghaffari and Su [SODA'17]: our algorithms are significantly simpler and faster, and have a
much smaller discrepancy. This also leads to a faster and simpler deterministic algorithm for
$(2+o(1))\Delta$edgecoloring, improving on that of Ghaffari and Su.
Mohsen Ghaffari,
Distributed MIS via AlltoAll Communication
ACM Symposium on Principles of Distributed Computing (PODC) 2017.
Mohsen Ghaffari, Fabian Kuhn, and HsinHao Su,
Distributed MST and Routing in Almost Mixing Time
ACM Symposium on Principles of Distributed Computing (PODC) 2017.
Reuven BarYehuda, Keren Censor Hillel, Mohsen Ghaffari, and Gregory Schwartzman
Distributed Approximation of Maximum Independent Set and Maximum Matching
ACM Symposium on Principles of Distributed Computing (PODC) 2017.

This paper is centered on the complexity of graph problems in the
wellstudied \LOCAL model of distributed computing, introduced by
Linial [FOCS '87]. It is widely known that for many of the classic
distributed graph problems (including maximal independent set (MIS)
and $(\Delta+1)$vertex coloring), the randomized complexity is at
most polylogarithmic in the size $n$ of the network, while the best
deterministic complexity is typically $2^{O(\sqrt{\log n})}$.
Understanding and potentially narrowing down this exponential gap is
considered to be one of the central longstanding open questions in
the area of distributed graph algorithms.
We investigate the problem by introducing a complexitytheoretic
framework that allows us to shed some light on the role of
randomness in the \LOCAL model. We define the \SLOCAL model as a
sequential version of the \LOCAL model. Our framework allows us to
prove \emph{completeness} results with respect to the class of
problems which can be solved efficiently in the \SLOCAL model,
implying that if any of the complete problems can be solved
deterministically in $\poly\log n$ rounds in the \LOCAL model, we
can deterministically solve all efficient \SLOCALproblems
(including MIS and $(\Delta+1)$coloring) in $\poly\log n$ rounds in
the \LOCAL model.
Perhaps most surprisingly, we show that a rather rudimentary looking
graph coloring problem is \emph{complete} in the above sense: Color
the nodes of a graph with colors red and blue such that each node of
sufficiently large polylogarithmic degree has at least one neighbor
of each color. The problem admits a trivial zeroround randomized
solution. The result can be viewed as showing that the only
obstacle to getting efficient determinstic algorithms in the \LOCAL
model is an efficient algorithm to \emph{approximately round
fractional values into integer values}.
In addition, our formal framework also allows us to develop
polylogarithmictime randomized distributed algorithms in a simpler
way. As a result, we provide a polylogtime distributed
approximation scheme for arbitrary distributed covering and packing
integer linear programs.
Mohsen Ghaffari and HsinHao Su,
Distributed Degree Splitting, Edge Coloring, and Orientations
ACMSIAM Symposium on Discrete Algorithms (SODA) 2017.
Mohsen Ghaffari, David Karger, and Debmalya Panigrahi,
Random Contractions and Sampling for Hypergraph and Hedge Connectivity.
ACMSIAM Symposium on Discrete Algorithms (SODA) 2017.

Mohsen Ghaffari and Calvin Newport,
How to Discreetly Spread a Rumor in a Crowd
International Symposium on DIStributed Computing (DISC) 2016.
Mohsen Ghaffari and Merav Parter,
MST in LogStar Rounds of Congested Clique
ACM Symposium on Principles of Distributed Computing (PODC) 2016.
Invited Talk at Highlights of Algorithms (HALG) 2017.
Mohsen Ghaffari and Bernhard Haeupler,
Distributed Algorithms for Planar Networks I: Planar Embedding
ACM Symposium on Principles of Distributed Computing (PODC) 2016.
Mohsen Ghaffari and Merav Parter,
A Polylogarithmic Gossip Algorithm for Plurality Consensus
ACM Symposium on Principles of Distributed Computing (PODC) 2016.
Mohsen Ghaffari and Merav Parter,
NearOptimal Distributed Algorithms for FaultTolerant Tree Structures
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2016.
Mohsen Ghaffari and Calvin Newport,
Leader Election in Unreliable Radio Networks
International Colloquium on Automata, Languages, and Programming (ICALP) 2016.
Mohsen Ghaffari,
An Improved Distributed Algorithm for Maximal Independent Set
ACMSIAM Symposium on Discrete Algorithms (SODA) 2016.
Best Paper Award (cowinner) and Best Student Paper Award at SODA'16.
Invited Talk at Highlights of Algorithms (HALG) 2017.
Invited Talk at Symposium on Theory of Computing (STOC) 2017.
Mohsen Ghaffari and Bernhard Haeupler,
Distributed Algorithms for Planar Networks II: LowCongestion Shortcuts, MST, and MinCut
ACMSIAM Symposium on Discrete Algorithms (SODA) 2016.
Mohsen Ghaffari,
NearOptimal Scheduling of Distributed Algorithms
ACM Symposium on Principles of Distributed Computing (PODC) 2015.
Best Student Paper Award at PODC'15.
Mohsen Ghaffari,
Andreas Karrenbauer,
Fabian Kuhn,
Christoph Lenzen, and
Boaz PattShamir,
NearOptimal Distributed Maximum Flow
ACM Symposium on Principles of Distributed Computing (PODC) 2015.
Mohsen Ghaffari,
Cameron Musco, Tsvetomira Radeva, and Nancy Lynch,
Distributed HouseHunting in Ant Colonies
ACM Symposium on Principles of Distributed Computing (PODC) 2015.
Mohsen Ghaffari,
Distributed Broadcast Revisited: Towards Universal Optimality
International Colloquium on Automata, Languages, and Programming (ICALP) 2015.

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)$, with high probability. This
paper proves the analogous result for vertex connectivity when
independently sampling vertices.
We show that for any $k$vertexconnected graph $G$ with $n$ nodes,
if each node is independently sampled with probability
$p=\Omega(\sqrt{\log n / k})$, then the subgraph induced by the
sampled nodes has vertex connectivity $\Omega(kp^2)$, with high
probability. These bounds are existentially optimal and they improve
upon the recent results of CensorHillel et al. [SODA 2014].
Mohsen Ghaffari and
Christoph Lenzen,
NearOptimal Distributed Tree Embedding
International Symposium on DIStributed Computing (DISC) 2014.
[Abstract]
[PDF]
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 shortestpathdiameter 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)$, even in graphs where the hopdiameter $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 nearoptimal.
Rati Gelashvili,
Mohsen Ghaffari,
Jerry Li and
Nir Shavit,
On the Importance of Registers for Computability
International Conference on Principles of Distributed Systems (OPODIS) 2014.
[Abstract]
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 readwrite memory and the powerful synchronization opera
tions available on modern architectures.
Mohsen Ghaffari and
Bernhard Haeupler,
Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding
IEEE Symposium on Foundations of Computer Science (FOCS) 2014.
[Abstract]
[PDF]
[arXiv]
[Press Coverage: MIT News]
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$,
communication complexity $N$, and computational complexity.
We give the first coding scheme for the standard setting which performs optimally in all three measures: Our randomized nonadaptive coding scheme has a nearlinear computational
complexity and tolerates any error rate $\delta < 1/4$ with a linear $N = \Theta(n)$ communication complexity. This improves over prior results [BravermanRao STOC'11; BrakerskiKalai FOCS'12; BrakerskiNaor SODA'13; GhaffariHaeuplerSudan 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 blackbox 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.
Mohsen Ghaffari,
Erez Kantor,
Nancy Lynch, and
Calvin Newport,
MultiMessage Broadcast with Abstract MAC Layers and Unreliable Links
ACM Symposium on Principles of Distributed Computing (PODC) 2014.
[Abstract]
We study the multimessage broadcast problem using abstract MAC layer models of wireless networks. These models capture the key guarantees of existing MAC layers
while abstracting away lowlevel 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 multimessage broadcast algorithm that (under certain natural assumptions) solves the problem faster than any known solutions in an abstract MAC layer setting.
Keren Censor Hillel, Mohsen Ghaffari, and
Fabian Kuhn,
Distributed Connectivity Decomposition
ACM Symposium on Principles of Distributed Computing (PODC) 2014.
Best Student Paper Award at PODC'14.
[Abstract]
[PDF]
[arXiv]
We present timeefficient 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 vertexconnectivity $k$ into (fractionally) vertexdisjoint weighted dominating trees with total weight $\Omega(\frac{k}{\log n})$, in $\widetilde{O}(D+\sqrt{n})$ rounds.
(II) A decomposition of each undirected graph with edgeconnectivity $\lambda$ into (fractionally) edgedisjoint weighted spanning trees with total weight $\lceil\frac{\lambda1}{2}\rceil(1\varepsilon)$, 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 vertexconnectivity decomposition extends to centralized algorithms and improves the time complexity of [CensorHillel et al., SODA'14] from $O(n^3)$ to nearoptimal $\tilde{O}(m)$.
As corollaries, we also get distributed oblivious routing broadcast with $O(1)$competitive edgecongestion and $O(\log n)$competitive vertexcongestion. Furthermore, the vertex connectivity decomposition leads to neartimeoptimal $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.
Mohsen Ghaffari,
NearOptimal Distributed Approximation of MinimumWeight Connected Dominating Set
International Colloquium on Automata, Languages, and Programming (ICALP) 2014.
Best Student Paper Award at ICALP'14, track C.
[Abstract]
[PDF]
[arXiv]
This paper presents a nearoptimal distributed approximation algorithm for the minimumweight 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 NPhard 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].
Mohsen Ghaffari and
Bernhard Haeupler, and Madhu Sudan,
Optimal Error Rates for Interactive Coding I: Adaptivity and Other Settings
ACM Symposium on Theory of Computing (STOC) 2014.
[Abstract]
[PDF]
[arXiv]
We consider the task of interactive communication in the presence of adversarial errors and present tight bounds on the tolerable errorrates 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 nonadaptively 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 listdecodable 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 NashWilliams from 1961 which show that a $\lambda$edgeconnected graph contains $\ceil{(\lambda1)/2}$ edgedisjoint spanning trees.
We argue that connected dominating set partitions and packings are the natural analogues of edgedisjoint 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 edgedisjoint spanning trees, focusing on vertexdisjointness rather than edgedisjointness, and their sizes are always upper bounded by the vertex connectivity $k$.
We constructively show that every $k$vertexconnected graph with $n$ nodes has CDS packings and partitions with sizes, respectively, $\Omega(k/\log n)$ and $\Omega(k/\log^5 n )$, and we prove that the former bound is existentially optimal.
Beautiful results by Karger show that when edges of a $\lambda$edgeconnected graph are independently sampled with probability $p$, 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$vertexconnected graph are independently sampled with probability $p$, the graph induced by the sampled vertices has vertex connectivity $\tilde{\Omega}(kp^2)$. This bound is optimal up to polylog 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 routingbased algorithms and use our new toolbox to yield a routingbased broadcast algorithm with optimal throughput $\Omega(k/\log n + 1)$, improving the (previously bestknown) trivial throughput of $\Theta(1)$.
Noga Alon, Mohsen Ghaffari,
Bernhard Haeupler, and
Majid Khabbazian,
Broadcast Throughput in Radio Networks: Routing vs. Network Coding
ACMSIAM Symposium on Discrete Algorithms (SODA) 2014.
[Abstract] [PDF]
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 worstcase broadcast throughput over all networks with $n$ nodes is $\Theta(1 / \log n)$ messagesperround for both routing and network coding.
Mohsen Ghaffari and Fabian Kuhn,
Distributed Minimum Cut Approximation
International Symposium on DIStributed Computing (DISC) 2013.
Best Paper Award at DISC'13.
[Abstract]
[PDF]
[arXiv]
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)$, 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$, D and n are respectively the minimumcut size, the diameter and the number of nodes of the network. The $\tilde{O}$notation hides polylogarithmic 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 [SIGACTNews '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})$.
Mohsen Ghaffari and
Bernhard Haeupler,
Fast Structuring of Radio Networks for MultiMessage Communications
International Symposium on DIStributed Computing (DISC) 2013.
[Abstract]
[PDF]
[arXiv]
We introduce collision free layerings as a powerful way to structure distributed radio networks. These layerings can replace hardtocompute BFStrees in many contexts while having an efficient randomized construction. We demonstrate their versatility by using them to provide near optimal distributed algorithms for several multimessage communication primitives.
Designing efficient communication primitives for radio networks has a rich history that began 25 years ago when BarYehuda et al. introduced fast randomized algorithms for broadcasting and for constructing a BFStree. Their BFStree 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, BFStrees have been used as a crucial building block for many communication primitives and the BFStree construction time remained a bottleneck for these primitives.
We introduce collision free layerings that can be used in place of BFStrees 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 polylogarithmic term between $T_{BC}$ and $T_{Lay}$. Moreover, they imply the first optimal $O(n \log n)$ round randomized gossip algorithm.
Mohsen Ghaffari,
Bernhard Haeupler, and
Majid Khabbazian,
Randomized Broadcast in Radio Networks with Collision Detection
ACM Symposium on Principles of Distributed Computing (PODC) 2013.
[Abstract]
[PDF]
[arXiv]
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 \frac{1}{n^c}$, for a constant $c\geq 1$, 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 singlemessage 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.
Mohsen Ghaffari,
Nancy Lynch, and
Calvin Newport,
The Cost of Radio Network Broadcast for Different Models of Unreliable Links
ACM Symposium on Principles of Distributed Computing (PODC) 2013.
[Abstract]
[PDF] [Press Coverage: MIT News]
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 graphbased 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
constantdiameter graphs in which both types of broadcast require $Omega(n/ \log n)$ rounds, for network
size n. This result is within logfactors 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.
Sebastian Daum,
Mohsen Ghaffari,
Seth Gilbert,
Fabian Kuhn,
and
Calvin Newport,
Maximal Independent Sets in Multichannel Radio Networks
ACM Symposium on Principles of Distributed Computing (PODC) 2013.
[Abstract]
[PDF]
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 graphbased 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 constantdegree
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 multimessage 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 $11/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.
Mohsen Ghaffari and
Bernhard Haeupler,
NearOptimal Leader Election in MultiHop Radio Networks
ACMSIAM Symposium on Discrete Algorithms (SODA) 2013.
[Abstract]
[PDF]
[arXiv]
We design leader election protocols for multihop 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 BarYehuda, 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 singlehop network that has collision detection in $T_{BC}$ time. The prime application of this simulation was to simulate Willards singlehop 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 singlebit 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 bestknown $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.
Mohsen Ghaffari,
Seth Gilbert,
Calvin Newport, and Henry Tan,
Optimal Broadcast in Shared Spectrum Radio Networks
International Conference Principles of Distributed Systems (OPODIS) 2012.
Mohsen Ghaffari,
Bernhard Haeupler,
Nancy Lynch, and
Calvin Newport,
Bounds on Contention Management in Radio Networks
International Symposium on DIStributed Computing (DISC) 2012.
[Abstract]
[PDF]
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 wellstudied 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.
Mohsen Ghaffari,
Nancy Lynch, and
Srikanth Sastry,
Leader Election Using Loneliness Detection International Symposium on DIStributed Computing (DISC) 2011 + Distributed Computing Journal 2012.
[Abstract]
[PDF]
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 nontransmitting 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.
