Source author record

Krzysztof Nowicki

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Distributed, Parallel, and Cluster Computing Data Structures and Algorithms

Catalog footprint

Research overview

3works

2topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Dynamic Graph Algorithms with Batch Updates in the Massively Parallel Computation Model

We study dynamic graph algorithms in the Massively Parallel Computation model, which was inspired by practical data processing systems. Our goal is to provide algorithms that can efficiently handle large batches of edge insertions and deletions. We show algorithms that require fewer rounds to update a solution to problems such as Minimum Spanning Forest, 2-Edge Connected Components, and Maximal Matching than would be required by their static counterparts to compute it from scratch. They work in the most restrictive memory regime, in which local memory per machine is strongly sublinear in the number of graph vertices. Improving on the size of the batch they can handle efficiently would improve on the round complexity of known static algorithms on sparse graphs. Our algorithms can process batches of updates of size $Θ(S)$ , for Minimum Spanning Forest and 2-Edge Connected Components, and $Θ(S^{1-\varepsilon})$ , for Maximal Matching, in $O(1)$ rounds, where $S$ is the local memory of a single machine.

preprint2020arXiv

A Deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique

In this paper, we show that the Minimum Spanning Tree problem can be solved \emph{deterministically}, in $\mathcal{O}(1)$ rounds of the $\mathsf{Congested}$ $\mathsf{Clique}$ model. In the $\mathsf{Congested}$ $\mathsf{Clique}$ model, there are $n$ players that perform computation in synchronous rounds. Each round consist of a phase of local computation and a phase of communication, in which each pair of players is allowed to exchange $\mathcal{O}(\log n)$ bit messages. The studies of this model began with the MST problem: in the paper by Lotker et al.[SPAA'03, SICOMP'05] that defines the $\mathsf{Congested}$ $\mathsf{Clique}$ model the authors give a deterministic $\mathcal{O}(\log \log n)$ round algorithm that improved over a trivial $\mathcal{O}(\log n)$ round adaptation of Borůvka's algorithm. There was a sequence of gradual improvements to this result: an $\mathcal{O}(\log \log \log n)$ round algorithm by Hegeman et al. [PODC'15], an $\mathcal{O}(\log^* n)$ round algorithm by Ghaffari and Parter, [PODC'16] and an $\mathcal{O}(1)$ round algorithm by Jurdziński and Nowicki, [SODA'18], but all those algorithms were randomized, which left the question about the existence of any deterministic $o(\log \log n)$ round algorithms for the Minimum Spanning Tree problem open. Our result resolves this question and establishes that $\mathcal{O}(1)$ rounds is enough to solve the MST problem in the $\mathsf{Congested}$ $\mathsf{Clique}$ model, even if we are not allowed to use any randomness. Furthermore, the amount of communication needed by the algorithm makes it applicable to some variants of the $\mathsf{MPC}$ model.

preprint2016arXiv

Parallel multiple selection by regular sampling

In this paper we present a deterministic parallel algorithm solving the multiple selection problem in congested clique model. In this problem for given set of elements S and a set of ranks $K = \{k_1 , k_2 , ..., k_r \}$ we are asking for the $k_i$ -th smallest element of $S$ for $1 \leq i \leq r$ . The presented algorithm is deterministic, time optimal , and needs $O(\log^*_{r+1} (n))$ communication rounds, where $n$ is the size of the input set, and $r$ is the size of the rank set. This algorithm may be of theoretical interest, as for $r = 1$ (classic selection problem) it gives an improvement in the asymptotic synchronization cost over previous $O(\log \log p)$ communication rounds solution, where $p$ is size of clique.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.