*For the most recent entries see the
Petri Nets Newsletter.*

## Performing Tasks on Restartalbe Message-Passing Pprocessors.

Chlebus, B.S.;
De Prisco, R.;
Shvartsman, A.A.
In:
Mavronicolas, M.; Tsigas, Ph.: *Lecture Notes in Computer Science, Vol. 1320: Distributed Algorithms, Proc. of 11th International Workshop, WDAG'97, Saarbrücken, Germany*, pages 96-110.
Springer,
September 1997.

Abstract:
This work presents new algorithms for the ``Do-All'' problem that consists
of performing t tasks reliably in a message-passing synchronous system of
p fault-prone processors. The algorithms are based on an aggressive
coordination paradigm in which multiple coordinators may be active as the
result of failures. The first algorithm is tolerant of Y<p
stop-failures and it does not allow restarts. It has the available
processor steps complexity S = O((t+p log p/log log p) log Y) and the
message complexity M = O((t+p log p/log log p+Y p). Unlike prior
solutions, our algorithm uses redundant broadcasts when encountering
failures and, for large Y, it has better complexity. This algorithm is
used as the basis for another algorithm which tolerates any patters of
stop-failures and restarts. This new algorithm is the first solution for
the Do-All problem that efficiently deals with processor restarts. Its
available processor steps complexity is S = O((t+p log p+Y) minlog p, log
Y), and its message complexity is M = O(t+p log p+Y p), where Y is the
number of failures.

*Do you need a refined search? Try our search engine
which allows complex field-based queries.*
*Back to the Petri Nets Bibliography*