7 Search Results for "Coy, Sam"

Document
DOI: 10.4230/LIPIcs.OPODIS.2025.10
Computing in a Faulty Congested Clique

Authors: Keren Censor-Hillel and Pedro Soto

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
We study a Faulty Congested Clique model, in which an adversary may fail nodes in the network throughout the computation. We show that any task of O(nlog{n})-bit input per node can be solved in roughly n rounds, where n is the size of the network. This nearly matches the linear upper bound on the complexity of the non-faulty Congested Clique model for such problems, by learning the entire input, and it holds in the faulty model even with a linear number of faults. Our main contribution is that we establish that one can do much better by looking more closely at the computation. Given a deterministic algorithm 𝒜 for the non-faulty Congested Clique model, we show how to transform it into an algorithm 𝒜' for the faulty model, with an overhead that could be as small as some logarithmic-in-n factor, by considering refined complexity measures of 𝒜. As an exemplifying application of our approach, we show that the O(n^{1/3})-round complexity of semi-ring matrix multiplication [Censor{-}Hillel, Kaski, Korhonen, Lenzen, Paz, Suomela, PODC 2015] remains the same up to polylog factors in the faulty model, even if the adversary can fail 99% of the nodes (or any other constant fraction).
Cite as

Keren Censor-Hillel and Pedro Soto. Computing in a Faulty Congested Clique. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.OPODIS.2025.10,
  author =	{Censor-Hillel, Keren and Soto, Pedro},
  title =	{{Computing in a Faulty Congested Clique}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.10},
  URN =		{urn:nbn:de:0030-drops-251833},
  doi =		{10.4230/LIPIcs.OPODIS.2025.10},
  annote =	{Keywords: distributed computing, graph algorithms, computing with faults}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.20
Two for One, One for All: Deterministic LDC-Based Robust Computation in Congested Clique

Authors: Keren Censor-Hillel, Orr Fischer, Ran Gelles, and Pedro Soto

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We design a deterministic compiler that makes any computation in the Congested Clique model robust to a constant fraction α < 1 of adversarial crash faults. In particular, we show how a network of n nodes can compute any circuit of depth d, width ω, and gate total fan Δ, in d ⋅ ⌈ω/n² + Δ/n⌉ ⋅ 2^{O(√{log{n}}log log{n})} rounds in such a faulty model. As a corollary, any T-round Congested Clique algorithm can be compiled into an algorithm that completes in T² n^{o(1)} rounds in this model. Our compiler obtains resilience to node crashes by coding information across the network, and its main underlying observation is that we can leverage locally-decodable codes (LDCs) to maintain a low complexity overhead, as these allow recovering the information needed at each computational step by querying only small parts of the codeword, instead of retrieving the entire coded message, which is inherent when using block codes. The main technical contribution is that because erasures occur in known locations, which correspond to crashed nodes, we can derandomize classical LDC constructions by deterministically selecting query sets that avoid sufficiently many erasures. Moreover, when decoding multiple codewords in parallel, our derandomization load-balances the queries per-node, thereby preventing congestion and maintaining a low round complexity. Deterministic decoding of LDCs presents a new challenge: the adversary can target precisely the (few) nodes that are queried for decoding a certain codeword. We overcome this issue via an adaptive doubling strategy: if a decoding attempt for a codeword fails, the node doubles the number of its decoding attempts. We employ a similar doubling technique when the adversary crashes the decoding node itself, replacing it dynamically with two other non-crashed nodes. By carefully combining these two doubling processes, we overcome the challenges posed by the combination of a deterministic LDC with a worst case pattern of crashes.
Cite as

