### Browsing by Author "Uitto, Jara"

Now showing 1 - 20 of 26

###### Results Per Page

###### Sort Options

Item Adaptive Massively Parallel Connectivity in Optimal Space(2023-06-17) Latypov, Rustam; Łacki, Jakub; Maus, Yannic; Uitto, Jara; Department of Computer Science; Google Research; Graz University of Technology; Computer Science ProfessorsWe study the problem of finding connected components in the Adaptive Massively Parallel Computation (AMPC) model. We show that when we require the total space to be linear in the size of the input graph the problem can be solved in O(log∗n) rounds in forests (with high probability) and 2O(log∗n) expected rounds in general graphs. This improves upon an existing O(log logm/nn) round algorithm. For the case when the desired number of rounds is constant we show that both problems can be solved using I(m + n log(k) n) total space in expectation (in each round), where k is an arbitrarily large constant and log(k) is the k-th iterate of the log2 function. This improves upon existing algorithms requiring ω(m + n log n) total space.Item Applying Category Theory to the Study of Biregular LCL-Problems and Round Elimination(2023-12-12) Virtanen, Selim; Suomela, Jukka; Uitto, Jara; Perustieteiden korkeakoulu; Hollanti, CamillaRecently, a lot of progress has been made in the study of distributed computational complexity in the class of so-called locally checkable labelling problems (LCLs). In particular, there is a new proof technique, round elimination, which resembles a function, and finding its periodic points in a further restricted biregular formalism has been fruitful for showing lower bounds. In this thesis I provide a rigorous definition for biregular LCL-problems based on category theory, which gives powerful tools for studying 0-round reductions and equivalence of problems. I define the category LCL (d, delta) with (d, delta)-biregular LCL-problems as objects and local correctness preserving (LCP) maps as morphisms. The use of categories gives access to terminology and definitions from category theory. LCP-maps imply 0-round reductions, and conversely I show that once impossible labels are removed, they capture all 0-round reductions that can be found with reasonable assumptions. In this framework round elimination becomes a map between categories, and I prove that it preserves the existence of LCP-maps. Thus it can be defined over equivalence classes, generalising it as a proof technique and unifying existing definitions. My main result is that with reasonable assumptions the longest period of a periodic point of round elimination is 2. This implies that periodicity of a problem Pi can be checked automatically by determining the existence of LCP-maps Re2(Pi) to Pi, for which I provide an implementable algorithm. Finally, the new tools make it possible to define a minimality condition for representatives of equivalence classes, which can be checked without referencing other problems. I prove that it is equivalent to an intuitive condition, and show how to minimise representatives. This work provides a new perspective for the further study of biregular LCLproblems and improvements for the automated analysis tools. These in turn enhance our understanding of distributed computational complexity, which can help us develop more efficient algorithms for distributed systems.Item Automaattinen markkinanteko Uniswap-protokollassa(2023-09-10) Oksa, Tuomas; Uitto, Jara; Perustieteiden korkeakoulu; Hyvönen, EeroItem Brief Announcement: Efficient Load-Balancing through Distributed Token Dropping(Schloss Dagstuhl--Leibniz-Zentrum für Informatik, 2020) Sebastian, Brandt; Keller, Barbara; Rybicki, Joel; Suomela, Jukka; Uitto, Jara; Department of Computer Science; Attiya, Hagit; Professorship Uitto J.; Professorship Suomela J.; Professorship Vuorimaa P.; Computer Science - Algorithms and Theoretical Computer Science (TCS); Swiss Federal Institute of Technology Zurich; IST AustriaWe introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for the stable orientation problem, which is a special case of the more general locally optimal semi-matching problem. The prior work by Czygrinow et al. (DISC 2012) finds a locally optimal semi-matching in O(Δ⁵) rounds in graphs of maximum degree Δ, which directly implies an algorithm with the same runtime for stable orientations. We improve the runtime to O(Δ⁴) for stable orientations and prove a lower bound of Ω(Δ) rounds.Item Brief Announcement: Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees(Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2021) Brandt, Sebastian; Latypov, Rustam; Uitto, Jara; ETH Zurich; Professorship Uitto J.; Computer Science Professors; Department of Computer Science; Gilbert, SethWe establish scalable Massively Parallel Computation (MPC) algorithms for a family of fundamental graph problems on trees. We give a general method that, for a wide range of LCL problems, turns their message passing counterparts into exponentially faster algorithms in the sublinear MPC model. In particular, we show that any LCL on trees that has a deterministic complexity of O(n) in the LOCAL model can be sped up to O(log n) (high-complexity regime) in the sublinear MPC model and similarly n^{o(1)} to O(log log n) (intermediate-complexity regime). We emphasize, that we work on bounded degree trees and all of our algorithms work in the sublinear MPC model, where local memory is O(n^δ) for δ < 1 and global memory is O(m). For the high-complexity regime, one key ingredient is a novel pointer-chain technique and analysis that allows us to solve any solvable LCL on trees with a sublinear MPC algorithm with complexity O(log n). For the intermediate-complexity regime, we adapt the approach by Chang and Pettie [FOCS'17], who gave a canonical algorithm for solving LCL problems on trees in the LOCAL model. For the special case of 3-coloring trees, which is a natural LCL problem, we provide a conditional Ω(log log n) lower bound, implying that solving LCL problems on trees with deterministic LOCAL complexity n^{o(1)} requires Θ(log log n) deterministic time in the sublinear MPC model when using a natural family of component-stable algorithms.Item Coloring Sparse Graphs with 3 Colors in the Massively Parallel Computation (MPC) Model Using Strongly Sublinear Memory(2021-01-26) Latypov, Rustam; Uitto, Jara; Perustieteiden korkeakoulu; Uitto, JaraThe question of what problems can be solved, and how efficiently, has always been at the core of theoretical computer science. One such fundamental problem is graph coloring; it is well researched and has numerous applications in areas of computer science such as scheduling and pattern matching. The challenges faced when designing graph coloring algorithms are dictated by the underlying graph family, the number of colors allowed, and the model of computation. In this work we consider the graph family of trees and the distributed Massively Parallel Computation (MPC) model, introduced by Karloff et al. \cite{karloff}. Our contribution to the field of distributed computing is a deterministic strongly sublinear MPC algorithm for 3-coloring unbounded degree trees with $n$ nodes in $O(\log \log n)$ time. To the best of our knowledge, this is the current state-of-the-art algorithm, improving on the work of Ghaffari et al. \cite{ghaffari}. It is loosely based on two previous works by Brandt et al. \cite{sparce,sirocco}. Before computing a 3-coloring, our algorithm partitions the input tree into disjoint node sets $H_1,H_2,\dots,H_l$, in $O(\log \log n)$ time. For each node $v \in H_i$, it holds that $v$ has at most two neighbors in the set $\bigcup_{j=i}^l H_j$. We consider this partitioning in and of itself an important contribution, since it has the potential of being a useful subroutine in future algorithms. For example, a similar technique was used by Chang et al. \cite{chang} in their seminal paper to establish an important time hierarchy theorem for the distributed LOCAL model on trees.Item Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds(2019-11) Ghaffari, Mohsen; Kuhn, Fabian; Uitto, Jara; Department of Computer Science; Professorship Savioja L.; Swiss Federal Institute of Technology Zurich; University of FreiburgWe present the first conditional hardness results for massively parallel algorithms for some central graph problems including (approximating) maximum matching, vertex cover, maximal independent set, and coloring. In some cases, these hardness results match or get close to the state of the art algorithms. Our hardness results are conditioned on a widely believed conjecture in massively parallel computation about the complexity of the connectivity problem. We also note that it is known that an unconditional variant of such hardness results might be somewhat out of reach for now, as it would lead to considerably improved circuit complexity lower bounds and would concretely imply that NC_1 is a proper subset of P. We obtain our conditional hardness result via a general method that lifts unconditional lower bounds from the well-studied LOCAL model of distributed computing to the massively parallel computation setting.Item Conditionally Optimal Parallel Coloring of Forests(2023-10) Grunau, Christoph; Latypov, Rustam; Maus, Yannic; Pai, Shreyas; Uitto, Jara; Department of Computer Science; Oshman, Rotem; Professorship Uitto J.; Computer Science Professors; Computer Science - Algorithms and Theoretical Computer Science (TCS); Swiss Federal Institute of Technology Zurich; Department of Computer Science; Graz University of TechnologyWe show the first conditionally optimal deterministic algorithm for 3-coloring forests in the low-space massively parallel computation (MPC) model. Our algorithm runs in O(log log n) rounds and uses optimal global space. The best previous algorithm requires 4 colors [Ghaffari, Grunau, Jin, DISC'20] and is randomized, while our algorithm are inherently deterministic. Our main technical contribution is an O(log log n)-round algorithm to compute a partition of the forest into O(log n) ordered layers such that every node has at most two neighbors in the same or higher layers. Similar decompositions are often used in the area and we believe that this result is of independent interest. Our results also immediately yield conditionally optimal deterministic algorithms for maximal independent set and maximal matching for forests, matching the state of the art [Giliberti, Fischer, Grunau, SPAA'23]. In contrast to their solution, our algorithms are not based on derandomization, and are arguably simpler.Item Deterministic (1+)-approximate maximum matching with poly(1/) passes in the semi-streaming model and beyond(2022-09-06) Fischer, Manuela; Mitrović, Slobodan; Uitto, Jara; Department of Computer Science; Leonardi, Stefano; Gupta, Anupam; Computer Science Professors; Computer Science - Algorithms and Theoretical Computer Science (TCS); Professorship Uitto J.; Swiss Federal Institute of Technology Zurich; University of California, DavisWe present a deterministic (1+ϵ)-approximate maximum matching algorithm in poly(1/ϵ) passes in the semi-streaming model, solving the long-standing open problem of breaking the exponential barrier in the dependence on 1/ϵ. Our algorithm exponentially improves on the well-known randomized (1/ϵ)O(1/ϵ)-pass algorithm from the seminal work by McGregor [APPROX05], the recent deterministic algorithm by Tirodkar with the same pass complexity [FSTTCS18]. Up to polynomial factors in 1/ϵ, our work matches the state-of-the-art deterministic (logn / loglogn) · (1/ϵ)-pass algorithm by Ahn and Guha [TOPC18], that is allowed a dependence on the number of nodes n. Our result also makes progress on the Open Problem 60 at sublinear.info. Moreover, we design a general framework that simulates our approach for the streaming setting in other models of computation. This framework requires access to an algorithm computing a maximal matching and an algorithm for processing disjoint ( 1 / ϵ)-size connected components. Instantiating our framework in CONGEST yields a (logn, 1/ϵ) round algorithm for computing (1+ϵ)-approximate maximum matching. In terms of the dependence on 1/ϵ, this result improves exponentially state-of-the-art result by Lotker, Patt-Shamir, and Pettie [LPSP15]. Our framework leads to the same quality of improvement in the context of the Massively Parallel Computation model as well.Item Distributed Drawing of Planar Graphs in the CONGEST model(2022-07-29) Sederholm, Hannes; Latypov, Rustam; Perustieteiden korkeakoulu; Uitto, JaraThe concept of planarity has been widely studied in many contexts. However, in the distributed setting and specifically in the CONGEST model, relatively little work has been done in the area. Especially, the problem of drawing planar graphs has not been solved previously in CONGEST. In this thesis the problem is studied by inspecting existing non-distributed algorithms. As a result a novel CONGEST algorithm solving this problem is presented. The algorithm utilizes an existing distributed algorithm to obtain a combinatorial embedding of a graph. Given the running time of obtaining an embedding the running time of the algorithm is negligible, and thus analysis of the performance of the algorithm focuses on the quality of the drawings. The quality of the drawings are evaluated with examples created by programmatically simulating the execution of the algorithm.Item Distributed recoloring(Schloss Dagstuhl--Leibniz-Zentrum für Informatik, 2018-10-01) Bonamy, Marthe; Ouvrard, Paul; Rabie, Mikaël; Suomela, Jukka; Uitto, Jara; Department of Computer Science; Schmid, Ulrich; Widder, Josef; Professorship Suomela J.; Université de Bordeaux; Swiss Federal Institute of Technology ZurichGiven two colorings of a graph, we consider the following problem: can we recolor the graph from one coloring to the other through a series of elementary changes, such that the graph is properly colored after each step? We introduce the notion of distributed recoloring: The input graph represents a network of computers that needs to be recolored. Initially, each node is aware of its own input color and target color. The nodes can exchange messages with each other, and eventually each node has to stop and output its own recoloring schedule, indicating when and how the node changes its color. The recoloring schedules have to be globally consistent so that the graph remains properly colored at each point, and we require that adjacent nodes do not change their colors simultaneously. We are interested in the following questions: How many communication rounds are needed (in the deterministic LOCAL model of distributed computing) to find a recoloring schedule? What is the length of the recoloring schedule? And how does the picture change if we can use extra colors to make recoloring easier? The main contributions of this work are related to distributed recoloring with one extra color in the following graph classes: trees, 3-regular graphs, and toroidal grids.Item Distributed Symmetry Breaking on Power Graphs via Sparsification(2023-06-12) Peltonen, Sakari; Maus, Yannic; Perustieteiden korkeakoulu; Uitto, JaraSymmetry breaking is a central theme in distributed graph algorithms. Classical symmetry breaking problems include maximal independent set (MIS), coloring and maximal matching. To compute a solution, nodes of the network must break their initial symmetry to take on different roles in the output. For instance, the maximal independent set problem requires nodes to select a subset of non-adjacent nodes, such that all excluded nodes have at least one neighbor in the set. We work in the CONGEST model of distributed computing, where the communication network is abstracted as a graph G. In CONGEST, nodes communicate with each other in synchronous rounds along the edges of the graph with O(log n)-bit messages. Local computation is free, while time is measured in the number of rounds. Classically, the problem instance is assumed to be identical to the communication network. This thesis considers symmetry breaking problems on power graphs G^k, k ≥ 1, where nodes are connected if their distance is at most k in G. The main contribution is a deterministic polylogarithmic-time algorithm for computing k-ruling sets of G^k. A beta-ruling set is a relaxation of the MIS problem, where the distance to the set is at most beta for all nodes, instead of 1. For k > 1, our algorithm improves the runtime exponentially compared to any previously known solutions. For randomized algorithms, we show that a maximal independent set of G^k can be computed in essentially the same time as an MIS of G. The second part of this thesis revisit the shattering framework [BEPS JACM'16], used to obtain the state-of-the-art MIS algorithms for G in CONGEST [Ghaffari SODA'19] and the LOCAL models [Ghaffari SODA'16]. We present novel approaches for the post-shattering phase, offering algorithmically and analytically simpler solutions while maintaining the same runtime as existing approaches.Item Distributed Symmetry Breaking on Power Graphs via Sparsification(2023-06-19) Maus, Yannic; Peltonen, Saku; Uitto, Jara; Department of Computer Science; Computer Science Professors; Computer Science - Algorithms and Theoretical Computer Science (TCS); Professorship Uitto J.; Graz University of Technology; Department of Computer ScienceIn this paper we present efficient distributed algorithms for classical symmetry breaking problems, maximal independent sets (MIS) and ruling sets, in power graphs. We work in the standard CONGEST model of distributed message passing, where the communication network is abstracted as a graph G. Typically, the problem instance in CONGEST is identical to the communication network G, that is, we perform the symmetry breaking in G. In this work, we consider a setting where the problem instance corresponds to a power graph Gk, where each node of the communication network G is connected to all of its k-hop neighbors.A β-ruling set is a set of non-adjacent nodes such that each node in G has a ruling neighbor within β hops; a natural generalization of an MIS. On top of being a natural family of problems, ruling sets (in power graphs) are well-motivated through their applications in the powerful shattering framework [BEPS JACM'16, Ghaffari SODA'19] (and others). We present randomized algorithms for computing maximal independent sets and ruling sets of Gk in essentially the same time as they can be computed in G. Our main contribution is a deterministic poly(k, log n) time algorithm for computing k-ruling sets of Gk, which (for k > 1) improves exponentially on the current state-of-the-art runtimes. Our main technical ingredient for this result is a deterministic sparsification procedure which may be of independent interest.We also revisit the shattering algorithm for MIS [BEPS J'ACM'16] and present different approaches for the post-shattering phase. Our solutions are algorithmically and analytically simpler (also in the LOCAL model) than existing solutions and obtain the same runtime as [Ghaffari SODA'16].Item Efficient CONGEST Algorithms for the Lovasz Local Lemma(Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021) Maus, Yannic; Uitto, Jara; Department of Computer Science; Gilbert, Seth; Computer Science Professors; Computer Science - Algorithms and Theoretical Computer Science (TCS); Professorship Uitto J.; Technion - Israel Institute of TechnologyWe present a poly log log n time randomized CONGEST algorithm for a natural class of Lovász Local Lemma (LLL) instances on constant degree graphs. This implies, among other things, that there are no LCL problems with randomized complexity between Ω(log n) and poly log log n. Furthermore, we provide extensions to the network decomposition algorithms given in the recent breakthrough by Rozhoň and Ghaffari [STOC2020] and the follow up by Ghaffari, Grunau, and Rozhoň [SODA2021]. In particular, we show how to obtain a large distance separated weak network decomposition with a negligible dependency on the range of unique identifiers.Item Exponential Speedup over Locality in MPC with Optimal Memory(Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2022-10-17) Balliu, Alkida; Sebastian, Brandt; Fischer, Manuela; Latypov, Rustam; Maus, Yannic; Olivetti, Dennis; Uitto, Jara; Gran Sasso Science Institute; CISPA Helmholtz Center for Information Security; ETH Zurich; Professorship Uitto J.; Graz University of Technology; Computer Science Professors; Department of Computer Science; Scheideler, ChristianLocally Checkable Labeling (LCL) problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example problems in this class include maximal matching, maximal independent set, and coloring problems. A successful line of research has been studying the complexities of LCL problems on paths/cycles, trees, and general graphs, providing many interesting results for the LOCAL model of distributed computing. In this work, we initiate the study of LCL problems in the low-space Massively Parallel Computation (MPC) model. In particular, on forests, we provide a method that, given the complexity of an LCL problem in the LOCAL model, automatically provides an exponentially faster algorithm for the low-space MPC setting that uses optimal global memory, that is, truly linear. While restricting to forests may seem to weaken the result, we emphasize that all known (conditional) lower bounds for the MPC setting are obtained by lifting lower bounds obtained in the distributed setting in tree-like networks (either forests or high girth graphs), and hence the problems that we study are challenging already on forests. Moreover, the most important technical feature of our algorithms is that they use optimal global memory, that is, memory linear in the number of edges of the graph. In contrast, most of the state-of-the-art algorithms use more than linear global memory. Further, they typically start with a dense graph, sparsify it, and then solve the problem on the residual graph, exploiting the relative increase in global memory. On forests, this is not possible, because the given graph is already as sparse as it can be, and using optimal memory requires new solutions.Item Fast Dynamic Programming in Trees in the MPC Model(2023-06-17) Gupta, Chetan; Latypov, Rustam; Maus, Yannic; Pai, Shreyas; Särkkä, Simo; Studený, Jan; Suomela, Jukka; Uitto, Jara; Vahidi, Hossein; Department of Computer Science; Department of Electrical Engineering and Automation; Professorship Uitto J.; Helsinki Institute for Information Technology (HIIT); Sensor Informatics and Medical Technology; Computer Science Professors; Computer Science - Algorithms and Theoretical Computer Science (TCS); Computer Science - Large-scale Computing and Data Analysis (LSCA); Professorship Suomela J.; Department of Computer Science; Graz University of TechnologyWe present a deterministic algorithm for solving a wide range of dynamic programming problems in trees in O(log D) rounds in the massively parallel computation model (MPC), with O(nδ) words of local memory per machine, for any given constant 0 < δ< 1. Here D is the diameter of the tree and n is the number of nodes - -we emphasize that our running time is independent of n. Our algorithm can solve many classical graph optimization problems such as maximum weight independent set, maximum weight matching, minimum weight dominating set, and minimum weight vertex cover. It can also be used to solve many accumulation tasks in which some aggregate information is propagated upwards or downwards in the tree - -this includes, for example, computing the sum, minimum, or maximum of the input labels in each subtree, as well as many inference tasks commonly solved with belief propagation. Our algorithm can also solve any locally checkable labeling problem (LCLs) in trees. Our algorithm works for any reasonable representation of the input tree; for example, the tree can be represented as a list of edges or as a string with nested parentheses or tags. The running time of O(log D) rounds is also known to be necessary, assuming the widely-believed 2-cycle conjecture. Our algorithm strictly improves on two prior algorithms: Bateni, Behnezhad, Derakhshan, Hajiaghayi, and Mirrokni [ICALP'18] solve problems of these flavors in O(log n) rounds, while our algorithm is much faster in low-diameter trees. Furthermore, their algorithm also uses randomness, while our algorithm is deterministic. Balliu, Latypov, Maus, Olivetti, and Uitto [SODA'23] solve only locally checkable labeling problems in O(log D) rounds, while our algorithm can be applied to a much broader family of problems.Item Improved distributed degree splitting and edge coloring(Schloss Dagstuhl--Leibniz-Zentrum für Informatik, 2017) Ghaffari, Mohsen; Hirvonen, Juho; Kuhn, Fabian; Maus, Yannic; Suomela, Jukka; Uitto, Jara; Department of Computer Science; Professorship Suomela J.; Swiss Federal Institute of Technology Zurich; University of Freiburg; Institut de Recherche en Informatique FondamentaleThe 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.Item Massively Parallel Correlation Clustering in Bounded Arboricity Graphs(Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021) Cambus, Melanie; Choo, Davin; Miikonen, Havu; Uitto, Jara; Department of Computer Science; Gilbert, Seth; Professorship Uitto J.; Computer Science Professors; Computer Science - Algorithms and Theoretical Computer Science (TCS); National University of Singapore; Department of Computer ScienceIdentifying clusters of similar elements in a set is a common task in data analysis. With the immense growth of data and physical limitations on single processor speed, it is necessary to find efficient parallel algorithms for clustering tasks. In this paper, we study the problem of correlation clustering in bounded arboricity graphs with respect to the Massively Parallel Computation (MPC) model. More specifically, we are given a complete graph where the edges are either positive or negative, indicating whether pairs of vertices are similar or dissimilar. The task is to partition the vertices into clusters with as few disagreements as possible. That is, we want to minimize the number of positive inter-cluster edges and negative intra-cluster edges. Consider an input graph G on n vertices such that the positive edges induce a λ-arboric graph. Our main result is a 3-approximation (in expectation) algorithm to correlation clustering that runs in (log λ ⋅ poly(log log n)) MPC rounds in the strongly sublinear memory regime. This is obtained by combining structural properties of correlation clustering on bounded arboricity graphs with the insights of Fischer and Noever (SODA '18) on randomized greedy MIS and the PIVOT algorithm of Ailon, Charikar, and Newman (STOC '05). Combined with known graph matching algorithms, our structural property also implies an exact algorithm and algorithms with worst case (1+ε)-approximation guarantees in the special case of forests, where λ = 1.Item Measuring Practical Applications of Modern Massively Parallel Algorithms(2023-01-23) Ferrai, Fabrizio; Uitto, Jara; Perustieteiden korkeakoulu; Uitto, JaraMassively parallel computations are gaining more and more importance in the computing world, due to hardware evolution and the staggering amounts of data produced and consumed by the ever-present software fabric in our daily lives. To keep up with all of this we constantly need more performing distributed algorithms; one of the main paradigms for modelling such problems is MPC, designed to capture the essence of frameworks widely used in the industry, such as MapReduce, Hadoop and Spark. This thesis explores – employing Triton, Aalto’s supercomputing cluster – the practical performance of some state-of-the-art, MPC-based algorithms for computing the connected components of undirected graphs, by benchmarking several of their implementations against each other on different graph sizes and topologies and providing insights on implementation challenges and theoretical complexity vs. practical performance.Item Optimal Deterministic Massively Parallel Connectivity on Forests(2023) Balliu, Alkida; Latypov, Rustam; Maus, Yannic; Olivetti, Dennis; Uitto, Jara; Gran Sasso Science Institute; Professorship Uitto J.; Graz University of Technology; Computer Science Professors; Department of Computer ScienceWe show fast deterministic algorithms for fundamental problems on forests in the challenging low-space regime of the well-known Massive Parallel Computation (MPC) model. A recent breakthrough result by Coy and Czumaj [STOC'22] shows that, in this setting, it is possible to deterministically identify connected components on graphs in O (log D + log log n) rounds, where D is the diameter of the graph and n the number of nodes. The authors left open a major question: is it possible to get rid of the additive log log n factor and deterministically identify connected components in a runtime that is completely independent of n? We answer the above question in the affirmative in the case of forests. We give an algorithm that identifies connected components in O(log D) deterministic rounds. The total memory required is O(n + m) words, where m is the number of edges in the input graph, which is optimal as it is only enough to store the input graph. We complement our upper bound results by showing that Ω(logD) time is necessary even for component-unstable algorithms, conditioned on the widely believed 1 vs. 2 cycles conjecture. Our techniques also yield a deterministic forest-rooting algorithm with the same runtime and memory bounds. Furthermore, we consider Locally Checkable Labeling problems (LCLs), whose solution can be verified by checking the O(1)-radius neighborhood of each node. We show that any LCL problem on forests can be solved in O (log D) rounds with a canonical deterministic algorithm, improving over the O (log n) runtime of Brandt, Latypov and Uitto [DISC'21]. We also show that there is no algorithm that solves all LCL problems on trees asymptotically faster.