Efficient algorithms for performing packet broadcasts in a mesh network

We consider processors communicating over a mesh network with the objective of broadcasting information among each other, One instance of the problem involves a number of nodes all with the same message to be broadcasted. For that problem, a lower-bound on the time to complete the broadcast, and an algorithm which achieves this bound are presented. In another instance, every node in the mesh has packets to be broadcast arriving independently, according to a Poisson random process, The stability region for performing such broadcasts is characterized, and broadcast algorithms which operate efficiently within that region are presented, These algorithms involve interacting queues whose analysis is known to be very difficult, Toward that end we develop an approximation which models an n-dimensional infinite Markov chain as a single-dimensional infinite Markov chain together with an n-dimensional finite Markov chain. This approximate model can be analyzed and the results compare favorably with simulation.