AVERAGE-CASE "MESSY" BROADCASTING
Chenkuan Li, Thomas E. Hart, Kevin J. Henry, IAN A. NEUFELD · Journal of Interconnection Networks · 2008
Current studies of "messy" broadcasting have so far concentrated on finding worst-case times. However, such worst-case scenarios are extremely unlikely to occur in general. Hence, determining average-case times or tight upper bounds for completing "messy" broadcasting in various network topologies is both necessary and meaningful in practice. In this paper, we focus on seeking the average-case "messy" broadcast times of stars, paths, cycles, and d-ary trees, and finding good upper bounds for hypercubes. Finally, we derive a recursive formula to express the average-case time for a specific "messy" broadcast model on a complete graph using a classical occupancy problem in probability theory, and provide a nice simulation result which indicates that this model behaves like classical broadcasting.