| Abstract |
|---|
| This paper describes a time-, transmission-, and memory-optimalalgorithm for gossiping in general 2-D tori in the noncombiningfull-duplex and all-port communication model. The algorithm is definedby constructing optimal generic broadcast trees. Since a 2-D torus isvertex-transitive, a generic broadcast tree can be rooted in any vertexof the torus using an automorphism by translation. The set of alltranslations of the generic tree forms a set of time-arc-disjointtrees. The number of rounds of the algorithm matches exactly the lowerbound, every node receives every packet exactly once, and routers needauxiliary buffers for at most 3 packets. This is the first gossipalgorithm for general 2-D tori which requires only constant-sizebuffers. This improves our previous result presented at EuroPar'96 andanswers an open problem stated there. |
| Contact |
| Pavel Tvrdik Department of Comp.Sci.& Engr.,Faculty of Electrical Engineering,Czech Technical University,Karlovo nam. 13, 12135 Praha 2,Czech Republic , tvrdik@sun.felk.cvut.cz |