Distributed Algorithms in Synchronous Broadcasting Networks

Title:

Distributed Algorithms in Synchronous Broadcasting Networks

Author(s):

Galil, Zvi
Landau, Gad M.
Yung, Moti

Date:

1985

Type:

Technical reports

Department:

Computer Science

Permanent URL:

http://hdl.handle.net/10022/AC:P:11702

Series:

Columbia University Computer Science Technical Reports

Part Number:

CUCS18085

Publisher:

Department of Computer Science, Columbia University

Publisher Location:

New York

Abstract:

In this paper we consider a synchronous broadcasting network, a distributed computation model which represents communication networks that are used extensively in practice. This is the first work we know of that deals with this model in a theoretical context. The problem we consider is a basic problem of information sharing, the computation of the multiple identification function. That is, given a network of p processors, each of which contains an nbit string of information, the question is how every processor can compute the subset of processors which have the same information as itself. The problem was suggested by Yao in his classical paper in communication complexity [17], as a generalization of the twoprocessor case studied in that paper. The immediate algorithm which solves this problem takes O(np) time (time = communication time in bits, which is our complexity measure). We present the following algorithms:  a. An algorithm which takes advantage of properties of strings, uses a very simple scheduling policy, and does not use arithmetic operations. (In fact, the processor can be a Turing machine). 'the algorithm's complexity is O(nlog2p+p).  b. An algorithm which uses a simulation of sorting networks by the distributed system. If t(p) is the depth of the sorting network of p processors, then our algorithm takes O( n t(p) + p) time. Using recent results on sorting networks we get an O(nlogp+p) (impractical) algorithm. The algorithm also uses addition and subtraction operations. c. By letting the processor use modular arithmetic operations as well, we can use Yao's probabilistic version, modify our algorithms and get probabilistic algorithms (with small error) where logn replaces n in the complexity expressions. To prove lower bounds for the problem we use Yao's result to get an fl(n) bound, and we also show an fl(p) bound. We suggest open problems concerning new techniques for proving lower bounds in the presence of broadcasting, as well as other problems about efficient use of the model and comparisons between different models of distributed computation.

Subject(s):

Computer science
 Item views:

208
 Metadata:

text  xml