Abstract | ||
---|---|---|
We consider the broadcasting operation in point-to-point packet-switched parallel and distributed networks of processors. We develop a general technique for the design of optimal broadcast algorithms on a wide range of such systems. Our technique makes it easier to design such algorithms and, furthermore, provides tools that can be used to derive precise analyses of their running times. As direct applications of this method we give an exact analysis of a known algorithm for the POSTAL model, and design and analyze an optimal broadcast algorithm for the MULTI PORT MULTI-MEDIA model. We then show how our method can be applied to networks with different underlying topologies, by designing and giving an exact analysis of an optimal broadcast algorithm for the OPTICAL RING. |
Year | DOI | Venue |
---|---|---|
1997 | 10.1016/S0166-218X(99)00107-9 | Discrete Applied Mathematics |
Keywords | Field | DocType |
postal model,broadcasting operation,general technique,optimal broadcast algorithm,optimal point-to-point broadcast algorithm,multi port multi-media model,known algorithm,optical ring,lopsided tree,precise analysis,exact analysis,different underlying topology,parallel algorithms,point to point,distributed algorithms,computer science,network topology,algorithm design and analysis,packet switching,message passing | Broadcast algorithm,Broadcasting,Discrete mathematics,Computer science,Parallel algorithm,Algorithm,Network topology,Distributed algorithm,Packet switching,Point-to-point,Message passing,Distributed computing | Conference |
Volume | Issue | ISSN |
93 | 2 | Discrete Applied Mathematics |
ISBN | Citations | PageRank |
0-8186-8037-7 | 6 | 0.56 |
References | Authors | |
15 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mordecai J. Golin | 1 | 13 | 1.73 |
Assaf Schuster | 2 | 6 | 1.91 |