Computing global combine operations in the multi-port postal model

Abstract-Consider a message-passing system of n processors, in which each processor holds one piece of data initially. The goal is to compute an associative and commutative reduction function on the n pieces of data and to make the result known to all the n processors. This operation is frequently used in many message-passing systems and is typically referred to as global combine, census computation, or gossiping. This paper explores the problem of global combine in the multiport postal model. This model is characterized by three parameters: n-the number of processors, k-the number of ports per processor, and &the com-munication latency. In this model, in every round r, each processor can send k distinct messages to k other processors, and it can receive k mes-sages that were sent from k other processors 1- 1 rounds earlier. This paper provides an optimal algorithm for the global combine problem that requires the least number of communication rounds and minimizes the time spent by any processor in sending and receiving messages. Index Terms-Census computation, distributed systems, global com-bine, gossiping, message-passing systems, multiple ports, parallel com-puters, postal model. I