Methods and problems of communication in usual networks (Q1339884)

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.