JISE


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


Journal of Information Science and Engineering, Vol. 8 No. 2, pp. 187-206


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 - nlog2nn}) 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

  Retrieve PDF document (JISE_199202_02.pdf)