Advertisement
Published in:
2018 | OriginalPaper | Chapter
The Expected Duration of Sequential Gossiping
Authors : Hans van Ditmarsch, Ioannis Kokkinis
Published in: Multi-Agent Systems and Agreement Technologies
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.