Search Results

Documents authored by Ghaffari, Mohsen

Document
DOI: 10.4230/LIPIcs.DISC.2020.34
Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond

Authors: Mohsen Ghaffari, Christoph Grunau, and Ce Jin

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
We present O(log log n) round scalable Massively Parallel Computation algorithms for maximal independent set and maximal matching, in trees and more generally graphs of bounded arboricity, as well as for coloring trees with a constant number of colors. Following the standards, by a scalable MPC algorithm, we mean that these algorithms can work on machines that have capacity/memory as small as n^{δ} for any positive constant δ < 1. Our results improve over the O(log²log n) round algorithms of Behnezhad et al. [PODC'19]. Moreover, our matching algorithm is presumably optimal as its bound matches an Ω(log log n) conditional lower bound of Ghaffari, Kuhn, and Uitto [FOCS'19].
Cite as

Mohsen Ghaffari, Christoph Grunau, and Ce Jin. Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 34:1-34:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ghaffari_et_al:LIPIcs.DISC.2020.34,
  author =	{Ghaffari, Mohsen and Grunau, Christoph and Jin, Ce},
  title =	{{Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{34:1--34:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.34},
  URN =		{urn:nbn:de:0030-drops-131128},
  doi =		{10.4230/LIPIcs.DISC.2020.34},
  annote =	{Keywords: Massively Parallel Computation, MIS, Matching, Coloring}
}
Document
DOI: 10.4230/LIPIcs.DISC.2019.4
Distributed Algorithms for Low Stretch Spanning Trees

Authors: Ruben Becker, Yuval Emek, Mohsen Ghaffari, and Christoph Lenzen

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
Given an undirected graph with integer edge lengths, we study the problem of approximating the distances in the graph by a spanning tree based on the notion of stretch. Our main contribution is a distributed algorithm in the CONGEST model of computation that constructs a random spanning tree with the guarantee that the expected stretch of every edge is O(log^{3} n), where n is the number of nodes in the graph. If the graph is unweighted, then this algorithm can be implemented to run in O(D) rounds, where D is the hop-diameter of the graph, thus being asymptotically optimal. In the weighted case, the run-time of our algorithm matches the currently best known bound for exact distance computations, i.e., O~ (min{sqrt{n D}, sqrt{n} D^{1 / 4} + n^{3 / 5} + D}). We stress that this is the first distributed construction of spanning trees leading to poly-logarithmic expected stretch with non-trivial running time.
Cite as

Ruben Becker, Yuval Emek, Mohsen Ghaffari, and Christoph Lenzen. Distributed Algorithms for Low Stretch Spanning Trees. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.DISC.2019.4,
  author =	{Becker, Ruben and Emek, Yuval and Ghaffari, Mohsen and Lenzen, Christoph},
  title =	{{Distributed Algorithms for Low Stretch Spanning Trees}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.4},
  URN =		{urn:nbn:de:0030-drops-113116},
  doi =		{10.4230/LIPIcs.DISC.2019.4},
  annote =	{Keywords: distributed graph algorithms, low-stretch spanning trees, CONGEST model, ball decomposition, star decomposition}
}
Document
DOI: 10.4230/LIPIcs.DISC.2019.18
Improved Network Decompositions Using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond

