|
|
Mohsen Ghaffari and Christoph Grunau
Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS
IEEE Symposium on Foundations of Computer Science (FOCS) 2024.
Best Paper Award at FOCS'24
Mohsen Ghaffari and Anton Trygub
A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP
ACM Symposium on Principles of Distributed Computing (PODC) 2024.
Mohsen Ghaffari and Anton Trygub
Parallel Dynamic Maximal Matching
ACM Symposium on Parallel Algorithms and Architectures (SPAA) 2024.
Shashwat Chandra, Yi-Jun Chang, Michal Dory, Mohsen Ghaffari, and Dean Leitersdorf
Fast Broadcast in Highly Connected Networks
ACM Symposium on Parallel Algorithms and Architectures (SPAA) 2024.
Mohsen Ghaffari and Christoph Grunau
Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping
ACM Symposium on Theory of Computing (STOC) 2024.
[arXiv]
Mohsen Ghaffari and Brandon Wang
Lenzen's Distributed Routing Generalized: A Full Characterization of Constant-Time Routability
ACM Symposium on Theory of Computing (STOC) 2024.
Mohsen Ghaffari and Christoph Grunau
Dynamic O(arboricity) coloring in polylogarithmic worst-case time
ACM Symposium on Theory of Computing (STOC) 2024.
Maxime Flin, Mohsen Ghaffari, Fabian Kuhn, Magnus Halldorsson, and Alexandre Nolin
A Distributed Palette Sparsification Theorem
ACM Symposium on Discrete Algorithms (SODA) 2024.
[arXiv]
Mohsen Ghaffari, Christoph Grunau, and Vaclav Rozhon
Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence
IEEE Symposium on Foundations of Computer Science (FOCS) 2023.
[arXiv]
Mohsen Ghaffari and Anton Trygub
A Near-Optimal Deterministic Distributed Synchronizer
ACM Symposium on Principles of Distributed Computing (PODC) 2023.
Best Student Paper Award at PODC'23.
[arXiv]
Mohsen Ghaffari and Julian Portmann
Distributed MIS with Low Energy and Time Complexities
ACM Symposium on Principles of Distributed Computing (PODC) 2023.
[arXiv]
Mohsen Ghaffari, Christoph Grunau, and Jiahao Qu
Nearly Work-Efficient Parallel DFS in Undirected Graphs
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2023.
Best Paper Award at SPAA'23
[arXiv]
Maxime Flin, Mohsen Ghaffari, Magnus Halldorsson, Fabian Kuhn, and Alexandre Nolin
Coloring Fast with Broadcasts
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2023.
[arXiv]
Mohsen Ghaffari and Christoph Grunau
Faster Deterministic Distributed MIS and Approximate Matching
ACM Symposium on Theory of Computing (STOC) 2023.
[arXiv]
Salwa Faour, Mohsen Ghaffari, Christoph Grunau,
Fabian Kuhn, and Vaclav Rozhon
Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond
ACM Symposium on Discrete Algorithms (SODA) 2023.
Invited to the special issue of SODA'23
[arXiv]
Michal Dory and Mohsen Ghaffari
A Nearly Time-Optimal Distributed Approximation of Minimum Cost k-Edge-Connected Spanning Subgraph
ACM Symposium on Discrete Algorithms (SODA) 2023.
[arXiv]
Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, and Vaclav Rozhon
Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization
ACM Symposium on Discrete Algorithms (SODA) 2023.
[arXiv]
Mohsen Ghaffari
Local Computation of Maximal Independent Set
IEEE Symposium on Foundations of Computer Science (FOCS) 2022.
Invited to the special issue of FOCS'22
Invited talk at Highlights of Algorithms (HALG) 2023
[arXiv]
Michal Dory, Mohsen Ghaffari, and Saeed Ilchi
Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs
ACM Symposium on Principles of Distributed Computing (PODC) 2022.
Invited to the special issue of PODC'22
[arXiv]
Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, and Dennis Olivetti
Node and Edge Averaged Complexities of Local Graph Problems
ACM Symposium on Principles of Distributed Computing (PODC) 2022.
Invited to the special issue of PODC'22
[arXiv]
Mohsen Ghaffari and Goran Zuzic
Universally-Optimal Distributed Exact Min-Cut
ACM Symposium on Principles of Distributed Computing (PODC) 2022.
[arXiv]
Mohsen Ghaffari and Julian Portmann
Awake Complexity of MIS and Matching
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2022.
[arXiv]
Mohsen Ghaffari, Christoph Grunau, and Slobodan Mitrovic
Massively Parallel Algorithms for b-Matching
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2022.
[arXiv]
Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari,
Christoph Grunau, Bernhard Haeupler,
Saeed Ilchi, and Vaclav Rozhon
Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2022.
[arXiv]
Bernhard Haeupler ® Harald Raecke ® Mohsen Ghaffari
Hop-Constrained Expander Decompositions, Oblivious Routing, and Distributed Universal Optimality
ACM Symposium on Theory of Computing (STOC) 2022.
Mohsen Ghaffari and Fabian Kuhn
Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition
IEEE Symposium on Foundations of Computer Science (FOCS) 2021.
[arXiv]
Yi-Jun Chang and Mohsen Ghaffari
Strong-Diameter Network Decomposition
ACM Symposium on Principles of Distributed Computing (PODC) 2021.
[arXiv]
Mohsen Ghaffari and Bernhard Haeupler
Low-Congestion Shortcuts for Graphs Excluding Dense Minors
ACM Symposium on Principles of Distributed Computing (PODC) 2021.
[arXiv]
Amartya Shankha Biswas, Michal Dory, Mohsen Ghaffari, Slobodan Mitrovic, and Yasamin Nazari
Massively Parallel Algorithms for Distance Approximation and Spanners
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2021.
[arXiv]
Mohsen Ghaffari, Bernhard Haeupler, and Goran Zuzic
Hop-constrained Oblivious Routing
ACM Symposium on Theory of Computing (STOC) 2021.
Invited to the special issue of STOC'21
[arXiv]
Mohsen Ghaffari, Christoph Grunau, and Vaclav Rozhon
Improved Deterministic Network Decomposition
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2021.
[arXiv]
Mohsen Ghaffari and Bernhard Haeupler
A Time-Optimal Randomized Parallel Algorithm for MIS
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2021.
Mohsen Ghaffari and Krzysztof Nowicki
Massively Parallel Algorithms for Minimum Cut
ACM Symposium on Principles of Distributed Computing (PODC) 2020.
Mohsen Ghaffari, Ce Jin, and Daan Nilis
A Massively Parallel Algorithm for Minimum Weight Vertex Cover
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2020.
[arXiv]
Mohsen Ghaffari, Christoph Grunau, and Ce Jin
Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond
International Symposium on DIStributed Computing (DISC) 2020.
[arXiv]
Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup
Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2020.
[arXiv]
Mohsen Ghaffari,
Fabian Kuhn, and
Jara Uitto
Conditional Hardness Results for Massively Parallel Computation from
Distributed Lower Bounds
IEEE Symposium on Foundations of Computer Science (FOCS) 2019.
Mohsen Ghaffari and Julian Portmann
Improved Network Decompositions using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond
International Symposium on DIStributed Computing (DISC) 2019.
Ruben Becker, Yuval Emek, Mohsen Ghaffari, and Christoph Lenzen
Distributed Algorithms for Low Stretch Spanning Trees
International Symposium on DIStributed Computing (DISC) 2019.
Yi-Jun Chang,
Manuela Fischer,
Mohsen Ghaffari,
Jara Uitto, and
Yufan Zheng
The Complexity of (Delta + 1) Coloring in Congested Clique, Massively
Parallel Computation, and Centralized Local Computation
ACM Symposium on Principles of Distributed Computing (PODC) 2019.
Best Student Paper Award at PODC'19.
[arXiv]
Mohsen Ghaffari and Fabian Kuhn
On the Use of Randomness in Local Distributed Graph Algorithms
ACM Symposium on Principles of Distributed Computing (PODC) 2019.
Michal Dory and Mohsen Ghaffari
Improved Distributed Approximations for Minimum-Weight
Two-Edge-Connected Spanning Subgraph
ACM Symposium on Principles of Distributed Computing (PODC) 2019.
Philipp Bamberger,
Mohsen Ghaffari,
Fabian Kuhn,
Yannic Maus, and
Jara Uitto
On the Complexity of Distributed Splitting Problems
ACM Symposium on Principles of Distributed Computing (PODC) 2019.
Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrovic
Improved Parallel Algorithms for Density-Based Network Clustering
International Conference on Machine Learning (ICML) 2019.
Mohsen Ghaffari and Ali Sayyadi
Distributed Arboricity-Dependent Graph Coloring via All-to-All Communication
International Colloquium on Automata, Languages and Programming (ICALP) 2019.
Mohsen Ghaffari and
Jara Uitto
Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2019.
[arXiv]
Mohsen Ghaffari
Distributed Maximal Independent Set using Small Messages
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2019.
Mohsen Ghaffari and
David Wajc
Simplified and Space-Optimal Semi-Streaming for (2+epsilon)-Approximate Matching
Symposium on Simplicity in Algorithms (SOSA) 2019.
[arXiv]
Mohsen Ghaffari,
David Harris, and
Fabian Kuhn
On Derandomizing Local Distributed Algorithms
IEEE Symposium on Foundations of Computer Science (FOCS) 2018.
[arXiv]
Mohsen Ghaffari and Fabian Kuhn
Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set
International Symposium on DIStributed Computing (DISC) 2018.
Mohsen Ghaffari and Fabian Kuhn
Distributed MST and Broadcast with Fewer Messages, and Faster Gossiping
International Symposium on DIStributed Computing (DISC) 2018.
Manuela Fischer
and Mohsen Ghaffari
A Simple Parallel and Distributed Sampling Technique: Local Glauber Dynamics
International Symposium on DIStributed Computing (DISC) 2018.
Mohsen Ghaffari and Jason Li
New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms
International Symposium on DIStributed Computing (DISC) 2018.
[arXiv]
Guy Even, Mohsen Ghaffari, and Moti Medina
Distributed Set Cover Approximation: Primal-Dual with Optimal Locality
International Symposium on DIStributed Computing (DISC) 2018.
Mohsen Ghaffari,
Themis Gouleakis,
Christian Konrad,
Slobodan Mitrovic, and Ronitt Rubinfeld
Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
ACM Symposium on Principles of Distributed Computing (PODC) 2018.
[arXiv]
Mohsen Ghaffari and Johannes Lengler
Nearly-Tight Analysis for 2-Choice and 3-Majority Consensus Dynamics
ACM Symposium on Principles of Distributed Computing (PODC) 2018.
Mohsen Ghaffari and Krzysztof Nowicki
Congested Clique Algorithms for the Minimum Cut Problem
ACM Symposium on Principles of Distributed Computing (PODC) 2018.
Mohsen Ghaffari,
Juho Hirvonen,
Fabian Kuhn, and
Yannic Maus
Improved Distributed Delta-Coloring
ACM Symposium on Principles of Distributed Computing (PODC) 2018.
Mohsen Ghaffari,
Fabian Kuhn,
Yannic Maus, and
Jara Uitto
Deterministic Distributed Edge-Coloring with Fewer Colors
ACM Symposium on Theory of Computing (STOC) 2018.
[arXiv]
Mohsen Ghaffari, and Jason Li
Improved Distributed Algorithms for Exact Shortest Paths
ACM Symposium on Theory of Computing (STOC) 2018.
[arXiv]
Manuela Fischer,
Mohsen Ghaffari, and Fabian Kuhn
Deterministic Distributed Edge Coloring via Hypergraph Maximal Matching
IEEE Symposium on Foundations of Computer Science (FOCS) 2017.
Invited to the SIAM Journal of Computing (SICOMP) Special Issue for FOCS'17.
[arXiv]
Manuela Fischer and
Mohsen Ghaffari
Sublogarithmic Distributed Algorithms for Lovász Local Lemma, and the Complexity Hierarchy
International Symposium on DIStributed Computing (DISC) 2017.
[arXiv]
Mohsen Ghaffari and Christiana Lymouri
Simple and Near-Optimal Distributed Coloring for Sparse Graphs
International Symposium on DIStributed Computing (DISC) 2017.
[arXiv]
Mohsen Ghaffari and Merav Parter
Near-Optimal 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.
[arXiv]
Mohsen Ghaffari,
Distributed MIS via All-to-All Communication
ACM Symposium on Principles of Distributed Computing (PODC) 2017.
Mohsen Ghaffari, Fabian Kuhn, and Hsin-Hao Su,
Distributed MST and Routing in Almost Mixing Time
ACM Symposium on Principles of Distributed Computing (PODC) 2017.
Reuven Bar-Yehuda, 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.
[arXiv]
Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus,
On the Complexity of Local Distributed Graph Problems
ACM Symposium on Theory of Computing (STOC) 2017.
[arXiv]
[A TCS+ talk on youtube]
Mohsen Ghaffari and Hsin-Hao Su,
Distributed Degree Splitting, Edge Coloring, and Orientations
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2017.
[arXiv]
Mohsen Ghaffari, David Karger, and Debmalya Panigrahi,
Random Contractions and Sampling for Hypergraph and Hedge Connectivity.
ACM-SIAM 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 Log-Star 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,
Near-Optimal Distributed Algorithms for Fault-Tolerant 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
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016.
Best Paper Award 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: Low-Congestion Shortcuts, MST, and Min-Cut
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016.
Mohsen Ghaffari,
Near-Optimal Scheduling of Distributed Algorithms
ACM Symposium on Principles of Distributed Computing (PODC) 2015.
Best Student Paper Award at PODC'15.
Invited to the Journal of ACM (JACM) Special Issue for PODC'15.
Mohsen Ghaffari,
Andreas Karrenbauer,
Fabian Kuhn,
Christoph Lenzen, and
Boaz Patt-Shamir,
Near-Optimal Distributed Maximum Flow
ACM Symposium on Principles of Distributed Computing (PODC) 2015.
Mohsen Ghaffari,
Cameron Musco, Tsvetomira Radeva, and Nancy Lynch,
Distributed House-Hunting 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.
Keren Censor Hillel, Mohsen Ghaffari,
George Giakkoupis,
Bernhard Haeupler, and
Fabian Kuhn,
Tight Bounds on Vertex Connectivity under Vertex Sampling
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2015.
Invited to the Transactions of Algorithms Special Issue for SODA 2015
[Abstract]
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$-vertex-connected 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 Censor-Hillel et al. [SODA 2014].
Mohsen Ghaffari and
Christoph Lenzen,
Near-Optimal 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 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)$, 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.
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 read-write 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 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.
Mohsen Ghaffari,
Erez Kantor,
Nancy Lynch, and
Calvin Newport,
Multi-Message Broadcast with Abstract MAC Layers and Unreliable Links
ACM Symposium on Principles of Distributed Computing (PODC) 2014.
[Abstract]
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.
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.
Invited to the Journal of ACM (JACM) Special Issue for PODC'14.
[Abstract]
[PDF]
[arXiv]
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})$, 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)$, 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.
Mohsen Ghaffari,
Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating Set
International Colloquium on Automata, Languages, and Programming (ICALP) 2014.
Best Student Paper Award at ICALP'14.
[Abstract]
[PDF]
[arXiv]
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].
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 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 )$, 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$, 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$, 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)$, improving the (previously best-known) trivial throughput of $\Theta(1)$.
Noga Alon, Mohsen Ghaffari,
Bernhard Haeupler, and
Majid Khabbazian,
Broadcast Throughput in Radio Networks: Routing vs. Network Coding
ACM-SIAM 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 worst-case broadcast throughput over all networks with $n$ nodes is $\Theta(1 / \log n)$ messages-per-round 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 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})$.
Mohsen Ghaffari and
Bernhard Haeupler,
Fast Structuring of Radio Networks for Multi-Message 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 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.
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 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.
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 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.
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 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-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.
Mohsen Ghaffari and
Bernhard Haeupler,
Near-Optimal Leader Election in Multi-Hop Radio Networks
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2013.
[Abstract]
[PDF]
[arXiv]
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.
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 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.
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 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.
|
