In this paper, we propose a new concept, the conflict-based algorithm, to derive efficient algorithms under the single-channel broadcast communication model. In proevious researches, conflict was regarded as a problem. Researchers have tried to resolve it , or to design conflict-free algorithms. Actually, conflict is not bad, because it also provides some useful information. Using conflict in fromation, we have designed algorithms to solve three problems: the maxima finding problem, the data ranking problem, and the data reporting problem. At present, the best algorithms for the above problems require O(nL)time, where n is the number of processors and L is bit length of data. Our algorithms take only O(L) to solve the maxima finding problem, and O(max{nL - nlog₂n, n}) to solve the other two problems.

Keywords: distributed computing, parallel algorithms, single-channel broadcast communication model, conflict, maxima finding problem, data ranking problem, data reporting problem

Received July 19, 1991; revised January 6, 1992.
Communicated by Ferng-Ching Lin.