publications

2025

1. ICDCN

   Fast Deterministic Massively Parallel Ruling Sets Algorithms

   Hongyan Ji, Kishore Kothapalli, Sriram V Pemmaraju, and Ajitanshu Singh

   In Proceedings of the 26th International Conference on Distributed Computing and Networking, 2025

   Abs PDF

   In this paper, we present a deterministic (tildeO(log ^1/3Delta) )-round algorithm for the 2-ruling set problem in the sublinear Massively Parallel Computation (MPC) model. This improves upon the fastest known deterministic 2-ruling set algorithm for this model, which is the (tildeO(sqrt log n) )-round algorithm by Giliberti and Parsaeian (PODC 2024). Our result is obtained by derandomizing the “sample-and-gather” approach of Kothapalli, Pai, and Pemmaraju (FSTTCS 2020). The “sample-and-gather” approach involves making random sampling decisions, not just for the current iteration, but a batch of future iterations. Thus, derandomizing this approach requires the “fixing” of randomness for a batch of future iterations. We further extend our results to show that a β -ruling set for β ≥ 2 can be obtained in (tildeO(log ^1/2^beta -1 Delta) ) deterministic rounds in the sublinear MPC model. Additionally, we present a deterministic β -ruling set algorithms for sparse graphs (i.e., bounded arboricity graphs) where β ≥ 2, which runs in (tildeO(log ^1/2^beta - 1 lambda) ) rounds for arboricity-λ graphs in the sublinear MPC model.

2. ICDCN

   Faster Set Cover in the MPC Model

   Hongyan Ji, Shreyas Pai, Sriram Pemmaraju, and Joshua Sobel

   In Proceedings of the 26th International Conference on Distributed Computing and Networking, 2025

   Abs PDF

   The Massively Parallel Computation (MPC) model is a popular abstraction for large-scale distributed computing. The Set Cover problem is a classical combinatorial optimization problem that has a wide variety of applications and generalizes many well-studied problems such as vertex cover, edge cover, and minimum dominating set. For a Set Cover instance with a ground set of n elements and a collection of m sets, we present two O(log n)-approximation algorithms in the MPC model. Our algorithms run in (tildeO(log N) )-rounds in the linear-memory MPC model and in (tildeO(log ^1.5 N) ) rounds in the sublinear-memory MPC model, where N = n + m. These are the first O(log n)-approximation algorithms for Set Cover in this setting that run in o(log 2N) rounds. Our results are obtained by repurposing the sparsified graph exponentiation technique that has been successful for the maximal independent set problem in the MPC model and applying it to a simple, distributed Set Cover algorithm by Grunau, Mitrović, Rubinfeld, and Vakilian (SODA 2020).

   Best Paper Award - Distributed Computing track 🏆 in ICDCN 2025

2024

1. SIROCCO

   Towards singular optimality in the presence of local initial knowledge

   Hongyan Ji, and Sriram V Pemmaraju

   In International Colloquium on Structural Information and Communication Complexity, 2024

   Abs PDF

   The \textitKnowledge Till ρ (in short, KT-ρ) CONGEST model is a variant of the classical CONGEST model of distributed computing in which each vertex v has initial knowledge of the radius-ρball centered at v. The most commonly studied variants of the CONGEST model are KT-0 CONGEST in which nodes initially know nothing about their neighbors and KT-1 CONGEST in which nodes initially know the IDs of all their neighbors. It has been shown that having access to neighbors IDs (as in the KT-1 CONGEST model) can substantially reduce the message complexity of algorithms for fundamental problems such as Broadcast and MST. For example, King, Kutten, and Thorup (PODC 2015) show how to construct an MST using just \tildeO(n) messages in the KT-1 CONGEST model for an n-node graph, whereas there is an Ω(m) message lower bound for MST in the KT-0 CONGEST model for m-edge graphs. Building on this result, Gmyr and Pandurangen (DISC 2018) present a family of distributed randomized algorithms for various global problems that exhibit a trade-off between message and round complexity. These algorithms are based on constructing a sparse, spanning subgraph called a \textitdanner. Specifically, given a graph G and any δ∈[0,1], their algorithm constructs (with high probability) a danner that has diameter \tildeO(D + n^1-δ) and \tildeO(\min{m,n^1+δ}) edges in \tildeO(n^1-δ) rounds while using \tildeO(\min{m,n^1+δ}) messages, where n, m, and D are the number of nodes, edges, and the diameter of G, respectively. In the main result of this paper, we show that if we assume the KT-2 CONGEST model, it is possible to substantially improve the time-message trade-off in constructing a danner. Specifically, we show in the KT-2 CONGEST model, how to construct a danner that has diameter \tildeO(D + n^1-2δ) and \tildeO(\min{m,n^1+δ}) edges in \tildeO(n^1-2δ) rounds while using \tildeO(\min{m,n^1+δ}) messages for any δ∈[0,\frac12]. This result has immediate consequences for Broadcast, spanning tree construction, MST, Leader Election, and even local problems such as (∆+1)-coloring in the KT-2 CONGEST model. For example, we obtain a KT-2 CONGEST algorithm for MST that runs in \tildeO(D + n^1/2) rounds, while using only \tildeO(\min{m, n^1 + 1/4}) messages.