The polling primitive for hypercube networks

We describe a distributed computing primitive termed polling that is both a means of synchronization and communication in distributed or concurrent systems. The polling operation involves the collection of messages from nodes in an interconnection network, in response to a query. We define the semantics of polling, and present algorithms for implementing the operation on hypercube networks. Time and message lower bounds are presented, and is followed by an analysis of the number of operations performed at each node for each of the different algorithms. We then present empirical results and discuss the characteristics of each algorithm in relation to observed performance.