BROADCAST COMMUNICATIONS AND DISTRIBUTED ALGORITHMS.

被引：49

作者：

Dechter, Rina ^{[1
]}

Kleinrock, Leonard ^{[1
]}

机构：

[1] Univ of California, Los Angeles, CA,, USA, Univ of California, Los Angeles, CA, USA

来源：

IEEE Transactions on Computers | 1986年 / C-35卷 / 03期

关键词：

BROADCASTING - COMPUTER PROGRAMMING - Algorithms;

D O I：

10.1109/TC.1986.1676745

中图分类号：

学科分类号：

摘要：

A discussion is presented of ways in which one can use 'broadcast communication' in distributed algorithms and of the relevant issues of design and complexity. The authors present an algorithm for merging k sorted lists of n/k elements using k processors and prove its worst case complexity to be 2n, regardless of the number of processors, while neglecting the cost arising from possible conflicts on the broadcast channel. They also show that this algorithm is optimal under single-channel broadcast communication. In a variation of the algorithm, they show that by using an extra local memory of O(k), the number of broadcasts is reduced to n. When the algorithm is used for sorting n elements with k processors, where each processor sorts its own list first, and then merging, it has a complexity of O(n/k log(n/k) plus n and is thus asymptotically optimal for large n. The cost incurred by the channel access scheme is discussed, and it is proved that resolving conflicts whenever k processors are involved introduces a cost factor of at least log k.

引用

页码：210 / 219