Show simple item record

dc.contributor.authorGiakkoupis, Georgeen
dc.contributor.authorMallmann-Trenn, Frederiken
dc.contributor.authorSaribekyan, Hayken
dc.date.accessioned2019-07-17T23:30:31Z
dc.date.available2019-07-17T23:30:31Z
dc.date.issued2019-07-16en
dc.identifier.isbn9781450362177en
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/294733
dc.description.abstractWe study the problem of randomized information dissemination in networks. We compare the now standard push-pull protocol, with agent-based alternatives where information is disseminated by a collection of agents performing independent random walks. In the visit-exchange protocol, both nodes and agents store information, and each time an agent visits a node, the two exchange all the information they have. In the meet-exchange protocol, only the agents store information, and exchange their information with each agent they meet. We consider the broadcast time of a single piece of information in an n-node graph for the above three protocols, assuming a linear number of agents that start from the stationary distribution. We observe that there are graphs on which the agent-based protocols are significantly faster than push-pull, and graphs where the converse is true. We attribute the good performance of agent-based algorithms to their inherently fair bandwidth utilization, and conclude that, in certain settings, agent-based information dissemination, separately or in combination with push-pull, can significantly improve the broadcast time. The graphs considered above are highly non-regular. Our main technical result is that on any regular graph of at least logarithmic degree, push-pull and visit-exchange have the same asymptotic broadcast time. The proof uses a novel coupling argument which relates the random choices of vertices in push-pull with the random walks in visit-exchange. Further, we show that the broadcast time of meet-exchange is asymptotically at least as large as the other two's on all regular graphs, and strictly larger on some regular graphs. As far as we know, this is the first systematic and thorough comparison of the running times of these very natural information dissemination protocols.
dc.description.sponsorshipThe authors would like to thank Thomas Sauerwald and Nicol\'{a}s Rivera for helpful discussions. This research was undertaken, in part, thanks to funding from the ANR Project PAMELA (ANR-16-CE23-0016-01), the NSF Award Numbers CCF-1461559, CCF-0939370 and CCF-18107, the Gates Cambridge Scholarship programme, and the ERC grant DYNAMIC MARCH.
dc.publisherAssociation for Computing Machinery (ACM)
dc.rightsPublisher's own licence
dc.rights.uri
dc.titleHow to Spread a Rumoren
dc.typeConference Object
prism.publicationDate2019en
prism.publicationNameProceedings of the 2019 ACM Symposium on Principles of Distributed Computingen
dc.identifier.doi10.17863/CAM.41836
dcterms.dateAccepted2019-05-05en
rioxxterms.versionofrecord10.1145/3293611.3331622en
rioxxterms.versionVoR
rioxxterms.licenseref.urihttp://www.rioxx.net/licenses/all-rights-reserveden
rioxxterms.licenseref.startdate2019-07-16en
dc.contributor.orcidSaribekyan, Hayk [0000-0002-7872-8005]
rioxxterms.typeConference Paper/Proceeding/Abstracten
pubs.funder-project-idECH2020 EUROPEAN RESEARCH COUNCIL (ERC) (679660)
cam.issuedOnline2019-07-29en
pubs.conference-namePODC '19: ACM Symposium on Principles of Distributed Computingen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record