Methods and problems of communication in usual networks
type: Item
instance of: scholarly article
title: Methods and problems of communication in usual networks
zbMATH Open document ID: 0818.94029
DOI: 10.1016/0166-218X(94)90180-5
author: Pierre Fraigniaud
author: Emmanuel Lazard
published in: Discrete Applied Mathematics
publication date: 1995-08-28T00:00:00Z
review text: This paper surveys results on some communication problems in processor networks. In particular, the following problems are considered: broadcasting (i.e. sending a message from one processor to all other ones), gossiping (i.e. each processor is the source of a broadcast), scattering (i.e. one processor sends a different message to each other processor), and multiscattering (i.e. each processor is the source of a scattering). Each of these problems is studied with respect to 1. the network topology, 2. the communication mode of the links -- full-duplex or half-duplex --, 3. the model for communication time -- constant time or linear time --, and 4. the number of neighbours a processor can communicate with at the same time. Moreover, references to other communication problems are given. The paper concludes with a list of open problems. It should be noted that some of the results in this paper are new.
Mathematics Subject Classification ID: 94C15
Mathematics Subject Classification ID: 94-02
Mathematics Subject Classification ID: 94A05
Mathematics Subject Classification ID: 05C90
zbMATH DE Number: 701699
zbMATH Keywords: processor networks
zbMATH Keywords: broadcasting
zbMATH Keywords: gossiping
zbMATH Keywords: scattering
zbMATH Keywords: multiscattering
reviewed by: Martin Middendorf
MaRDI profile type: Publication
cites work: Q3197858
cites work: Décomposition de la somme cartesienne d'un cycle et de l'union de deux cycles hamiltoniens en cycles hamiltoniens
cites work: Q3796744
cites work: Potential function analysis of greedy hot-potato routing
cites work: Data transfers in broadcast networks
cites work: Multiple Communication in Multihop Radio Networks
cites work: Q5615282
cites work: Broadcasting and Gossiping in de Bruijn Networks
cites work: Antepenultimate broadcasting
cites work: Broadcasting in Bounded Degree Graphs
cites work: Q3793717
cites work: Broadcasting in wraparound meshes with parallel monodirectional links
cites work: Q3827949
cites work: On bufferless routing of variable length messages in leveled networks
cites work: Q4694740
cites work: Finding the roots of a polynomial on an MIMD multicomputer
cites work: Gossiping in Minimal Time
cites work: Deadlock-Free Message Routing in Multiprocessor Interconnection Networks
cites work: Gossips and telegraphs
cites work: Optimal algorithms for total exchange without buffering on the hypercube
cites work: Q3886878
cites work: Bounded-call broadcasting
cites work: Q3864434
cites work: Complexity analysis of broadcasting in hypercubes with restricted communication capabilities
cites work: Interval routing schemes
cites work: Scattering on a ring of processors
cites work: Fast gossiping on square mesh computers
cites work: Broadcasting on recursively decomposable Cayley graphs
cites work: A Cure for the Telephone Disease
cites work: A survey of gossiping and broadcasting in communication networks
cites work: Broadcasting and spanning trees in de Bruijn and Kautz networks
cites work: Q3997411
cites work: Spanning Balanced Trees in Boolean Cubes
cites work: Q3359735
cites work: Q4198056
cites work: Optimum broadcasting and personalized communication in hypercubes
cites work: Broadcasting in butterfly and deBruijn networks
cites work: New gossips and telephones
cites work: Minimum \(k\)-broadcast graphs
cites work: Fast Gossiping for the Hypercube
cites work: Bounds of the number of disjoint spanning trees
cites work: Some minimum gossip graphs
cites work: Information flows on hypergraphs
cites work: Quick gossiping by telegraphs
cites work: Q3972008
cites work: Broadcasting in DMA-bound bounded degree graphs
cites work: Q4002466
cites work: Broadcast Networks of Bounded Degree
cites work: Minimum broadcast digraphs
cites work: Generalizations of broadcasting and gossiping
cites work: Note on the problem of gossiping in multidimensional grids
cites work: Orientations of the n-cube with minimum diameter
cites work: Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
cites work: An Optimal Synchronizer for the Hypercube
cites work: Bounded depth broadcasting
cites work: Optimal total exchange for a 3-D torus of processors
cites work: Efficient routing in all-optical networks
cites work: On the optimal strongly connected orientations of city street graphs. III. Three east–west avenues or north–south streets

Methods and problems of communication in usual networks (cites work)
cites work: On the Optimal Strongly Connected Orientations of City Street Graphs I: Large Grids

Methods and problems of communication in usual networks (cites work)
cites work: On the optimal strongly connected orientations of city street graphs. II: Two east-west avenues or North—South Streets

Methods and problems of communication in usual networks (cites work)
cites work: Data communication in parallel architectures

Methods and problems of communication in usual networks (cites work)
cites work: Comments on broadcast algorithms for two-dimensional grids

Methods and problems of communication in usual networks (cites work)
cites work: An efficient algorithm for multiple simultaneous broadcasts in the hypercube

Methods and problems of communication in usual networks (cites work)
cites work: Broadcasting in the butterfly network

Methods and problems of communication in usual networks (cites work)
cites work: Q4694736

Methods and problems of communication in usual networks (cites work)
cites work: Communication algorithms for isotropic tasks in hypercubes and wraparound meshes

Methods and problems of communication in usual networks (cites work)
cites work: The Communication Complexity of Atomic Commitment and of Gossiping

Methods and problems of communication in usual networks (full work available at URL)
full work available at URL: 0166-218x(94)90180-5

Methods and problems of communication in usual networks (OpenAlex ID)
OpenAlex ID: W2080750094

Methods and problems of communication in usual networks (Wikidata QID)
Wikidata QID: Q127213036