In this paper, we analyze the minimum acceptable bandwidths for networks performing communication for barrier synchronization. We relate these critical bandwidths to the variance of the arrival times of the processors participating in the barrier. We propose a new model called the network bandwidth overflow model that can be used for certain algorithms to compute the difference between the time of the last arriving processor and the time at which the barrier completes. A high variance of arrivals enables a very low bandwidth network to service the barrier traffic and adds only a negligible delay to the barrier completion time. Additionally, there is negligible delay in barrier completion for network bandwidths above a critical bandwidth. The major characteristics of the network bandwidth model are: barrier arrivals are modeled with a normal distribution, messages announcing arrivals receive sequential service by the synchronization network, and these messages are broadcast to all processors.