Optimal scheme for disseminating information

An optimal communication pattern is presented that achieves complete dissemination of information among n machines in log n time by repeated use of point-to-point messages. This scheme improves previous results in this field by removing restrictions on n (it need not be a power of 2) and by introducing reorganization to tolerate single-machine faults. Although present data-dissemination algorithms are described for point-to-point networks, they are also suited to multimachine organizations with broadcast media such as token-ring network and ethernets.