Time-optimal gossip of large packets in noncombining 2D tori and meshes
The main results of this paper are algorithms for time-optimal gossip of large packets in noncombining full-duplex all-port 2-D tori and meshes of any size m x n. The gossip algorithms define the structure of broadcast trees and lock-step scheduling schemes for packets that make the broadcast trees time-are-disjoint. The gossip algorithm for tori is also buffer-optimal-it requires routers with auxiliary buffers far at most three packets. The gossip algorithm for meshes requires routers with auxiliary buffers for O(m + n) packets.
gossip all-to-all broadcast 2d torus 2d mesh time-arc-disjoint broadcast trees buffer requirements