Tuesday, October 31, 2006

Paper: "BAR Gossip"

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.

2 Comments:

Blogger Anthony Nicholson said...

Official scribe comments:

The motivation scenario for talk is a live, peer-to-peer streaming media application. Such applications can fall apart, however, in the presence of malicious nodes, if it is not in a node's self-interest to forward data packet on to their peers. The authors introduce the concept of BAR gossip, a gossip protocol that makes it in the interest of selfish nodes to act toward the benefit of the overall system, while detecting and punishing Byzantine (malicious) nodes. BAR gossip is in fact two protocols: balanced exchange and optimistic push.

During balanced exchange, at each round every node selects one partner, the partners exchange their transaction histories, and then trade equal numbers of data updates. Clients must commit to their histories before discovering their partner's history, and similarly must send the data updates first in encrypted form before subsequently sending the key. This makes bandwidth a "sunk cost" so that it is illogical for selfish nodes to withhold the data key from their partner later on. The authors also introduce the notion of verifiable partner selection to prevent clients from talking to more than one client per round (to accumulate more updates). The second part of BAR gossip is optimistic push, which handles bootstrapping for new nodes. In this case, unequal numbers of updates may be exchanged, but the lesser peer must sacrifice the same amount of energy and bandwidth by sending junk to even out the exchange. Their simulation results show that following the protocol was the most beneficial strategy clients in all cases.

Rob Sherwood from Maryland asked about cases where clients consider different weights for inbound and outbound traffic. Harry argued that such asymmetry can be handled by sizing key requests accordingly. Rob responded that in cases where one is downloading illegal content, it might be overwhelmingly important to never upload anything. Harry responded that in such extreme cases BAR Gossip might not work. Jim Liang from UIUC noted the authors assume that all clients know the complete membership list. Harry responded that they are currently looking at handling cases where clients have only partial membership information. Jim further asked about how the BAR Gossip protocol achieves low latency for streaming media. Harry said their experiments showed an average latency of 20 seconds for a live video stream. This compares favorably with existing streaming media applications (such as the free NCAA Final Four video feed). Another questioner asked about how their protocol handles collusion. Harry noted they have no explicit mechanism for this because handling collusion in game theory is difficult. Their results showed, however, that BAR Gossip is robust for small colluding groups (up to 30% nodes colluding). The last question concerned how scalable BAR Gossip is. Harry noted three limitations in scaling their system: first, handling dynamic membership churn; second, handling nodes with only partial membership information; third, locality aware partner selection. They are currently looking at all three issues.

8:12 PM  
Blogger Kurt A. Tasche said...

Get over 10,000 hits per day to your website for free!! Check out
this start page traffic exchange

5:25 PM  

Post a Comment

<< Home