Line broadcasting in cycles
| Autor: | Jave O. Kane, Joseph G. Peters |
|---|---|
| Jazyk: | angličtina |
| Předmět: |
Scheme (programming language)
021103 operations research Computer science business.industry Node (networking) Distributed computing Applied Mathematics Minimum time 0211 other engineering and technologies Process (computing) 0102 computer and information sciences 02 engineering and technology Broadcasting 01 natural sciences 010201 computation theory & mathematics Broadcast communication network Computer Science::Networking and Internet Architecture Discrete Mathematics and Combinatorics Line (text file) business computer computer.programming_language Computer network Computer Science::Information Theory |
| Zdroj: | Discrete Applied Mathematics. (1-3):207-228 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/S0166-218X(97)00111-X |
| Popis: | Broadcasting is the process of transmitting information from an originating node (processor) in a network to all other nodes in the network. A local broadcast scheme only allows a node to send information along single communication links to adjacent nodes, while a line broadcast scheme allows nodes to use paths of several communication links to call distant nodes. The minimum time possible for broadcasting in a network of n nodes when no node is involved in more than one communication at any given time is ⌊ log n⌋ phases. Local broadcasting is not sufficient, in general, for broadcasting to be completed in minimum time; line broadcasting is always sufficient. An optimal line broadcast is a minimum-time broadcast that uses the smallest possible total number of communication links. In this paper, we give a complete characterization of optimal line broadcasting in cycles, and we develop efficient methods for constructing optimal line broadcast schemes. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|