Authors: Mohsen Ghaffari and Julian Portmann

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
Network decompositions, as introduced by Awerbuch, Luby, Goldberg, and Plotkin [FOCS'89], are one of the key algorithmic tools in distributed graph algorithms. We present an improved deterministic distributed algorithm for constructing network decompositions of power graphs using small messages, which improves upon the algorithm of Ghaffari and Kuhn [DISC'18]. In addition, we provide a randomized distributed network decomposition algorithm, based on our deterministic algorithm, with failure probability exponentially small in the input size that works with small messages as well. Compared to the previous algorithm of Elkin and Neiman [PODC'16], our algorithm achieves a better success probability at the expense of its round complexity, while giving a network decomposition of the same quality. As a consequence of the randomized algorithm for network decomposition, we get a faster randomized algorithm for computing a Maximal Independent Set, improving on a result of Ghaffari [SODA'19]. Other implications of our improved deterministic network decomposition algorithm are: a faster deterministic distributed algorithms for constructing spanners and approximations of distributed set cover, improving results of Ghaffari, and Kuhn [DISC'18] and Deurer, Kuhn, and Maus [PODC'19]; and faster a deterministic distributed algorithm for constructing neighborhood covers, resolving an open question of Elkin [SODA'04].
Cite as

Mohsen Ghaffari and Julian Portmann. Improved Network Decompositions Using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ghaffari_et_al:LIPIcs.DISC.2019.18,
  author =	{Ghaffari, Mohsen and Portmann, Julian},
  title =	{{Improved Network Decompositions Using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.18},
  URN =		{urn:nbn:de:0030-drops-113259},
  doi =		{10.4230/LIPIcs.DISC.2019.18},
  annote =	{Keywords: Distributed Graph Algorithms, Network Decomposition, Maximal Independent Set, Neighborhood Cover}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.142
Distributed Arboricity-Dependent Graph Coloring via All-to-All Communication

Authors: Mohsen Ghaffari and Ali Sayyadi

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We present a constant-time randomized distributed algorithms in the congested clique model that computes an O(alpha)-vertex-coloring, with high probability. Here, alpha denotes the arboricity of the graph, which is, roughly speaking, the edge-density of the densest subgraph. Congested clique is a well-studied model of synchronous message passing for distributed computing with all-to-all communication: per round each node can send one O(log n)-bit message algorithm to each other node. Our O(1)-round algorithm settles the randomized round complexity of the O(alpha)-coloring problem. We also explain that a similar method can provide a constant-time randomized algorithm for decomposing the graph into O(alpha) edge-disjoint forests, so long as alpha <= n^{1-o(1)}.
Cite as

Mohsen Ghaffari and Ali Sayyadi. Distributed Arboricity-Dependent Graph Coloring via All-to-All Communication. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 142:1-142:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ghaffari_et_al:LIPIcs.ICALP.2019.142,
  author =	{Ghaffari, Mohsen and Sayyadi, Ali},
  title =	{{Distributed Arboricity-Dependent Graph Coloring via All-to-All Communication}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{142:1--142:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.142},
  URN =		{urn:nbn:de:0030-drops-107187},
  doi =		{10.4230/LIPIcs.ICALP.2019.142},
  annote =	{Keywords: Distributed Computing, Message Passing Algorithms, Graph Coloring, Arboricity, Congested Clique Model, Randomized Algorithms}
}
Document
DOI: 10.4230/OASIcs.SOSA.2019.13
Simplified and Space-Optimal Semi-Streaming (2+epsilon)-Approximate Matching

Authors: Mohsen Ghaffari and David Wajc

Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)

Abstract
In a recent breakthrough, Paz and Schwartzman (SODA'17) presented a single-pass (2+epsilon)-approximation algorithm for the maximum weight matching problem in the semi-streaming model. Their algorithm uses O(n log^2 n) bits of space, for any constant epsilon>0. We present a simplified and more intuitive primal-dual analysis, for essentially the same algorithm, which also improves the space complexity to the optimal bound of O(n log n) bits - this is optimal as the output matching requires Omega(n log n) bits.
Cite as

Mohsen Ghaffari and David Wajc. Simplified and Space-Optimal Semi-Streaming (2+epsilon)-Approximate Matching. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 13:1-13:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ghaffari_et_al:OASIcs.SOSA.2019.13,
  author =	{Ghaffari, Mohsen and Wajc, David},
  title =	{{Simplified and Space-Optimal Semi-Streaming (2+epsilon)-Approximate Matching}},
  booktitle =	{2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
  pages =	{13:1--13:8},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-099-6},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{69},
  editor =	{Fineman, Jeremy T. and Mitzenmacher, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.13},
  URN =		{urn:nbn:de:0030-drops-100396},
  doi =		{10.4230/OASIcs.SOSA.2019.13},
  annote =	{Keywords: Streaming, Semi-Streaming, Space-Optimal, Matching}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.22
Distributed Set Cover Approximation: Primal-Dual with Optimal Locality

Authors: Guy Even, Mohsen Ghaffari, and Moti Medina

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
This paper presents a deterministic distributed algorithm for computing an f(1+epsilon) approximation of the well-studied minimum set cover problem, for any constant epsilon>0, in O(log (f Delta)/log log (f Delta)) rounds. Here, f denotes the maximum element frequency and Delta denotes the cardinality of the largest set. This f(1+epsilon) approximation almost matches the f-approximation guarantee of standard centralized primal-dual algorithms, which is known to be essentially the best possible approximation for polynomial-time computations. The round complexity almost matches the Omega(log (Delta)/log log (Delta)) lower bound of Kuhn, Moscibroda, Wattenhofer [JACM'16], which holds for even f=2 and for any poly(log Delta) approximation. Our algorithm also gives an alternative way to reproduce the time-optimal 2(1+epsilon)-approximation of vertex cover, with round complexity O(log Delta/log log Delta), as presented by Bar-Yehuda, Censor-Hillel, and Schwartzman [PODC'17] for weighted vertex cover. Our method is quite different and it can be viewed as a locality-optimal way of performing primal-dual for the more general case of set cover. We note that the vertex cover algorithm of Bar-Yehuda et al. does not extend to set cover (when f >= 3).
Cite as

Guy Even, Mohsen Ghaffari, and Moti Medina. Distributed Set Cover Approximation: Primal-Dual with Optimal Locality. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{even_et_al:LIPIcs.DISC.2018.22,
  author =	{Even, Guy and Ghaffari, Mohsen and Medina, Moti},
  title =	{{Distributed Set Cover Approximation: Primal-Dual with Optimal Locality}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.22},
  URN =		{urn:nbn:de:0030-drops-98114},
  doi =		{10.4230/LIPIcs.DISC.2018.22},
  annote =	{Keywords: Distributed Algorithms, Approximation Algorithms, Set Cover, Vertex Cover}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.26
A Simple Parallel and Distributed Sampling Technique: Local Glauber Dynamics

Authors: Manuela Fischer and Mohsen Ghaffari

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
Sampling constitutes an important tool in a variety of areas: from machine learning and combinatorial optimization to computational physics and biology. A central class of sampling algorithms is the Markov Chain Monte Carlo method, based on the construction of a Markov chain with the desired sampling distribution as its stationary distribution. Many of the traditional Markov chains, such as the Glauber dynamics, do not scale well with increasing dimension. To address this shortcoming, we propose a simple local update rule based on the Glauber dynamics that leads to efficient parallel and distributed algorithms for sampling from Gibbs distributions. Concretely, we present a Markov chain that mixes in O(log n) rounds when Dobrushin's condition for the Gibbs distribution is satisfied. This improves over the LubyGlauber algorithm by Feng, Sun, and Yin [PODC'17], which needs O(Delta log n) rounds, and their LocalMetropolis algorithm, which converges in O(log n) rounds but requires a considerably stronger mixing condition. Here, n denotes the number of nodes in the graphical model inducing the Gibbs distribution, and Delta its maximum degree. In particular, our method can sample a uniform proper coloring with alpha Delta colors in O(log n) rounds for any alpha >2, which almost matches the threshold of the sequential Glauber dynamics and improves on the alpha>2 + sqrt{2} threshold of Feng et al.
Cite as

Manuela Fischer and Mohsen Ghaffari. A Simple Parallel and Distributed Sampling Technique: Local Glauber Dynamics. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 26:1-26:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.DISC.2018.26,
  author =	{Fischer, Manuela and Ghaffari, Mohsen},
  title =	{{A Simple Parallel and Distributed Sampling Technique: Local Glauber Dynamics}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{26:1--26:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.26},
  URN =		{urn:nbn:de:0030-drops-98154},
  doi =		{10.4230/LIPIcs.DISC.2018.26},
  annote =	{Keywords: Distributed Graph Algorithms, Parallel Algorithms, Local Algorithms, Locality, Sampling, Glauber Dynamics, Coloring}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.29
Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set

Authors: Mohsen Ghaffari and Fabian Kuhn

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
This paper presents improved deterministic distributed algorithms, with O(log n)-bit messages, for some basic graph problems. The common ingredient in our results is a deterministic distributed algorithm for computing a certain hitting set, which can replace the random part of a number of standard randomized distributed algorithms. This deterministic hitting set algorithm itself is derived using a simple method of conditional expectations. As one main end-result of this derandomized hitting set, we get a deterministic distributed algorithm with round complexity 2^O(sqrt{log n * log log n}) for computing a (2k-1)-spanner of size O~(n^{1+1/k}). This improves considerably on a recent algorithm of Grossman and Parter [DISC'17] which needs O(n^{1/2-1/k} * 2^k) rounds. We also get a 2^O(sqrt{log n * log log n})-round deterministic distributed algorithm for computing an O(log^2 n)-approximation of minimum dominating set; all prior algorithms for this problem were either randomized or required large messages.
Cite as

Mohsen Ghaffari and Fabian Kuhn. Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ghaffari_et_al:LIPIcs.DISC.2018.29,
  author =	{Ghaffari, Mohsen and Kuhn, Fabian},
  title =	{{Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{29:1--29:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.29},
  URN =		{urn:nbn:de:0030-drops-98181},
  doi =		{10.4230/LIPIcs.DISC.2018.29},
  annote =	{Keywords: Distributed Algorithms, Derandomization, Spanners, Dominating Set}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.30
Distributed MST and Broadcast with Fewer Messages, and Faster Gossiping

Authors: Mohsen Ghaffari and Fabian Kuhn

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
We present a distributed minimum spanning tree algorithm with near-optimal round complexity of O~(D+sqrt{n}) and message complexity O~(min{n^{3/2}, m}). This is the first algorithm with sublinear message complexity and near-optimal round complexity and it improves over the recent algorithms of Elkin [PODC'17] and Pandurangan et al. [STOC'17], which have the same round complexity but message complexity O~(m). Our method also gives the first broadcast algorithm with o(n) time complexity - when that is possible at all, i.e., when D=o(n) - and o(m) messages. Moreover, our method leads to an O~(sqrt{nD})-round GOSSIP algorithm with bounded-size messages. This is the first such algorithm with a sublinear round complexity.
Cite as

Mohsen Ghaffari and Fabian Kuhn. Distributed MST and Broadcast with Fewer Messages, and Faster Gossiping. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 30:1-30:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ghaffari_et_al:LIPIcs.DISC.2018.30,
  author =	{Ghaffari, Mohsen and Kuhn, Fabian},
  title =	{{Distributed MST and Broadcast with Fewer Messages, and Faster Gossiping}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{30:1--30:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.30},
  URN =		{urn:nbn:de:0030-drops-98194},
  doi =		{10.4230/LIPIcs.DISC.2018.30},
  annote =	{Keywords: Distributed Algorithms, Minimum Spanning Tree, Round Complexity, Message Complexity, Gossiping, Broadcast}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.31
New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms

Authors: Mohsen Ghaffari and Jason Li

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
We show that many classical optimization problems - such as (1 +/- epsilon)-approximate maximum flow, shortest path, and transshipment - can be computed in tau_{mix}(G)* n^o(1) rounds of distributed message passing, where tau_{mix}(G) is the mixing time of the network graph G. This extends the result of Ghaffari et al. [PODC'17], whose main result is a distributed MST algorithm in tau_{mix}(G)* 2^O(sqrt{log n log log n}) rounds in the CONGEST model, to a much wider class of optimization problems. For many practical networks of interest, e.g., peer-to-peer or overlay network structures, the mixing time tau_{mix}(G) is small, e.g., polylogarithmic. On these networks, our algorithms bypass the Omega(sqrt n+D) lower bound of Das Sarma et al. [STOC'11], which applies for worst-case graphs and applies to all of the above optimization problems. For all of the problems except MST, this is the first distributed algorithm which takes o(sqrt n) rounds on a (nontrivial) restricted class of network graphs. Towards deriving these improved distributed algorithms, our main contribution is a general transformation that simulates any work-efficient PRAM algorithm running in T parallel rounds via a distributed algorithm running in T * tau_{mix}(G)* 2^O(sqrt{log n}) rounds. Work- and time-efficient parallel algorithms for all of the aforementioned problems follow by combining the work of Sherman [FOCS'13, SODA'17] and Peng and Spielman [STOC'14]. Thus, simulating these parallel algorithms using our transformation framework produces the desired distributed algorithms. The core technical component of our transformation is the algorithmic problem of solving multi-commodity routing - that is, roughly, routing n packets each from a given source to a given destination - in random graphs. For this problem, we obtain a new algorithm running in 2^O(sqrt{log n}) rounds, improving on the 2^O(sqrt{log n log log n}) round algorithm of Ghaffari, Kuhn, and Su [PODC'17]. As a consequence, for the MST problem in particular, we obtain an improved distributed algorithm running in tau_{mix}(G)* 2^O(sqrt{log n}) rounds.
Cite as

Mohsen Ghaffari and Jason Li. New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ghaffari_et_al:LIPIcs.DISC.2018.31,
  author =	{Ghaffari, Mohsen and Li, Jason},
  title =	{{New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.31},
  URN =		{urn:nbn:de:0030-drops-98207},
  doi =		{10.4230/LIPIcs.DISC.2018.31},
  annote =	{Keywords: Distributed Graph Algorithms, Mixing Time, Random Graphs, Multi-Commodity Routing}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.28
A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors

Authors: Andrea Clementi, Mohsen Ghaffari, Luciano Gualà, Emanuele Natale, Francesco Pasquale, and Giacomo Scornavacca

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
The Undecided-State Dynamics is a well-known protocol for distributed consensus. We analyze it in the parallel PULL communication model on the complete graph with n nodes for the binary case (every node can either support one of two possible colors, or be in the undecided state). An interesting open question is whether this dynamics is an efficient Self-Stabilizing protocol, namely, starting from an arbitrary initial configuration, it reaches consensus quickly (i.e., within a polylogarithmic number of rounds). Previous work in this setting only considers initial color configurations with no undecided nodes and a large bias (i.e., Theta(n)) towards the majority color. In this paper we present an unconditional analysis of the Undecided-State Dynamics that answers to the above question in the affirmative. We prove that, starting from any initial configuration, the process reaches a monochromatic configuration within O(log n) rounds, with high probability. This bound turns out to be tight. Our analysis also shows that, if the initial configuration has bias Omega(sqrt(n log n)), then the dynamics converges toward the initial majority color, with high probability.
Cite as

Andrea Clementi, Mohsen Ghaffari, Luciano Gualà, Emanuele Natale, Francesco Pasquale, and Giacomo Scornavacca. A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{clementi_et_al:LIPIcs.MFCS.2018.28,
  author =	{Clementi, Andrea and Ghaffari, Mohsen and Gual\`{a}, Luciano and Natale, Emanuele and Pasquale, Francesco and Scornavacca, Giacomo},
  title =	{{A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{28:1--28:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.28},
  URN =		{urn:nbn:de:0030-drops-96107},
  doi =		{10.4230/LIPIcs.MFCS.2018.28},
  annote =	{Keywords: Distributed Consensus, Self-Stabilization, PULL Model, Markov Chains}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.18
Sublogarithmic Distributed Algorithms for Lovász Local Lemma, and the Complexity Hierarchy

Authors: Manuela Fischer and Mohsen Ghaffari

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
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 Lovasz 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 (on bounded degree graphs). 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 vertex-coloring.
Cite as

Manuela Fischer and Mohsen Ghaffari. Sublogarithmic Distributed Algorithms for Lovász Local Lemma, and the Complexity Hierarchy. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.DISC.2017.18,
  author =	{Fischer, Manuela and Ghaffari, Mohsen},
  title =	{{Sublogarithmic Distributed Algorithms for Lov\'{a}sz Local Lemma, and the Complexity Hierarchy}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.18},
  URN =		{urn:nbn:de:0030-drops-79732},
  doi =		{10.4230/LIPIcs.DISC.2017.18},
  annote =	{Keywords: Distributed Graph Algorithms, the Lov'\{a\}sz Local Lemma (LLL), Locally Checkable Labeling problems (LCL), Defective Coloring, Frugal Coloring, List Ve}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.19
Improved Distributed Degree Splitting and Edge Coloring

Authors: Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, and Jara Uitto

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
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-edge-coloring, improving on that of Ghaffari and Su.
Cite as

Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, and Jara Uitto. Improved Distributed Degree Splitting and Edge Coloring. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{ghaffari_et_al:LIPIcs.DISC.2017.19,
  author =	{Ghaffari, Mohsen and Hirvonen, Juho and Kuhn, Fabian and Maus, Yannic and Suomela, Jukka and Uitto, Jara},
  title =	{{Improved Distributed Degree Splitting and Edge Coloring}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{19:1--19:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.19},
  URN =		{urn:nbn:de:0030-drops-79794},
  doi =		{10.4230/LIPIcs.DISC.2017.19},
  annote =	{Keywords: Distributed Graph Algorithms, Degree Splitting, Edge Coloring, Discrepancy}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.20
Simple and Near-Optimal Distributed Coloring for Sparse Graphs

Authors: Mohsen Ghaffari and Christiana Lymouri

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
Graph coloring is one of the central problems in distributed graph algorithms. Much of the research on this topic has focused on coloring with Delta+1 colors, where Delta denotes the maximum degree. Using Delta+1 colors may be unsatisfactory in sparse graphs, where not all nodes have such a high degree; it would be more desirable to use a number of colors that improves with sparsity. A standard measure that captures sparsity is arboricity, which is the smallest number of forests into which the edges of the graph can be partitioned. We present simple randomized distributed algorithms that, with high probability, color any n-node alpha-arboricity graph: - using (2+epsilon)alpha colors, for constant epsilon>0, in O(log n) rounds, if alpha=Omega(log n log log n), or - using O(alpha log alpha) colors, in O(log n) rounds, or - using O(alpha) colors, in O(log n min{log log n, log alpha}) rounds. These algorithms are nearly-optimal, as it is known by results of Linial [FOCS'87] and Barenboim and Elkin [PODC'08] that coloring with Theta(alpha) colors, or even poly(alpha) colors, requires Omega(log_alpha n) rounds. The previously best-known O(log n)-time result was a deterministic algorithm due to Barenboim and Elkin [PODC'08], which uses Theta(alpha^2) colors. Barenboim and Elkin stated improving this number of colors as an open problem in their Distributed Graph Coloring Book.
Cite as

Mohsen Ghaffari and Christiana Lymouri. Simple and Near-Optimal Distributed Coloring for Sparse Graphs. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{ghaffari_et_al:LIPIcs.DISC.2017.20,
  author =	{Ghaffari, Mohsen and Lymouri, Christiana},
  title =	{{Simple and Near-Optimal Distributed Coloring for Sparse Graphs}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.20},
  URN =		{urn:nbn:de:0030-drops-80178},
  doi =		{10.4230/LIPIcs.DISC.2017.20},
  annote =	{Keywords: Distributed Graph Algorithms, Graph Coloring, Arboricity}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.21
Near-Optimal Distributed DFS in Planar Graphs

Authors: Mohsen Ghaffari and Merav Parter

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
We present a randomized distributed algorithm that computes a Depth-First Search (DFS) tree in ~O(D) rounds, in any planar network G=(V,E) with diameter D, with high probability. This is the first sublinear-time distributed DFS algorithm, improving on a three decades-old O(n) algorithm of Awerbuch (1985), which remains the best known for general graphs. Furthermore, this ~O(D) round complexity is nearly-optimal as Omega(D) is a trivial lower bound. A key technical ingredient in our results is the development of a distributed method for (recursively) computing a separator path, which is a path whose removal from the graph leaves connected components that are all a constant factor smaller. We believe that the general method we develop for computing path separators recursively might be of broader interest, and may provide the first step towards solving many other problems.
Cite as

Mohsen Ghaffari and Merav Parter. Near-Optimal Distributed DFS in Planar Graphs. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{ghaffari_et_al:LIPIcs.DISC.2017.21,
  author =	{Ghaffari, Mohsen and Parter, Merav},
  title =	{{Near-Optimal Distributed DFS in Planar Graphs}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{21:1--21:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.21},
  URN =		{urn:nbn:de:0030-drops-80195},
  doi =		{10.4230/LIPIcs.DISC.2017.21},
  annote =	{Keywords: congest model, planar graphs, separator}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.138
Leader Election in Unreliable Radio Networks

Authors: Mohsen Ghaffari and Calvin Newport

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
The dual graph model describes a radio network that contains both reliable and unreliable links. In recent years, this model has received significant attention by the distributed algorithms community [Kuhn/Lynch/Newport/Oshman/Richa, PODC 2010; Censor-Hillel/Gilbert/Kuhn/Lynch/Newport, Dist. Comp. 2014; Ghaffari/Haeupler/Lynch/Newport, DISC 2012; Ghaffari/Lynch/Newport, PODC 2013; Ghaffir/Kantor/Lynch/Newport, PODC 2014; Newport, DISC 2014; Ahmadi/Ghodselahi/Kuhn/Molla, OPODIS 2015; Lynch/Newport, PODC 2015]. Due to results in [Ghaffari/Lynch/Newport, PODC 2013], it is known that leader election plays a key role in enabling efficient computation in this difficult setting: a leader can synchronize the network in such a manner that most problems can be subsequently solved in time similar to the classical radio network model that lacks unreliable links. The feasibility of efficient leader election in the dual graph model, however, was left as an important open question. In this paper, we answer this question. In more detail, we prove new upper and lower bound results that characterize the complexity of leader election in this setting. By doing so, we reveal a surprising dichotomy: (1) under the assumption that the network size n is in the range 1 to N, where N is a large upper bound on the maximum possible network size (e.g., the ID space), leader election is fundamentally hard, requiring ~Omega(sqrt(N)) rounds to solve in the worst-case; (2) under the assumption that n is in the range 2 to N, however, the problem can be solved in only ~O(D) rounds, for network diameter D, matching the lower bound for leader election in the standard radio network model (within log factors) [Ghaffari/Haeupler, SODA 2013].
Cite as

Mohsen Ghaffari and Calvin Newport. Leader Election in Unreliable Radio Networks. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 138:1-138:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{ghaffari_et_al:LIPIcs.ICALP.2016.138,
  author =	{Ghaffari, Mohsen and Newport, Calvin},
  title =	{{Leader Election in Unreliable Radio Networks}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{138:1--138:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.138},
  URN =		{urn:nbn:de:0030-drops-62823},
  doi =		{10.4230/LIPIcs.ICALP.2016.138},
  annote =	{Keywords: Radio Networks, Leader Election, Unreliability, Randomized Algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact