Optimal computation of census functions in the postal model

Amotz Bar-Noy, Shlomo Kipnis, Baruch Schieber

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

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 languageEnglish (US)
Pages (from-to)213-222
Number of pages10
JournalDiscrete Applied Mathematics
Volume58
Issue number3
DOIs
StatePublished - Apr 7 1995
Externally publishedYes

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

Fingerprint Dive into the research topics of 'Optimal computation of census functions in the postal model'. Together they form a unique fingerprint.

Cite this