File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Optimal gossiping in square 2D meshes

TitleOptimal gossiping in square 2D meshes
Authors
KeywordsAlgorithms
Gossiping
Information dissemination
Meshes
Networks
Issue Date2007
PublisherElsevier 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?
AbstractGossiping 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 Identifierhttp://hdl.handle.net/10722/88964
ISSN
2015 Impact Factor: 0.643
2015 SCImago Journal Rankings: 0.720
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorWang, Ren_HK
dc.contributor.authorLau, FCMen_HK
dc.date.accessioned2010-09-06T09:50:41Z-
dc.date.available2010-09-06T09:50:41Z-
dc.date.issued2007en_HK
dc.identifier.citationTheoretical Computer Science, 2007, v. 384 n. 2-3, p. 263-286en_HK
dc.identifier.issn0304-3975en_HK
dc.identifier.urihttp://hdl.handle.net/10722/88964-
dc.description.abstractGossiping 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.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcsen_HK
dc.relation.ispartofTheoretical Computer Scienceen_HK
dc.rightsTheoretical Computer Science. Copyright © Elsevier BV.en_HK
dc.subjectAlgorithmsen_HK
dc.subjectGossipingen_HK
dc.subjectInformation disseminationen_HK
dc.subjectMeshesen_HK
dc.subjectNetworksen_HK
dc.titleOptimal gossiping in square 2D meshesen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://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+meshesen_HK
dc.identifier.emailLau, FCM:fcmlau@cs.hku.hken_HK
dc.identifier.authorityLau, FCM=rp00221en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/j.tcs.2007.04.032en_HK
dc.identifier.scopuseid_2-s2.0-34548499095en_HK
dc.identifier.hkuros138639en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-34548499095&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume384en_HK
dc.identifier.issue2-3en_HK
dc.identifier.spage263en_HK
dc.identifier.epage286en_HK
dc.identifier.isiWOS:000250387800011-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridWang, R=36072127500en_HK
dc.identifier.scopusauthoridLau, FCM=7102749723en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats