AN OPTIMAL ALGORITHM FOR COMPUTING CENSUS FUNCTIONS IN MESSAGE-PASSING SYSTEMS

Abstract
We consider a message-passing system of n processors, each of which initially holds one piece of data. The goal is to compute an associative and commutative census function f on the n distributed pieces of data and to make the result known to all processors. To perform the computation, processors communicate with each other by sending and receiving messages in specified communication rounds. We describe an optimal algorithm for this problem that requires the least number of communication rounds and that minimizes the time spent by any processor in sending and receiving messages.