File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Fast gossiping in square meshes/tori with bounded-size packets

TitleFast gossiping in square meshes/tori with bounded-size packets
Authors
Lau, FCMZhang, SH
KeywordsAll-to-all broadcast
Collective communication
Communication optimization
Gossiping
Interconnection networks
Parallel algorithms
Scheduling
Total exchange
Issue Date2002
PublisherI E E E. The Journal's web site is located at http://www.computer.org/tpds
Citation
Ieee Transactions On Parallel And Distributed Systems, 2002, v. 13 n. 4, p. 349-358 How to Cite?
DOI: http://dx.doi.org/10.1109/71.995815
AbstractGossiping is the communication problem in which each node has a unique message (token) to be transmitted to every other node. The nodes exchange their tokens 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 token) are used, the links (edges) of the network are half-duplex (only one packet can flow through a link at a time), and the nodes are all-port (a node's incident edges can all be active at the same time). This is also known as the H* model. We study the 2D square mesh and the 2D square torus. An improved, asymptotically optimal algorithm for the mesh and an optimal algorithm for the torus are presented.
Persistent Identifierhttp://hdl.handle.net/10722/43660
ISSN
1045-9219
2023 Impact Factor: 5.6
2023 SCImago Journal Rankings: 2.340
ISI Accession Number ID
WOS:000174971500002
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorLau, FCMen_HK
dc.contributor.authorZhang, SHen_HK
dc.date.accessioned2007-03-23T04:51:27Z-
dc.date.available2007-03-23T04:51:27Z-
dc.date.issued2002en_HK
dc.identifier.citationIeee Transactions On Parallel And Distributed Systems, 2002, v. 13 n. 4, p. 349-358en_HK
dc.identifier.issn1045-9219en_HK
dc.identifier.urihttp://hdl.handle.net/10722/43660-
dc.description.abstractGossiping is the communication problem in which each node has a unique message (token) to be transmitted to every other node. The nodes exchange their tokens 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 token) are used, the links (edges) of the network are half-duplex (only one packet can flow through a link at a time), and the nodes are all-port (a node's incident edges can all be active at the same time). This is also known as the H* model. We study the 2D square mesh and the 2D square torus. An improved, asymptotically optimal algorithm for the mesh and an optimal algorithm for the torus are presented.en_HK
dc.format.extent350148 bytes-
dc.format.extent26112 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/msword-
dc.languageengen_HK
dc.publisherI E E E. The Journal's web site is located at http://www.computer.org/tpdsen_HK
dc.relation.ispartofIEEE Transactions on Parallel and Distributed Systemsen_HK
dc.rights©2002 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.-
dc.subjectAll-to-all broadcasten_HK
dc.subjectCollective communicationen_HK
dc.subjectCommunication optimizationen_HK
dc.subjectGossipingen_HK
dc.subjectInterconnection networksen_HK
dc.subjectParallel algorithmsen_HK
dc.subjectSchedulingen_HK
dc.subjectTotal exchangeen_HK
dc.titleFast gossiping in square meshes/tori with bounded-size packetsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1045-9219&volume=13&issue=4&spage=349&epage=358&date=2002&atitle=Fast+Gossiping+in+Square+Meshes/Tori+with+Bounded-Size+Packetsen_HK
dc.identifier.emailLau, FCM:fcmlau@cs.hku.hken_HK
dc.identifier.authorityLau, FCM=rp00221en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1109/71.995815en_HK
dc.identifier.scopuseid_2-s2.0-0036530146en_HK
dc.identifier.hkuros71113-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0036530146&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume13en_HK
dc.identifier.issue4en_HK
dc.identifier.spage349en_HK
dc.identifier.epage358en_HK
dc.identifier.isiWOS:000174971500002-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridLau, FCM=7102749723en_HK
dc.identifier.scopusauthoridZhang, SH=7409369263en_HK
dc.identifier.citeulike3066588-
dc.identifier.issnl1045-9219-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats