File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Optimal gossiping in paths and cycles

TitleOptimal gossiping in paths and cycles
Authors
KeywordsAnalysis of algorithms
Gossiping
Information dissemination
Interconnection networks
Issue Date2003
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/jda
Citation
Journal Of Discrete Algorithms, 2003, v. 1 n. 5-6, p. 461-475 How to Cite?
AbstractIn the gossiping problem, each node in a network possesses a token initially; after gossiping, every node has a copy of every other node's token. 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 a packet is of limited size (a packet can hold up to p tokens), 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). We study the path and the cycle which are essential building blocks for more complex structures. We present tight lower bounds and algorithms which match them. The results also lead to the conclusion that p = 2 is the optimal packet size. © 2003 Elsevier B.V. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/89136
ISSN
2015 SCImago Journal Rankings: 0.764
References

 

DC FieldValueLanguage
dc.contributor.authorLau, FCMen_HK
dc.contributor.authorZhang, SHen_HK
dc.date.accessioned2010-09-06T09:52:50Z-
dc.date.available2010-09-06T09:52:50Z-
dc.date.issued2003en_HK
dc.identifier.citationJournal Of Discrete Algorithms, 2003, v. 1 n. 5-6, p. 461-475en_HK
dc.identifier.issn1570-8667en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89136-
dc.description.abstractIn the gossiping problem, each node in a network possesses a token initially; after gossiping, every node has a copy of every other node's token. 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 a packet is of limited size (a packet can hold up to p tokens), 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). We study the path and the cycle which are essential building blocks for more complex structures. We present tight lower bounds and algorithms which match them. The results also lead to the conclusion that p = 2 is the optimal packet size. © 2003 Elsevier B.V. All rights reserved.en_HK
dc.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/jdaen_HK
dc.relation.ispartofJournal of Discrete Algorithmsen_HK
dc.rightsJournal of Discrete Algorithms. Copyright © Elsevier BV.en_HK
dc.subjectAnalysis of algorithmsen_HK
dc.subjectGossipingen_HK
dc.subjectInformation disseminationen_HK
dc.subjectInterconnection networksen_HK
dc.titleOptimal gossiping in paths and cyclesen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1570-8667&volume=1&issue=5-6&spage=461&epage=475&date=2003&atitle=Optimal+gossiping+in+paths+and+cyclesen_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/S1570-8667(03)00038-8en_HK
dc.identifier.scopuseid_2-s2.0-24944516464en_HK
dc.identifier.hkuros92487en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-24944516464&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume1en_HK
dc.identifier.issue5-6en_HK
dc.identifier.spage461en_HK
dc.identifier.epage475en_HK
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridLau, FCM=7102749723en_HK
dc.identifier.scopusauthoridZhang, SH=36509474900en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats