[month] [year]

IPDPS-2021

Prof. Kishore Kothapalli presented a paper on Efficient  Distributed Algorithms in the k.-machine model via PRAM Simulations at IEEE International Parallel and Distributed Processing Symposium (IPDPS -2021). The conference was held virtually from 17 – 20 May. The authors of this paper are John Augustine, Dr. Kishore Kothapalli and Gopal Pandurangan and here is the explanation of their research work: 

We study several fundamental problems in the $k$-machine model, a message-passing model for large-scale distributed computations where $k\geq 2$ machines jointly perform computations on a large input of size $N$, (typically, $N \gg k$). The input is initially partitioned (randomly or in a balanced fashion) among the $k$ machines, a common implementation in many real-world systems. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation.

Our main result is a general technique for designing efficient deterministic distributed  algorithms in the $k$-machine model using PRAM algorithms. Our technique works by efficiently simulating PRAM algorithms in the $k$-machine model in a \emph{deterministic} way.  This simulation allows us to arrive at  new algorithms in the $k$-machine model for some problems for which no efficient $k$-machine algorithms are known before and also improve on existing results in the $k$-machine model for some problems.

While our simulation allows us to obtain $k$-machine algorithms for any problem with a known PRAM algorithm, we mainly focus on graph problems. For an input graph on $n$ vertices and $m$ edges, we obtain   $\tilde{O}(m/k^2)$ round\footnote{$\tilde{O}$ notation hides a $\polylog(\cdot)$ factor and an additive $\polylog(\cdot)$ term.} algorithms for various graph problems such as $r$–connectivity for $r=1,2,3,4$, minimum spanning tree (MST), maximal independent set (MIS), ($\Delta+1$)-coloring, maximal matching, ear decomposition, and spanners under the assumption that the edges of the input graph are partitioned (randomly, or in an arbitrary, but balanced, fashion) among the $k$ machines. For problems such as connectivity and MST, the above bound is (essentially) the best possible (up to logarithmic factors). Our simulation technique allows us to obtain the first known efficient \emph{deterministic} algorithms in the $k$-machine model for  other problems with known deterministic PRAM algorithms.

IPDPS is an international forum for engineers and scientists from around the world to present their latest research findings in all aspects of parallel computation. In addition to technical sessions of submitted paper presentations, the meeting offered workshops, tutorials, and commercial presentations & exhibits. IPDPS had a unique international gathering of computer scientists from around the world.