Distributed algorithms in synchronous broadcasting networks. (English) Zbl 0612.68006
Automata, languages and programming, 12th Colloq., Nafplion/Greece 1985, Lect. Notes Comput. Sci. 194, 363-372 (1985).
[For the entire collection see Zbl 0563.00018.]
In the paper a synchronous broadcasting network, a distributed computation model which represents communication networks, is considered. The problem investigated 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.
Immediate algorithms which solves this problem there are presented.
There are proved lower bounds for the problem and suggested 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 comparison between different models of distributed computation.
In the paper a synchronous broadcasting network, a distributed computation model which represents communication networks, is considered. The problem investigated 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.
Immediate algorithms which solves this problem there are presented.
There are proved lower bounds for the problem and suggested 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 comparison between different models of distributed computation.
Reviewer: J.Just
MSC:
68N99 | Theory of software |
68W99 | Algorithms in computer science |
68Q25 | Analysis of algorithms and problem complexity |
03D60 | Computability and recursion theory on ordinals, admissible sets, etc. |
68P10 | Searching and sorting |
68U20 | Simulation (MSC2010) |
94A05 | Communication theory |