Advanced Teleprocessing Systems
Semiannual technical rept.
CALIFORNIA UNIV LOS ANGELES DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
This report consists of two reprints 1 Distributed Systems Growth of distributed systems has attained unstopable momentum. If we better understood how to think about, analyze, and design distributed systems, we could direct their implementation with more confidence. 2 Broadcast Communications and Distributed Algorithms The paper addresses ways in which one can use broadcast communication in distributed algorithms and the relevant issues of design and complexity. We present an algorithm for merging k sorted lists of nk 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. We also show that this algorithm is optimal under single-channel broadcast communication. In a variation of the algorithm we 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 Onk log nk n, and is thus asymptotically optimal for large n. We also discuss the cost incurred by the channel access scheme and prove that resolving conflicts whenever k processors are involved introduces a cost factor of at least logk.
- Computer Hardware
- Computer Systems