Jelenlegi hely

Kutatószeminárium

Félév: 
2017/18 I. félév
Helyszín: 
Árpád tér 2. II. em. 220. sz.
Dátum: 
2017-11-07
Időpont: 
15:15-16:00
Előadó: 
Gabor Danner
Cím: 
Token Account Algorithms: The Best of the Proactive and Reactive World
Absztrakt: 

Many decentralized algorithms allow both proactive
and reactive implementations. Examples include gossip protocols
for broadcasting and decentralized computing, as well
as chaotic matrix iteration algorithms. In proactive systems,
nodes communicate at a fixed rate in regular intervals, while
in reactive systems they communicate in response to certain
events such as the arrival of fresh data. Although reactive
algorithms tend to stabilize/converge/self-heal much faster, they
have serious drawbacks: they may cause bursts in bandwidth
consumption, and they may also cause starvation when the
number of messages circulating in the system becomes too
low. Proactive algorithms do not have these problems, however,
nodes waste a lot of time sitting on fresh information.
We propose a novel family of adaptive protocols that apply
rate limiting inspired by the token bucket algorithm to prevent
bursts but they also include proactive communication
to prevent starvation. With the help of our traffic shaping
service, some applications approach the speed of the reactive
implementation, while maintaining strong guarantees regarding
the total communication cost and burstiness. Due to the
proactive component we can help maintain a certain level of
activity despite losing messages due to faults or the application
semantics. We perform simulation experiments over synthetic
network topologies as well as over a real smartphone availability
trace. Our results indicate a fourfold speedup in a broadcast
application, and an order of magnitude speedup in the case
of gossip learning, when compared to the purely proactive
implementation.

Everyone is welcome.