Synergy in Parallel Algorithms

In parallel computations one wishes to devise algorithms which will introduce some cooperation among the various processes. Although this will increase the complexity, it might improve the error reduction to such an extent so as to render the total performance beneficial. In such a case we speak of “synergistic algorithm” (synergism is “a cooperative action so that the total effect is greater than the effects taken independently”). This concept with some examples and applications was introduced by Henderson and Miranker [1]. On February 5, 1988 Willard Miranker from IBM Thomas J. Watson Research Center (Yorktown Heights) surveyed this work, part of which we describe below, and outlined some open problems.