Show simple item record

dc.contributor.authorBerenbrink, Pen
dc.contributor.authorElsässer, Ren
dc.contributor.authorSauerwald, Thomasen
dc.date.accessioned2019-06-26T09:35:30Z
dc.date.available2019-06-26T09:35:30Z
dc.date.issued2014-02-06en
dc.identifier.issn0304-3975
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/294029
dc.description.abstractIn this paper we analyse broadcasting in d-regular networks with good expansion properties. For the underlying communication, we consider modifications of the so-called random phone call model. In the standard version of this model, each node is allowed in every step to open a channel to a randomly chosen neighbour, and the channels can be used for bi-directional communication. Then, broadcasting on the graphs mentioned above can be performed in time O(logn), where n is the size of the network. However, every broadcast algorithm with runtime O(logn) needs on average Ω(logn/logd) message transmissions per node for random graphs with expected degree d [11]. In this paper we show that it is possible to save significantly on communications if the standard model is modified such that nodes can avoid opening channels to exactly the same neighbours in two consecutive steps. We consider the so-called Rr model where we assume that every node has a cyclic list of all of its neighbours, ordered in a random way. Then, in step i the node communicates with the i-th neighbour from that list. We provide an O(√logn) time algorithm which produces in average O(logn) transmissions per node in networks with suitably defined expansion properties. Furthermore, we present a related lower bound of Ω(√logn/loglogn) for the average number of message transmissions. These results show that by using memory it is possible to reduce the number of transmissions per node by almost a quadratic factor. Crown Copyright © 2013 Published by Elsevier B.V. All rights reserved.
dc.publisherElsevier
dc.titleRandomised broadcasting: Memory vs. randomnessen
dc.typeArticle
prism.endingPage42
prism.publicationDate2014en
prism.publicationNameTheoretical Computer Scienceen
prism.startingPage27
prism.volume520en
dc.identifier.doi10.17863/CAM.15559
dcterms.dateAccepted2013-08-19en
rioxxterms.versionofrecord10.1016/j.tcs.2013.08.011en
rioxxterms.versionVoR*
rioxxterms.licenseref.urihttp://www.rioxx.net/licenses/all-rights-reserveden
rioxxterms.licenseref.startdate2014-02-06en
rioxxterms.typeJournal Article/Reviewen
cam.issuedOnline2013-08-28en
dc.identifier.urlhttps://www.sciencedirect.com/science/article/pii/S0304397513006087?via%3Dihub#!en


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record