BAR Gossip
Proceedings of the USENIX Operating Systems Design and Implementation (OSDI) 2006.
View
PDF or BibTeX.
areas
Distributed Systems,
Game Theory
abstract
We present the first peer-to-peer data streaming application that guarantees predictable
throughput and low latency in the BAR (Byzantine/Altruistic/Rational) model, in which non-altruistic nodes can behave in ways that are
self-serving (rational) or arbitrarily malicious
(Byzantine). At the core of our solution is a BAR-tolerant version of gossip, a well-known technique
for scalable and reliable data dissemination. BAR
Gossip relies on verifiable pseudo-random partner
selection to eliminate non-determinism that can
be used to game the system while maintaining the
robustness and rapid convergence of traditional gossip. A novel fair enough exchange primitive entices
cooperation among selfish nodes on short timescales,
avoiding the need for long-term node reputations.
Our initial experience provides evidence for BAR
Gossip’s robustness. Our BAR-tolerant streaming
application provides over 99% convergence for
broadcast updates when all clients are selfish but
not colluding, and over 95% convergence when up
to 40% of clients collude while the rest follow the
protocol. BAR Gossip also performs well when
the client population consists of both selfish and
Byzantine nodes, achieving over 93% convergence
even when 20% of the nodes are Byzantine.