Time-optimal gossip of large packets in noncombining 2D tori and meshes
Michal Šoch, Pavel Tvrdı́k · IEEE Transactions on Parallel and Distributed Systems · 1999
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/spl times/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 for at most three packets. The gossip algorithm for meshes requires routers with auxiliary buffers for O(m+n) packets.