o problema
Em 2006 já estava assentado que dividir um arquivo em peças e deixar cada par servir o que tem escala melhor que um servidor. O que não estava assentado era como decidir: qual peça pedir, e para quem mandar, sabendo apenas o que os oitenta vizinhos do seu peer set têm. Os modelos analíticos que provavam a eficiência do BitTorrent assumiam conhecimento global — cada par conhece todos os outros. Isso descreve o caso ótimo, não o caso que roda.
Nesse vácuo apareceu uma safra de propostas para trocar as duas heurísticas do protocolo. Simulações sugeriam que o rarest first levava à escassez de certas peças, e propunham network coding no lugar. Outros trabalhos acusavam o choke de ser injusto e de favorecer free riders, e propunham tit-for-tat no nível de bytes: só mando para você se o saldo do que já mandei menos o que recebi ficar abaixo de um limiar. Nenhuma dessas conclusões vinha de medição em torrent real.
a ideia
Em vez de simular, instrumentar. Os autores modificaram o cliente mainline 4.0.2 — a referência de fato do protocolo, já que não existe especificação oficial mantida — para registrar cada mensagem, cada mudança de estado do choke e cada estimativa de taxa. Depois plugaram esse cliente em 26 torrents reais, escolhidos para castigar os algoritmos: torrents sem seed nenhum, torrents com um único seed e mais de mil leechers, torrents com milhares de seeds. Cada experimento durou 8 horas, tempo suficiente para o cliente virar seed. Nenhum outro par foi controlado.
A métrica central é a peer availability: a fração do tempo em que o par local está interested num par remoto, enquanto esse remoto está no peer set. Se o valor é 1, todo mundo sempre tem algo que interessa a todo mundo — a entropia ideal que qualquer estratégia de seleção de peça deveria perseguir.
como funciona
O rarest first é literal. Cada par conta quantas cópias de cada peça existem no seu peer set; se a peça menos replicada tem m cópias, todas as peças com m cópias formam o conjunto das mais raras, e a próxima peça sai desse conjunto por sorteio. Três políticas o corrigem nas bordas: as 4 primeiras peças são escolhidas ao acaso (peça aleatória é mais replicada, logo baixa mais rápido, e é preciso ter o que reciprocar); os blocos de uma peça já iniciada têm prioridade máxima, porque só peça completa pode ser servida; e no fim do download entra o end game mode, que pede os blocos faltantes a todos e cancela os duplicados.
O choke roda em dois modos. Como leecher: a cada 10 segundos os pares interessados são ordenados pela taxa de download que entregam, e os 3 mais rápidos ficam desafogados; a cada 30 segundos um quarto par é sorteado — o optimistic unchoke, que serve de descoberta e dá a primeira peça a quem chegou sem nada. Como seed, a partir da versão 4.0.0, a ordenação deixou de ser por velocidade: os pares são ordenados pelo tempo do último unchoke, mais recentes primeiro; em dois períodos de 10 segundos mantém-se os 3 do topo e sorteia-se um quarto, e no terceiro período mantém-se os 4.
Os números batem com a explicação. No torrent 8 (1 seed, 861 leechers, 863 peças de 4 MB), o conjunto das peças mais raras encolhe linearmente no tempo, a uma taxa próxima de 36 kB/s — a banda do seed inicial, e não o algoritmo, é o gargalo. No torrent 7 (1 seed, 713 leechers), já em regime estacionário, o número de peças mais raras faz dente de serra: entra um par novo, muda o conjunto das raras, o rarest first replica e o conjunto desaba de novo.
o que isso custou
O estudo tem um único cliente instrumentado, por escolha — mais clientes enviesariam o próprio torrent —, e 26 torrents não são amostra exaustiva da internet. Experimento assim não se repete: cada corrida depende de quem estava no enxame e de que lista o tracker devolveu. Os autores não avaliam a capacidade de serviço obtida pelo choke, apenas sua justiça, e admitem não entender o equilíbrio que faz o algoritmo convergir para um subconjunto estável de parceiros.
O paper também não é uma acusação contra network coding. Codificação é ótima em mais casos: com grau de saída pequeno, ou com conectividade ruim entre grupos de pares, o rarest first vai mal. O argumento é de contexto — torrents na internet têm peer set de 80 e não sofrem desses gargalos — somado a custo de CPU e complexidade de implantação. E sobram dois defeitos reais: os primeiros blocos chegam devagar, o que dói em conteúdo pequeno, e a fase transiente dura o que a banda do seed inicial mandar.
onde isso aparece hoje
O algoritmo de choke descrito aqui é o de Incentives Build Robustness in BitTorrent; este trabalho é a auditoria empírica daquele desenho, e a parte sobre o estado de seed documenta uma versão que o paper original não tinha. A separação que ele faz entre localizar conteúdo e replicar conteúdo continua sendo a divisória do campo: DHTs como Chord resolvem a primeira metade, e o rarest first mais o choke resolvem a segunda. IPFS monta as duas na mesma pilha, com troca de blocos herdada do BitTorrent.