BitTorrent e o Dilema do Prisioneiro

Pesquisando algumas coisas para o meu mestrado descobri algumas curiosidades sobre como o BitTorrent funciona e porquê. Eu já conhecia o funcionamento básico, mas descobri que algumas coisas sempre me intrigaram, como por que em arquivos com milhares de usuários, apenas uma parte deles aparece na lista de peers.


Um dos maiores problemas em redes para download de arquivos p2p (e em outros sistemas onde não há uma autoridade central) é o chamado 'free-riding', que consiste em usuários que consomem os recursos (fazendo o download de arquivos) sem produzir nada (fazer upload dos arquivos já baixados).

Como não é pago nenhum 'preço' por baixar um arquivo e fazer upload não traz nenhum benefício à pessoa que o faz, o 'free-riding' parece uma opção tentadora, mas que acaba degradando a qualidade da rede.

O Dilema do Prisioneiro

Essa dificuldade de cooperação é exemplificada em um dos problemas mais clássicos de Teoria dos Jogos, o Dilema do Prisioneiro.

Nesse problema, dois suspeitos são interrogados em salas separadas sobre um crime que cometeram. Cada um deles deve escolher entre Confessar (C) ou Permanecer em Silêncio (S).
Caso ambos confessem, ficarão presos por 5 anos.
Se apenas um confessar, este será libertado, enquanto o outro ficará preso por 10 anos.
Se nenhum confessar, os dois ficarão presos por 6 meses, por algum crime menor.

Cada suspeito então, chegará ao seguinte raciocínio: Se o outro confessar, a melhor opção será confessar também e cumprir 5 anos de pena em vez de 10. Se o outro ficar em silêncio, a melhor opção também será confessar e ser libertado em vez de ficar 6 meses na prisão.

Assim, a única solução racional (supondo, é claro, que cada suspeito só está interessado em ficar o menor tempo possível na prisão) é que os dois confessem, cada um cumprindo 5 anos.

Embora seja fácil ver que a melhor solução seria ambos ficarem em silêncio, esse resultado não é estável, pois os dois tem um incentivo a confessar, mesmo se antes do interrogatório tivessem decidido ficar em silêncio.

Apesar de simples, esse exemplo (que pode ser generalizado para mais jogadores) ilustra bem o impasse das redes p2p. Mas como resolvê-lo?

Jogos Iterados

Embora a única solução racional para o Dilema dos Prisioneiros seja que os jogadores confessem (não produzam / não façam upload), a situação muda se o jogo for repetido várias vezes.

Quando os jogadores irão se encontrar de novo e sabem disso (seja para compartilhar novos arquivos ou para cometer novos crimes - ou ambos, no caso de pirataria), a cooperação pode ser garantida através de reciprocidade e retaliação (não cooperar em uma rodada fará com que os outros jogadores não cooperem com você no futuro), de forma que, a longo prazo, a cooperação seja a melhor opção. (Uma coisa interessante de notar é que se os jogadores souberem que uma iteração é a última - ou uma das últimas, dependendo dos valores nas penas - cooperar deixa de ser vantajoso)

Essa estratégia (conhecida como Tit for Tat, ou Olho por Olho) é simples: coopere se a outra pessoa se é a primeira vez que se encontram ou se a pessoa cooperou com você na última vez que se encontraram. Dessa forma, nenhum jogador tem incentivo a desertar, pois isso levará a penas maiores (ou recompensas menores) no futuro.

E as redes p2p?

Bom, mas se as pessoas em geral usam redes p2p para compartilhar arquivos várias vezes, por que os free-riders ainda existem?

Em primeiro lugar, há o problema de como garantir a reciprocidade. Além da necessidade de criar uma lista com todos os logins que cooperaram / não cooperaram, é fácil para um usuário que não coopera criar uma nova conta e burlar o sistema. Além disso, é difícil definir se um usuário coopera ou não, pois a cada interação entre os usuários, geralmente um está enviando o arquivo enquanto o outro está apenas o baixando, não havendo uma garantia de que este já tenha tido a oportunidade de enviar algum arquivo que o primeiro precisasse (não há reciprocidade direta).

Mesmo ignorando os problemas de falsas identidades e de identificação de cooperação, há um problema maior: redes de compartilhamento de arquivos tem muitos usuários. Assim, a probabilidade de encontrar um usuário mais de uma vez é baixa e não a interação entre um mesmo par de usuários não é frequente o suficiente para que a reciprocidade seja eficiente.

O BitTorrent

A solução encontrada pelo BitTorrent é a seguinte:

Os usuários são separados em dois grupos: os que tem o arquivo completo e estão fazendo upload (seeders) e os que ainda estão baixando o arquivo (leechers).

O arquivo a ser compartilhado é dividido em vários pedaços pequenos.

Seeders não levam em conta a cooperação (pois já conseguiram o arquivo inteiro) e enviam pedaços para os leechers, dando preferência àqueles com maior velocidade de conexão (e portanto, poderão compartilhar essa parte com os outros mais rapidamente) e escolhendo os pedaços mais raros entre os leechers para enviar, fazendo com que, embora os leechers não tenham o arquivo completo, as partes estejam bem distribuídas e seja possível terminar o download mesmo se o seeder se desconectar.

Ao iniciar o download de um arquivo, um leecher se conecta a um grupo relativamente pequeno de outros leechers (e seeders) para começar a transferência. Desses leechers conectados, um grupo ainda menor (geralmente 4 ou 5) é escolhido como 'vizinhança' e a transferência é feita com esses (compartilhando os pedaços já recebidos do arquivo e baixando pedaços que os vizinhos possuam). Também entre leechers, pedaços mais raros tem preferência na transmissão.

Essa lista é atualizada com frequência de forma a manter o conjunto de vizinhos que lhe dá a maior taxa de download (dando assim preferência aos usuários que cooperam mais). De tempos em tempos um leecher aleatório é escolhido para a lista, dando oportunidade a um novo usuário de cooperar.

Principalmente para arquivos grandes (o foco do BitTorrent), a divisão em várias partes pequenas e a restrição no número de peers 'conectados' asseguram que os mesmos usuários se conectarão frequentemente, e a escolha de vizinhos que compartilham mais faz com que quanto mais um usuário compartilhe, mais rapidamente ele baixe um determinado arquivo. (por isso a velocidade do download começa geralmente baixa e vai aumentando com o tempo)