Y. Aumann et al., EFFICIENT EXECUTION OF NONDETERMINISTIC PARALLEL PROGRAMS ON ASYNCHRONOUS SYSTEMS, Information and computation, 139(1), 1997, pp. 1-16
We consider the problem of asynchronous execution of parallel programs
. We assume that the original program is designed for a synchronous sy
stem, whereas the actual system may be asynchronous. We seek an automa
tic execution scheme, which allows the asynchronous system to execute
the synchronous program. Previous execution schemes provide solutions
only for the case where the original program is deterministic. Here, w
e provide the first solution for the more general case where the origi
nal program can be nondeterministic (e.g., randomized). Our scheme is
based on a novel agreement protocol for the asynchronous parallel sett
ing. Our protocol allows n asynchronous processors to agree on n word-
sited values in O(n log n log log n) total work, assuming an oblivious
adversary scheduler. Total work is defined to be tile summation of th
e number of steps performed by all processors (including steps from bu
sy waiting). (C) 1997 Academic Press.