Previous [1] 2 [3 ] [4 ] [5 ] [6 ] [7 ] [8 ]

Journal of Inforamtion Science and Engineering, Vol.8 No.2, pp.187-206 (June 1992)
Using Conflicts to Derive Efficient Algorithms on the
Single-Channel Broadcast Communication Model

Chuan Yi Tang and Yuh Hann Liang
Department of Computer Science
National Tsing-Hua Unviersity
Hsinchu, Taiwan 300, R.O.C.

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 - nlog2n, 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.