The time complexity of wait-free algorithms in “normal” executions, where no failures occur
and processes operate at approximately the same speed, is considered. A lower bound of …

Massively parallel computation (MPC) algorithms for graph problems have witnessed a
resurgence of interest in recent years. Despite major progress for numerous graph problems …

Likewise, when a long series of identical computations is to be performed, such as those
required for the formation of numerical tables, the machine can be brought into play so as to …

Цель данного обзора дать максимально полное представление о достижениях и
современном состоянии дел в разработке аналитических моделей параллельных …

The gossip problem involves communicating a unique item from each node in a graph to
every other node. This paper studies the minimum time required to do this under the …

Parallel complexity theory | Guide books skip to main content ACM Digital Library home
ACM home Google, Inc. (search) Advanced Search Browse About Sign in Register …

Threshold machines are Turing machines whose acceptance is determined by what portion
of the machine's computation paths are accepting paths. Probabilistic machines are Turing …

A directed cycle separator of an n-vertex directed graph is a simple directed cycle such that
when the vertices of the cycle are deleted, the resulting graph has no strongly connected …

We present a parallel priority queue that supports the following operations in constant time:
parallel insertionof a sequence of elements ordered according to key, parallel decrease …

To understand the power of distributed systems, it is necessary to understand their inherent
limitations: what problems cannot be solved in particular systems, or without sufficient …