This paper outlines a theory of parallel algorithms that emphasizes two crucial aspects of
parallel computation: speedup the improvement in running time due to parallelism, and …

A technique to extend the base of a residue number system (RNS) based on the Chinese
remainder theorem (CRT) and the use of a redundant modulus, is proposed. The technique …

Population protocols, roughly defined as systems consisting of large numbers of simple
identical agents, interacting at random and updating their state following simple rules, are an …

Identifying the connected components of a graph, apart from being a fundamental problem
with countless applications, is a key primitive for many other algorithms. In this paper, we …

The goal of this article is to identify fundamental limitations on how efficiently algorithms
implemented on platforms such as MapReduce and Hadoop can compute the central …

This paper introduces the queue-read queue-write (\sc qrqw) parallel random access
machine (\sc pram) model, which permits concurrent reading and writing to shared-memory …

We study the problem of sorting n numbers on a p-processor bulk-synchronous
parallel(BSP) computer, which is a parallel multicomputer that allows for general processor …

We survey results from distributed computing that show tasks to be impossible, either
outright or within given resource bounds, in various models. The parameters of the models …

In this paper, we study parallel algorithms for private-cache chip multiprocessors (CMPs),
focusing on methods for foundational problems that are scalable with the number of cores …