File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1016/j.tcs.2007.04.032
- Scopus: eid_2-s2.0-34548499095
- WOS: WOS:000250387800011
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Optimal gossiping in square 2D meshes
Title | Optimal gossiping in square 2D meshes |
---|---|
Authors | |
Keywords | Algorithms Gossiping Information dissemination Meshes Networks |
Issue Date | 2007 |
Publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs |
Citation | Theoretical Computer Science, 2007, v. 384 n. 2-3, p. 263-286 How to Cite? |
Abstract | Gossiping is the communication problem in which each node has a unique message 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 paper, 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, which are also known as the H* model and the F* model, respectively. We study the class of 2D square 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. Parallel Distribut. Syst. 13 (4) (2002) 349-358) have obtained fast algorithms for the H* model. We present optimal algorithms for both models, with the interesting property that they route their messages along the same paths and in the same order, i.e. for any edge {u, v}, the i-th message from u to v under either model is the same message. © 2007 Elsevier Ltd. All rights reserved. |
Persistent Identifier | http://hdl.handle.net/10722/88964 |
ISSN | 2023 Impact Factor: 0.9 2023 SCImago Journal Rankings: 0.570 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Wang, R | en_HK |
dc.contributor.author | Lau, FCM | en_HK |
dc.date.accessioned | 2010-09-06T09:50:41Z | - |
dc.date.available | 2010-09-06T09:50:41Z | - |
dc.date.issued | 2007 | en_HK |
dc.identifier.citation | Theoretical Computer Science, 2007, v. 384 n. 2-3, p. 263-286 | en_HK |
dc.identifier.issn | 0304-3975 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/88964 | - |
dc.description.abstract | Gossiping is the communication problem in which each node has a unique message 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 paper, 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, which are also known as the H* model and the F* model, respectively. We study the class of 2D square 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. Parallel Distribut. Syst. 13 (4) (2002) 349-358) have obtained fast algorithms for the H* model. We present optimal algorithms for both models, with the interesting property that they route their messages along the same paths and in the same order, i.e. for any edge {u, v}, the i-th message from u to v under either model is the same message. © 2007 Elsevier Ltd. All rights reserved. | en_HK |
dc.language | eng | en_HK |
dc.publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs | en_HK |
dc.relation.ispartof | Theoretical Computer Science | en_HK |
dc.rights | Theoretical Computer Science. Copyright © Elsevier BV. | en_HK |
dc.subject | Algorithms | en_HK |
dc.subject | Gossiping | en_HK |
dc.subject | Information dissemination | en_HK |
dc.subject | Meshes | en_HK |
dc.subject | Networks | en_HK |
dc.title | Optimal gossiping in square 2D meshes | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0304-3975&volume=384&spage=263&epage=286&date=2007&atitle=Optimal+gossiping+in+square+2D+meshes | en_HK |
dc.identifier.email | Lau, FCM:fcmlau@cs.hku.hk | en_HK |
dc.identifier.authority | Lau, FCM=rp00221 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1016/j.tcs.2007.04.032 | en_HK |
dc.identifier.scopus | eid_2-s2.0-34548499095 | en_HK |
dc.identifier.hkuros | 138639 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-34548499095&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 384 | en_HK |
dc.identifier.issue | 2-3 | en_HK |
dc.identifier.spage | 263 | en_HK |
dc.identifier.epage | 286 | en_HK |
dc.identifier.isi | WOS:000250387800011 | - |
dc.publisher.place | Netherlands | en_HK |
dc.identifier.scopusauthorid | Wang, R=36072127500 | en_HK |
dc.identifier.scopusauthorid | Lau, FCM=7102749723 | en_HK |
dc.identifier.issnl | 0304-3975 | - |