Example of two ways (simple way, better way) to do a broadcast.
Simple approach: One process broadcasts the same message to all the other processes, one at a time.
Smarter approach: Let other processes help propagate the message. In the first step, process 1 sends the message to process 2. In the second step, both processes can now participate: process 1 sends to process 3, while process 2 sends to process 4. Similarly, by the third step, four processes (1, 3, 2, and 4) are sending the message to the four remaining processes (5, 6, 7, and 8).
Solid line: data transfer
Dotted line: carry-over from previous transfer
Amount of data transferred: (N-1)*p
N = number of processes
p = size of message
Number of steps: log2N
Compare the number of steps in the two approaches:
Simple approach: N-1
Smarter approach: log2N
The latter scales better as N increases.
