Optimal and Near-Optimal Algorithms fork-Item Broadcast

Research output: Contribution to journalArticlepeer-review


Since many distributed-memory machines rely only on point-to-point com- munication between processors, various broadcast operations must be created using this type of primitive. In this paper we consider the fundamental problem of broadcastingk-items from one processor to all the remaining processors on a parallel machine. Using point-to-point communication and the LogP model, we design an algorithm fork-item broadcast whose running time is within an additive constant of the lower bound. We also present an optimal algorithm fork-item broadcast on a variant of LogP.

Original languageEnglish (US)
Pages (from-to)121-139
Number of pages19
JournalJournal of Parallel and Distributed Computing
Issue number2
StatePublished - May 1999
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 and Near-Optimal Algorithms fork-Item Broadcast'. Together they form a unique fingerprint.

Cite this