Abstract
We consider the problem of computing a census function among n processors in a message-passing system. In this problem, each of the n processors holds one piece of data initially. The goal is to compute an associative and commutative census function h on the n distributed pieces of data and to make the result known to all the processors. To perform the computation, processors send messages to and receive messages from one another in specified communication rounds. To model the communication latencies inherent in many modern message-passing systems, we use the postal model which was recently introduced by Bar-Noy and Kipnis. In this model, a message sent by one processor in a given round is received by another processor only several rounds later. This paper describes an optimal algorithm for the census problem in the postal model. The algorithm requires the least number of communication rounds and minimizes the time spent by each processor in sending and receiving messages.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 213-222 |
| Number of pages | 10 |
| Journal | Discrete Applied Mathematics |
| Volume | 58 |
| Issue number | 3 |
| DOIs | |
| State | Published - Apr 7 1995 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Applied Mathematics
Keywords
- Census computation
- Combining algorithms
- Distributed systems
- Gossiping
- Message-passing systems
- Parallel computers
- Postal model