Jelenlegi hely


2017/18 I. félév
Árpád tér 2. II. em. 220. sz.
Gabor Danner
Token Account Algorithms: The Best of the Proactive and Reactive World

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

Everyone is welcome.