Kademlia: A Peer-to-peer Information System Based on the XOR Metric

Abstract
We describe a peer-to-peer distributed hash table with provable consistency and performance in a fault-prone environment. Our system routes queries and locates nodes using a novel XOR-based metric topology that simplifies the algorithm and facilitates our proof. The topology has the property that every message exchanged conveys or reinforces useful contact information. The system exploits this information to send parallel, asynchronous query messages that tolerate node failures without imposing timeout delays on users.
by Petar Maymounkov and David Mazi`eres

Artigo dos autores do Kademilia.

• A folha mais próxima é aquela que compartilha o maior prefixo
• Xor é unidirecional. Para uma determinada distância e um ponto X te, apenas um ponto a essa distância. Unidirecionalidade garante que buscas pela mesma chave convergem pelo mesmo caminho. Assim, rola de cachear coisas no meio do caminho afim de aliviar hot spots
• Um nó guarda o endereço de k nós situados a [2^i:2^i+1], 0 <= i <= 160. Ou seja, k nós de cada subárvore. Esta lista de nós é chamada k-bucket. Nós antigos ficam mais tempo no balde pois são mais prováveis de ficar.
  

Incentives Build Robustness in BitTorrent

Abstract
The BitTorrent file distribution system uses tit-for-tat as a method of seeking pareto efficiency. It achieves a higher level of robustness and resource utilization than any currently known cooperative technique. We explain what BitTorrent does, and how economic methods are used to achieve that goal.

by Bram Cohen

Escrito pelo autor do BitTorrent, descreve em alto nível o funcoinamento do BitTorrent.


Características legais do BT:
Piece download

• Utiliza pipeline de requisições para evitar ficar esperando pela confirmação de envio de cada subpiece
• Utiliza a política de rarest first para escolha de pieces pois:
• Faz com que todo mundo se interesse pelos mesmos pieces, então o peer acaba obtendo um piece desejado
• Piecees mais comuns são deixados para o final do download já que eles são mais provãveis de serem encontrados então
• Distribui melhor o arquivo pela primeira vez pois baixa do seed os pedaços ainda não baixados por ninguém
• No caso do seed não querer mais fazer upload, reduz as chances de um pedaço ficar indisponível, pois distribui mais rapidamente os mais raros
• No início do download, rarest first não é utilizado. O que interessa para o peer é conseguir um piece o mais rápido possível, assim ele pode participar da rede logo. Como os pieces mais raros estão distribuídos em menos nós, a taxa de transferência pode ser menor e demoraria mais para conseguir este piece. Então os peer pedem um piece aleatório.

Resource alocation

• Optimistic unchoke: Simply uploading to the peers which provide the best download rate would suffer from having no method of discovering if currently unused connections are better than the ones being used. To fix this, at all times a BitTorrent peer has a single ‘optimistic unchoke’, which is unchoked regardless of the current download rate from it.

Making Gnutella-like P2P Systems Scalable

Abstract
Napster pioneered the idea of peer-to-peer file sharing, and supported it with a centralized file search facility. Subsequent P2P systems like Gnutella adopted decentralized search algorithms. However, Gnutella’s notoriously poor scaling led some to propose distributed hash table solutions to the wide-area file search problem. Contrary to that trend, we advocate retaining Gnutella’s simplicity while proposing new mechanisms that greatly improve its scalability. Building upon prior research [1, 12, 22], we propose several modifications to Gnutella’s design that dynamically adapt the overlay topology and the search algorithms in order to accommodate the natural heterogeneity present in most peer-to-peer systems. We test our design through simulations and the results show three to five orders of magnitude improvement in total system capacity. We also report on a prototype implementation and its deployment on a testbed.

Mostra alguns problemas de escalabilidade do Gnutella e propões as seguintes soluções:

• Adaptação da topologia: Ensures that high-capacity nodes are the high degree nodes
• Controle de fluxo: Forward queries if can't answer them
• Cria ponteiros para o conteúdo nos vizinhos
• Biased walk: Não realiza flooding, encaminha para alguns poucos nós. Em geral encaminha para os nós mais conectados. Como o conteúdo é replicado nos vizinhos, nós muito conectados conhecem muito da rede.

Ele ainda argumenta porquê utilizar Gnutella ao invés de DHTs, uma vez que DHTs não sofrem tanto com escalabilidade:

• P2P clients are extremely transient
• Keyword searches are more prevalent, and more important, than exact-match queries.
• Most queries are for hay, not needles.