๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Optimal and Near-Optimal Algorithms fork-Item Broadcast

โœ Scribed by Eunice E. Santos

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
330 KB
Volume
57
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

โœฆ Synopsis

Since many distributed-memory machines rely only on point-to-point communication between processors, various broadcast operations must be created using this type of primitive. In this paper we consider the fundamental problem of broadcasting k-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 for k-item broadcast whose running time is within an additive constant of the lower bound. We also present an optimal algorithm for k-item broadcast on a variant of LogP.

๐Ÿ“œ SIMILAR VOLUMES

An Optimal Algorithm for Broadcasting Mu
An Optimal Algorithm for Broadcasting Multiple Messages in Trees
โœ Krzysztof Diks; Andrzej Lingas; Andrzej Pelc ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 118 KB

We consider multiple message broadcasting in tree networks. The source (considered as the root of the tree) has k messages which have to be broadcast to all nodes of the tree. In every time unit each node can send one of its already obtained messages to one of its children. A k-message broadcasting

Optimal hierarchical structure of broadc
Optimal hierarchical structure of broadcast network
โœ Takumi Miyoshi; Yoshiaki Tanaka ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 151 KB

With the realization of broadband integrated service digital networks (B-ISDN), broadcast services will occupy a large part of the network traffic. In these services, the same information is distributed to many subscribers through the point-to-multipoint connection paths. This connection form is qui