Keren Censor-Hillel, Orr Fischer, Ran Gelles, and Pedro Soto. Two for One, One for All: Deterministic LDC-Based Robust Computation in Congested Clique. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.DISC.2025.20,
  author =	{Censor-Hillel, Keren and Fischer, Orr and Gelles, Ran and Soto, Pedro},
  title =	{{Two for One, One for All: Deterministic LDC-Based Robust Computation in Congested Clique}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{20:1--20:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.20},
  URN =		{urn:nbn:de:0030-drops-248379},
  doi =		{10.4230/LIPIcs.DISC.2025.20},
  annote =	{Keywords: Congested Clique, Fault Tolerance, Error Correction Codes}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.64
Fully Scalable MPC Algorithms for Euclidean k-Center

Authors: Artur Czumaj, Guichen Gao, Mohsen Ghaffari, and Shaofeng H.-C. Jiang

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
The k-center problem is a fundamental optimization problem with numerous applications in machine learning, data analysis, data mining, and communication networks. The k-center problem has been extensively studied in the classical sequential setting for several decades, and more recently there have been some efforts in understanding the problem in parallel computing, on the Massively Parallel Computation (MPC) model. For now, we have a good understanding of k-center in the case where each local MPC machine has sufficient local memory to store some representatives from each cluster, that is, when one has Ω(k) local memory per machine. While this setting covers the case of small values of k, for a large number of clusters these algorithms require undesirably large local memory, making them poorly scalable. The case of large k has been considered only recently for the fully scalable low-local-memory MPC model for the Euclidean instances of the k-center problem. However, the earlier works have been considering only the constant dimensional Euclidean space, required a super-constant number of rounds, and produced only k(1+o(1)) centers whose cost is a super-constant approximation of k-center. In this work, we significantly improve upon the earlier results for the k-center problem for the fully scalable low-local-memory MPC model. In the low dimensional Euclidean case in ℝ^d, we present the first constant-round fully scalable MPC algorithm for (2+ε)-approximation. We push the ratio further to (1 + ε)-approximation albeit using slightly more (1 + ε)k centers. All these results naturally extends to slightly super-constant values of d. In the high-dimensional regime, we provide the first fully scalable MPC algorithm that in a constant number of rounds achieves an O(log n/ log log n)-approximation for k-center.
Cite as

Artur Czumaj, Guichen Gao, Mohsen Ghaffari, and Shaofeng H.-C. Jiang. Fully Scalable MPC Algorithms for Euclidean k-Center. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 64:1-64:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{czumaj_et_al:LIPIcs.ICALP.2025.64,
  author =	{Czumaj, Artur and Gao, Guichen and Ghaffari, Mohsen and Jiang, Shaofeng H.-C.},
  title =	{{Fully Scalable MPC Algorithms for Euclidean k-Center}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{64:1--64:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.64},
  URN =		{urn:nbn:de:0030-drops-234416},
  doi =		{10.4230/LIPIcs.ICALP.2025.64},
  annote =	{Keywords: Massively Parallel Computing, Euclidean Spaces, k-Center Clustering}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2025.7
O(1)-Round MPC Algorithms for Multi-Dimensional Grid Graph Connectivity, Euclidean MST and DBSCAN

Authors: Junhao Gan, Anthony Wirth, and Zhuo Zhang

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract
In this paper, we investigate three fundamental problems in the Massively Parallel Computation (MPC) model: (i) grid graph connectivity, (ii) approximate Euclidean Minimum Spanning Tree (EMST), and (iii) approximate DBSCAN. Our first result is a O(1)-round Las Vegas (i.e., succeeding with high probability) MPC algorithm for computing the connected components on a d-dimensional c-penetration grid graph ((d,c)-grid graph), where both d and c are positive integer constants. In such a grid graph, each vertex is a point with integer coordinates in ℕ^d, and an edge can only exist between two distinct vertices with 𝓁_∞-norm at most c. To our knowledge, the current best existing result for computing the connected components (CC’s) on (d,c)-grid graphs in the MPC model is to run the state-of-the-art MPC CC algorithms that are designed for general graphs: they achieve O(log log n + log D) [Behnezhad et al., 2019] and O(log log n + log 1/(λ)) [Sepehr Assadi et al., 2019] rounds, respectively, where D is the diameter and λ is the spectral gap of the graph. With our grid graph connectivity technique, our second main result is a O(1)-round Las Vegas MPC algorithm for computing approximate Euclidean MST. The existing state-of-the-art result on this problem is the O(1)-round MPC algorithm proposed by Andoni et al. [Alexandr Andoni et al., 2014], which only guarantees an approximation on the overall weight in expectation. In contrast, our algorithm not only guarantees a deterministic overall weight approximation, but also achieves a deterministic edge-wise weight approximation. The latter property is crucial to many applications, such as finding the Bichromatic Closest Pair and Single-Linkage Clustering. Last, but not least, our third main result is a O(1)-round Las Vegas MPC algorithm for computing an approximate DBSCAN clustering in O(1)-dimensional Euclidean space.
Cite as

Junhao Gan, Anthony Wirth, and Zhuo Zhang. O(1)-Round MPC Algorithms for Multi-Dimensional Grid Graph Connectivity, Euclidean MST and DBSCAN. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gan_et_al:LIPIcs.ICDT.2025.7,
  author =	{Gan, Junhao and Wirth, Anthony and Zhang, Zhuo},
  title =	{{O(1)-Round MPC Algorithms for Multi-Dimensional Grid Graph Connectivity, Euclidean MST and DBSCAN}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{7:1--7:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.7},
  URN =		{urn:nbn:de:0030-drops-229483},
  doi =		{10.4230/LIPIcs.ICDT.2025.7},
  annote =	{Keywords: Massively Parallel Computation, Graph Connectivity, Grid Graphs, Euclidean Minimum Spanning Tree, DBSCAN}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.45
Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs

Authors: Jinfeng Dou, Thorsten Götte, Henning Hillebrandt, Christian Scheideler, and Julian Werthmann

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We consider the distributed and parallel construction of low-diameter decompositions with strong diameter. We present algorithms for arbitrary undirected, weighted graphs and also for undirected, weighted graphs that can be separated through k ∈ Õ(1) shortest paths. This class of graphs includes planar graphs, graphs of bounded treewidth, and graphs that exclude a fixed minor K_r. Our algorithms work in the PRAM, CONGEST, and the novel HYBRID communication model and are competitive in all relevant parameters. Given 𝒟 > 0, our low-diameter decomposition algorithm divides the graph into connected clusters of strong diameter 𝒟. For an arbitrary graph, an edge e ∈ E of length 𝓁_e is cut between two clusters with probability O(𝓁_e⋅log(n)/𝒟). If the graph can be separated by k ∈ Õ(1) paths, the probability improves to O(𝓁_e⋅log(log n)/𝒟). In either case, the decompositions can be computed in Õ(1) depth and Õ(m) work in the PRAM and Õ(1) time in the HYBRID model. In CONGEST, the runtimes are Õ(HD + √n) and Õ(HD) respectively. All these results hold w.h.p. Broadly speaking, we present distributed and parallel implementations of sequential divide-and-conquer algorithms where we replace exact shortest paths with approximate shortest paths. In contrast to exact paths, these can be efficiently computed in the distributed and parallel setting [STOC '22]. Further, and perhaps more importantly, we show that instead of explicitly computing vertex-separators to enable efficient parallelization of these algorithms, it suffices to sample a few random paths of bounded length and the nodes close to them. Thereby, we do not require complex embeddings whose implementation is unknown in the distributed and parallel setting.
Cite as

Jinfeng Dou, Thorsten Götte, Henning Hillebrandt, Christian Scheideler, and Julian Werthmann. Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 45:1-45:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dou_et_al:LIPIcs.ITCS.2025.45,
  author =	{Dou, Jinfeng and G\"{o}tte, Thorsten and Hillebrandt, Henning and Scheideler, Christian and Werthmann, Julian},
  title =	{{Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{45:1--45:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.45},
  URN =		{urn:nbn:de:0030-drops-226734},
  doi =		{10.4230/LIPIcs.ITCS.2025.45},
  annote =	{Keywords: Distributed Graph Algorithms, Network Decomposition, Excluded Minor}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.46
Optimal (Degree+1)-Coloring in Congested Clique

Authors: Sam Coy, Artur Czumaj, Peter Davies, and Gopinath Mishra

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We consider the distributed complexity of the (degree+1)-list coloring problem, in which each node u of degree d(u) is assigned a palette of d(u)+1 colors, and the goal is to find a proper coloring using these color palettes. The (degree+1)-list coloring problem is a natural generalization of the classical (Δ+1)-coloring and (Δ+1)-list coloring problems, both being benchmark problems extensively studied in distributed and parallel computing. In this paper we settle the complexity of the (degree+1)-list coloring problem in the Congested Clique model by showing that it can be solved deterministically in a constant number of rounds.
Cite as

Sam Coy, Artur Czumaj, Peter Davies, and Gopinath Mishra. Optimal (Degree+1)-Coloring in Congested Clique. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{coy_et_al:LIPIcs.ICALP.2023.46,
  author =	{Coy, Sam and Czumaj, Artur and Davies, Peter and Mishra, Gopinath},
  title =	{{Optimal (Degree+1)-Coloring in Congested Clique}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{46:1--46:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.46},
  URN =		{urn:nbn:de:0030-drops-180987},
  doi =		{10.4230/LIPIcs.ICALP.2023.46},
  annote =	{Keywords: Distributed computing, graph coloring, parallel computing}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.11
Near-Shortest Path Routing in Hybrid Communication Networks

Authors: Sam Coy, Artur Czumaj, Michael Feldmann, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, Philipp Schneider, and Martijn Struijs

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

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

Sam Coy, Artur Czumaj, Michael Feldmann, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, Philipp Schneider, and Martijn Struijs. Near-Shortest Path Routing in Hybrid Communication Networks. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{coy_et_al:LIPIcs.OPODIS.2021.11,
  author =	{Coy, Sam and Czumaj, Artur and Feldmann, Michael and Hinnenthal, Kristian and Kuhn, Fabian and Scheideler, Christian and Schneider, Philipp and Struijs, Martijn},
  title =	{{Near-Shortest Path Routing in Hybrid Communication Networks}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.11},
  URN =		{urn:nbn:de:0030-drops-157863},
  doi =		{10.4230/LIPIcs.OPODIS.2021.11},
  annote =	{Keywords: Hybrid networks, overlay networks}
}
  • Refine by Type
  • 7 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 4 2025
  • 1 2023
  • 1 2022

  • Refine by Author
  • 3 Czumaj, Artur
  • 2 Censor-Hillel, Keren
  • 2 Coy, Sam
  • 2 Scheideler, Christian
  • 2 Soto, Pedro
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs

  • Refine by Classification
  • 5 Theory of computation → Distributed algorithms
  • 3 Theory of computation → Massively parallel algorithms
  • 2 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Facility location and clustering
  • 1 Theory of computation → Parallel algorithms
  • Show More...

  • Refine by Keyword
  • 1 Congested Clique
  • 1 DBSCAN
  • 1 Distributed Graph Algorithms
  • 1 Distributed computing
  • 1 Error Correction Codes
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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