One-to-many routing on the mesh

We study the routing of messages with multiple destinations on an n-node square mesh (one-to-many routing). The obvious approach of simply replicating each message into the appropriate number of point-to-point messages and routing these independently does not generally yield optimal performance. A standard argument proves that Ω(√n+cm) time is required to route m ≤ n messages, where each message is generated by a distinct node and at most c messages must be delivered to any individual node. The lower bound does not depend on the number of destinations per message. We provide both randomized and deterministic algorithms for one-to-many routing, which use constant-size buffers at each node. The randomized algorithm attains optimal performance, while the deterministic algorithm is slower by a factor of O (log² n). We also describe an optimal deterministic algorithm that, however, requires large buffers of size O (c).