Optimal multiple message broadcasting in telephone-like communication systems

Amotz Bar-Noy, Shlomo Kipnis, Baruch Schieber

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

We consider the problem of broadcasting multiple messages from one processor to many processors in telephone-like communication systems. In such systems, processors communicate in rounds, where in every round, each processor can communicate with exactly one other processor by exchanging messages with it. Finding an optimal solution for this problem was open for over a decade. In this paper, we present an optimal algorithm for this problem when the number of processors is even. For an odd number of processors, we provide an algorithm which is within an additive term of 3 of the optimum. A by-product of our solution is an optimal algorithm for the problem of broadcasting multiple messages for any number of processors in the simultaneous send/receive model. In this latter model, in every round, each processor can send a message to one processor and receive a message from another processor.

Original languageEnglish (US)
Pages (from-to)1-15
Number of pages15
JournalDiscrete Applied Mathematics
Volume100
Issue number1-2
DOIs
StatePublished - Mar 15 2000
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Keywords

  • Broadcasting
  • Communication networks
  • Distributed parallel computers
  • Multiple messages
  • Simultaneous send/receive
  • Telephone systems

Fingerprint

Dive into the research topics of 'Optimal multiple message broadcasting in telephone-like communication systems'. Together they form a unique fingerprint.

Cite this