1985 Reports

Distributed Algorithms in Synchronous Broadcasting Networks

Galil, Zvi; Landau, Gad M.; Yung, Moti

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 n-bit 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 two-processor 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.