On the time complexity of broadcast communication schemes (Preliminary Version)
Albert G. Greenberg · 1982
In this paper, we investigate the power of such broadcast in solving a paradigmatic problem in distributed computing. Imagine a network in which each node machine Ni (1≤i≤n) keeps a Boolean value vi in local memory. The vi 's determine a set S={i: vi=1}. The non-emptiness problem on n nodes is to find some i in S, or else find that S is empty. In practice, a problem of this type arises in two ways: