Deterministic Massively Parallel Algorithms for Ruling Sets

2022/05/25 by Pai, Shreyas, Pemmaraju, Sriram V.
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.2205.12686

Abstract

In this paper we present a deterministic O(loglog n)-round algorithm for the 2-ruling set problem in the Massively Parallel Computation model with O(n) memory; this algorithm also runs in O(loglog n) rounds in the Congested Clique model. This is exponentially faster than the fastest known deterministic 2-ruling set algorithm for these models, which is simply the O(log Δ)-round deterministic Maximal Independent Set algorithm due to Czumaj, Davies, and Parter (SPAA 2020). Our result is obtained by derandomizing the 2-ruling set algorithm of Kothapalli and Pemmaraju (FSTTCS 2012).

Related

• Massively Parallel Ruling Set Made Deterministic
• Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem
• Sample-and-Gather: Fast Ruling Set Algorithms in the Low-Memory MPC Model
• Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets
• A Deterministic Algorithm for the MST Problem in Constant Rounds of\n Congested Clique