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

Using Conflicts to Derive Efficient Algorithms on the

Single-Channel Broadcast Communication Model

**Chuan Yi Tang and Yuh Hann Liang**

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* - *n*log_{2}*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.