OSDI '06 Abstract
Pp. 191–204 of the Proceedings
BAR Gossip
Harry C. Li, Allen Clement, Edmund L. Wong, Jeff Napper, Indrajit Roy,
Lorenzo Alvisi, and Michael Dahlin, The University of Texas at Austin
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.
- View the full text of this paper in HTML and PDF. Listen to the presentation in MP3 format.
Until November 2007, you will need your USENIX membership identification in order to access the full papers.
The Proceedings are published as a collective work, © 2006 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.
|
