Abstract. We consider the distributed complexity of the ( degree + 1 )-list coloring problem, in which each node [Formula: see text] of degree [Formula: see text] is assigned a palette of [Formula: see text] 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 [Formula: see text]-coloring and [Formula: see text]-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.

We consider the classic \( k \) -center problem in the constant dimensional Euclidean space under a parallel setting, on the low-local-space Massively Parallel Computation (MPC) model, with local space per machine of \(\mathcal{O}(n^{\delta})\) , where \(\delta\in(0,1)\) is an arbitrary constant. As a central clustering problem, the \( k \) -center problem has been studied extensively. Still, until very recently, all parallel MPC algorithms have been requiring \(\Omega(k)\) or even \(\Omega(kn^{\delta})\) local space per machine. While this setting covers the case of small values of \( k \) , for a large number of clusters these algorithms require large local memory, making them poorly scalable. The case of large \( k \) , \(k\geq\Omega(n^{\delta})\) , has been considered recently for the low-local-space MPC model by Bateni et al. [2021], who gave an \(\mathcal{O}(\log\log n)\) -round MPC algorithm that produces \(k(1+o(1))\) centers whose cost has multiplicative approximation of \(\mathcal{O}(\log\log\log n)\) . In this article, we extend the algorithm of Bateni et al. and design a low-local-space MPC algorithm that in \(\mathcal{O}(\log\log n)\) rounds returns a clustering with \(k(1+o(1))\) clusters that is an \(\mathcal{O}(\log^{*}n)\) -approximation for \( k \) -center.

• We develop a general derandomization framework, providing a useful tool for translating some class of randomized LOCAL algorithms to deterministic MPC in a black-box manner. • As an application, we give an O (log log log n )-round deterministic algorithm for (degree+1)-list coloring in strongly-sublinear space MPC . Graph coloring problems are among the most fundamental problems in parallel and distributed computing, and have been studied extensively in both settings. In this context, designing efficient deterministic algorithms for these problems has been found particularly challenging. In this work we consider this challenge, and design a novel framework for derandomizing algorithms for coloring-type problems in the Massively Parallel Computation (MPC) model with sublinear space. We give an application of this framework by showing that a recent ( d e g r e e + 1 ) -list coloring algorithm by Halldórsson, Kuhn, Nolin, and Tonoyan (STOC’22) in the LOCAL model of distributed computation can be translated to the MPC model and efficiently derandomized. Our algorithm runs in O (log log log n ) rounds, which matches the complexity of the state of the art algorithm for the ( Δ + 1 ) -coloring problem.

Graph coloring problems are among the most fundamental problems in parallel and distributed computing, and have been studied extensively in both settings. In this context, designing efficient deterministic algorithms for these problems has been found particularly challenging.In this work we consider this challenge, and design a novel framework for derandomizing algorithms for coloring-type problems in the Massively Parallel Computation (MPC) model with sublinear space. We give an application of this framework by showing that a recent (degree + 1) -list coloring algorithm by Halldorsson et al. (STOC’22) in the LOCAL model of distributed computation can be translated to the MPC model and efficiently derandomized. Our algorithm runs in O (log log log n) rounds, which matches the complexity of the state of the art algorithm for the (Δ + 1)-coloring problem.

We consider two natural variants of the problem of minimum spanning tree (MST) of a graph in the parallel setting: MST verification (verifying if a given tree is an MST) and the sensitivity analysis of an MST (finding the lowest cost replacement edge for each edge of the MST). These two problems have been studied extensively for sequential algorithms and for parallel algorithms in the PRAM model of computation. In this paper, we extend the study to the standard model of Massive Parallel Computation (MPC).

We consider the problem of computing routing schemes in the HYBRID model of distributed computing where nodes have access to two fundamentally different communication modes. In this problem nodes have to compute small labels and routing tables that allow for efficient routing of messages in the local network, which typically offers the majority of the throughput. Recent work has shown that using the HYBRID model admits a significant speed-up compared to what would be possible if either communication mode were used in isolation. Nonetheless, if general graphs are used as the input graph the computation of routing schemes still takes polynomial rounds in the HYBRID model. We bypass this lower bound by restricting the local graph to unit-disc-graphs and solve the problem deterministically with running time O(|H|2+log⁡n), label size O(log⁡n), and size of routing tables O(|H|2⋅log⁡n) where |H| is the number of “radio holes” in the network. Our work builds on recent work by Coy et al., who obtain this result in the much simpler setting where the input graph has no radio holes. We develop new techniques to achieve this, including a decomposition of the local graph into path-convex regions, where each region contains a shortest path for any pair of nodes in it.

We consider the classic k-center problem in a parallel setting, on the low-local-space Massively Parallel Computation (MPC) model, with local space per machine of O (nδ), where δ ∈ (0,1) is an arbitrary constant. As a central clustering problem, the k-center problem has been studied extensively. Still, until very recently, all parallel MPC algorithms have been requiring Ω(k) or even Ω(knδ) local space per machine. While this setting covers the case of small values of k, for a large number of clusters these algorithms require large local memory, making them poorly scalable. The case of large k,k ≥ Ω(nδ), has been considered recently for the low-local-space MPC model by Bateni et al. (2021), who gave an O (log log n)-round MPC algorithm that produces k(1 + ο (1)) centers whose cost has multiplicative approximation of O (log log log n). In this paper we extend the algorithm of Bateni et al. and design a low-local-space MPC algorithm that in O (log log n) rounds returns a clustering with k(1 + ο(1)) clusters that is an O (log*n)-approximation for k-center.

Abstract. We consider the problem of designing fundamental graph algorithms on the model of massively parallel computation (MPC). The input to the problem is an undirected graph [Formula: see text] with [Formula: see text] vertices and [Formula: see text] edges and with [Formula: see text] being the maximum diameter of any connected component in [Formula: see text]. We consider the MPC with low local space, allowing each machine to store only [Formula: see text] words for an arbitrary constant [Formula: see text] and with linear global space (which is the number of machines times the local space available), that is, with optimal utilization. In a recent breakthrough, Andoni et al. [ Parallel graph connectivity in log diameter rounds, 2018] and Behnezhad, Hajiaghayi, and Harris [ Exponentially faster massively parallel maximal matching, 2019] designed parallel randomized algorithms that in [Formula: see text] rounds on an MPC with low local space determine all connected components of a graph, improving on the classic bound of [Formula: see text] derived from earlier works on PRAM algorithms. In this paper, we show that asymptotically identical bounds can be also achieved for deterministic algorithms: We present a deterministic MPC low local space algorithm that in [Formula: see text] rounds determines connected components of the input graph. Our result matches the complexity of state-of-the-art randomized algorithms for this task. We complement our upper bounds by extending a recent lower bound for the connectivity on an MPC conditioned on the 1-vs-2-cycles conjecture (which requires [Formula: see text]) by showing a related conditional hardness of [Formula: see text] MPC rounds for the entire spectrum of [Formula: see text], covering a particularly interesting range when [Formula: see text].

We consider the problem of designing fundamental graph algorithms on the model of Massive Parallel Computation (MPC). The input to the problem is an undirected graph G with n vertices and m edges, and with D being the maximum diameter of any connected component in G. We consider the MPC with low local space, allowing each machine to store only Θ(nδ) words for an arbitrary constant δ>0, and with linear global space (which is the number of machines times the local space available), that is, with optimal utilization.

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 $\mathsf{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 $\mathsf{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.