Optimal communication algorithms for hypercubes

D. P. Bertsekas, C. Özveren, G. D. Stamoulis, P. Tseng, J. N. Tsitsiklis

Research output: Contribution to journalArticlepeer-review

94 Scopus citations


We consider the following basic communication problems in a hypercube network of processors: the problem of a single processor sending a different packet to each of the other processors, the problem of simultaneous broadcast of the same packet from every processor to all other processors, and the problem of simultaneous exchange of different packets between every pair of processors. The algorithms proposed for these problems are optimal in terms of execution time and communication resource requirements; that is, they require the minimum possible number of time steps and packet transmissions. In contrast, algorithms in the literature are optimal only within an additive or multiplicative factor.

Original languageEnglish (US)
Pages (from-to)263-275
Number of pages13
JournalJournal of Parallel and Distributed Computing
Issue number4
StatePublished - Apr 1991
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'Optimal communication algorithms for hypercubes'. Together they form a unique fingerprint.

Cite this