Author Description

This dissertation, "Gossiping in Meshes in All-port Mode and With Short Packets" by Rui, Wang,, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: Abstract of thesis entitled "Gossiping in Meshes in All-Port Mode and with Short Packets" Submitted by Rui Wang for the degree of Doctor of Philosophy at The University of Hong Kong in May 2006 Gossiping is the communication problem in which each node has a unique mes- sage to be transmitted to every other node. The nodes exchange their message by packets. A solution to the problem is judged by how many rounds of packet sending it requires. In this thesis, we consider the version of the problem in which small-size packets each carrying exactly one message are used. The nodes of the target meshes are assumed to be all-port (a node's incident edges can all be active at the same time); and their edges are either half-duplex or full- duplex, also known as the H* model and the F* model respectively. We study ˘ the class of 2D meshes. Soch and Tvrdik (SIROCCO'97, pp. 253-265; Tech. rep. DC-97-04, Dept. of CS&E, Czech Technical University) have obtained optimal algorithms for the F* model (for square or nonsquare meshes). Lau and Zhang (IEEE Trans. on Parallel and Distributed Systems Vol. 13, No. 4, pp. 349-358, 2002) have obtained fast algorithms for the H* model. We present optimal algorithms for square meshes under both models, and a fast algorithm for general 2D meshes under the H* model. All of these algorithms route mes- sages along the shortest paths. Note that for the F* model, although Soch and Tvrdik have optimally solved the problem, we present yet ano