Event Based Systems in Iași

Optimal Epidemic Dissemination​
Dr. Hugues Mercier (Université de Neuchâtel)

• Friday, 24 November 2017, 12:00, C308 (Faculty of Computer Science, C Building, UAIC)—map

We consider the problem of reliable epidemic dissemination of a rumor in a fully connected network of n processes using push and pull operations. We revisit the random phone call model and show that it is possible to disseminate a rumor to all processes with high probability using Θ(ln n) rounds of communication and only n+o(n) messages of size b, all of which are asymptotically optimal and achievable with pull and push-then-pull algorithms. This contradicts two highly-cited lower bounds of Karp et al. stating that any algorithm in the random phone call model running in O(ln n) rounds with communication peers chosen uniformly at random requires at least ω(n) messages to disseminate a rumor with high probability, and that any address-oblivious algorithm needs Ω(n ln ln n) messages regardless of the number of communication rounds. The reason for this contradiction is that in the original work, processes do not have to share the rumor once the communication is established. However, it is implicitly assumed that they always do so in the proofs of their lower bounds, which, it turns out, is not optimal. Our algorithms are strikingly simple, address-oblivious, and robust against εn adversarial failures and stochastic failures occurring with probability δ for any 0 ≤ {ε, δ } < 1. Furthermore, they can handle multiple rumors of size b ∈ ω(ln n ln ln n) with nb + o(nb) bits of communication per rumor.

Joint work with Laurent Hayez and Miguel Matos

Dr. Hugues Mercier received the B.Sc. degree in mathematics from Université Laval, the M.Sc. degree in computer science from the Université de Montréal, and the Ph.D. degree in electrical and computer engineering from the University of British Columbia, Canada, in 2008. From 2008 to 2011, he was a postdoctoral research fellow at the Harvard School of Engineering and Applied Sciences, and at McGill University. Currently, he is a research associate at the Université de Neuchâtel in Switzerland. His current interests are the applications of coding theory, information theory, combinatorics, and algorithms to the study of communication networks. He is the scientific and technical director of the European H2020 project SafeCloud.

Back to EBSIS Events section.