A Case Study in Real-Time Parallel Computation: Correcting Algorithms

A correcting algorithm is one that receives an endless stream of corrections to its initial input data and terminates when all the corrections received have been taken into account. We give a characterization of correcting algorithms based on the theory of data-accumulating algorithms. In particular, it is shown that any correcting algorithm exhibits superunitary behavior in a parallel computation setting if and only if the static counterpart of that correcting algorithm manifests a strictly superunitary speedup. Since both classes of correcting and data-accumulating algorithms are included in the more general class of real--time algorithms, we show in fact that many problems from this class manifest superunitary behavior. Moreover, we give an example of a real-time parallel computation that pertains to neither of the two classes studied (namely, correcting and data-accumulating algorithms), but still manifests superunitary behavior. Because of the aforementioned results, the usual..