Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
The Expected Duration of Sequential Gossiping
verfasst von : Hans van Ditmarsch, Ioannis Kokkinis
Erschienen in: Multi-Agent Systems and Agreement Technologies
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
A gossip protocol aims at arriving, by means of point-to-point communications (or telephone calls), at a situation in which every agent knows all the information initially present in the network. If it is forbidden to have more than one call at the same time, the protocol is called sequential. We generalise a method, that originates from the famous coupon collector’s problem and that was proposed by John Haigh in 1981, for bounding the expected duration of sequential gossip protocols. We give two examples of protocols where this method succeeds and two examples of protocols where this method fails to give useful bounds. Our main contribution is that, although Haigh originally applied this method in a protocol where any call is available at any moment, we show that this method can be applied in protocols where the number of available calls is decreasing. Furthermore, for one of the protocols where Haigh’s method fails we were able to obtain lower bounds for the expectation using results from random graph theory.