A two‐step mutual multicast technique for n‐to‐n communication
Amane Nakajima · Systems and Computers in Japan · 1993
Abstract Mutual multicast is a communication pattern in which each node in a group sends a message to any other node in that group. This n‐to‐n communication pattern is required in various cases of distributed processing, and an efficient realization of the pattern is needed. This paper proposes a two‐stage mutual multicast technique in which mutual multicast is executed by two stages of the submulticasts through distributed control. Ordinary mutual multicast is executed in one stage. But two‐stage multicast can carry out a communication with fewer messages and in a shorter time if the submulticast destination node sets are approximately set in each stage. When there are n nodes, single‐stage multicast requires n(n‐1) messages and a time of 2(n‐1) if all communications are carried out as one‐to‐one message communications; but two‐stage mutual multicast requires only 2n⌈√n⌉ and a time of 4⌈√n⌉. In LANs, such as Ethernet, the multicast function is provided by the MAC sublayer. When this function is available, the two‐stage mutual multicast procedure can carry out a communication in a time of 2(⌈√n⌉+1), which compared with a time n in single‐stage mutual multicast.