Optimal broadcasting with universal lists based on competitive analysis

In this article we study a variant of broadcasting: each node has a predetermined ordered list of neighbors regardless of the node, called the source, from which the originating message is transmitted to all nodes in a network. Each node transmits a received message to its neighbors in order of the...

Full description

Saved in:
Bibliographic Details
Published in:Networks 2005-07, Vol.45 (4), p.224-231
Main Authors: Kim, Jae-Hoon, Chwa, Kyung-Yong
Format: Article
Language:English
Subjects:
Applied sciences
broadcasting
competitive analysis
complete graph
Computer science
control theory
systems
Computer systems and distributed systems. User interface
Exact sciences and technology
grid
hypercube
Software
tree
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this article we study a variant of broadcasting: each node has a predetermined ordered list of neighbors regardless of the node, called the source, from which the originating message is transmitted to all nodes in a network. Each node transmits a received message to its neighbors in order of the list. We propose a new measure of the efficiency of a Broadcasting scheme, which is obtained from competitive analysis, and we design new broadcasting schemes for lines, complete k‐ary trees, grids, complete graphs, and hypercubes. In particular, we provide optimal broadcasting schemes for lines and grids. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(4), 224–231 2005
ISSN:0028-3045
1097-0037
DOI:10.1002/net.20068