Optimal Epidemic Dissemination
-----------------------------------
          
This seminar is part of the "EBSIS - Event Based Systems in Iasi" Twinning project. This project has received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No 692178.
-----------------------------------
          
ABSTRACT
-----------------------------------
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.

Prezentarea va fi incheiata de un anunt privind o posibila co-supervizare 
a unei teze de master intre Facultatea de Informatica si 
Institutul de Informatica de la Universitatea din Neuchatel, Elvetia 
pe tema: "Optimisation of the gossip layer for bitcoin, hyperledger 
and other blockchains". 
Incurajam pe aceasta cale participarea studentilor masteranzi interesati.
          
SPEAKER(S)
-----------------------------------
MERCIER Hugues, PhD
University of Neuchatel
Elvetia
-----------------------------------
Hugues Mercier received the Ph.D. degree in 
electrical and computer engineering from the 
University of British Columbia 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 researcher at the Universite de 
Neuchatel in Switzerland. 
His current interests are the applications of coding theory,
information theory, and algorithms to the study of 
communication networks. With a background in Mathematics, 
Computer Science and Electrical Engineering, he enjoys 
solving applied problems supported by theoretical 
results allowing a better understanding of the behavior 
and limits of communication systems.
-----------------------------------