o problema
O Clearinghouse traduzia nomes hierárquicos em endereços de máquina na Xerox Corporate Internet: centenas de Ethernets ligadas por gateways e linhas telefônicas de capacidades variadas, milhares de máquinas, um pacote do Japão para a Europa atravessando até 14 gateways e 7 linhas. Alguns domains estavam replicados em todos os servidores — várias centenas deles. Em 1986, boa parte dos problemas de desempenho observáveis da rede vinha justamente da tentativa de manter esses domains consistentes.
O mecanismo era direct mail mais anti-entropy noturna, e havia um passo de remailing: quando dois participantes de anti-entropy discordavam, o valor correto era enviado por mail a todos os sites. Para um domain guardado em 300 sites, isso podia significar 90.000 mensagens por noite, muito além da capacidade da rede — e o resultado era a queda de todos os serviços: mail, transferência de arquivo, lookup de nome. Os servidores nem sequer terminavam a anti-entropy na janela entre meia-noite e 6h. As alternativas da literatura dependiam de garantias que aquela rede não dava: mail confiável, entrega ordenada, estruturas de controle distribuídas mutuamente consistentes (uma delas com estado O(n²) por servidor descrevendo todos os outros), ou um primary site que centraliza o controle.
a ideia
Parar de tentar entregar e deixar contagiar. Cada site, periodicamente, escolhe outro ao acaso e troca informação com ele. Nada além disso: nenhum site precisa saber quem são todos os outros, nenhuma mensagem precisa chegar, nenhuma ordem precisa ser respeitada. O que sustenta a corretude é a repetição aleatória, não a garantia individual.
Os autores adotam o vocabulário da epidemiologia: um site é suscetível se não conhece a atualização, infectivo se a conhece e está disposto a compartilhá-la, removido se a conhece e parou. Anti-entropy é uma epidemia simples — ninguém nunca é removido, e por isso ela sempre termina infectando todo mundo. Rumor mongering é uma epidemia complexa — o site perde o interesse depois de encontrar gente que já sabia, o que a torna barata e falível.
como funciona
O banco guarda, por nome, um par (valor, timestamp); timestamp maior sempre vence, e o valor pode ser NIL. Em anti-entropy, ResolveDifference tem três formas: push (mando se o meu for mais novo), pull (peço se o dele for mais novo) e push-pull. A comparação ingênua envia o banco inteiro. Checksums incrementais só ajudam se as réplicas concordarem quase sempre — e uma atualização recente basta para fazê-las discordar. A saída é uma janela τ: cada site mantém uma recent update list com as entradas mais novas que τ, os dois trocam essa lista primeiro, atualizam os checksums e só comparam os bancos completos se ainda houver desacordo. Se τ for escolhido abaixo do tempo real de propagação, os checksums passam a falhar sempre e o tráfego fica pior que sem eles.
Em rumor mongering, o site infectivo escolhe um parceiro por ciclo e perde interesse com probabilidade 1/k ao encontrar quem já sabia. As variantes trocam a moeda por um contador de k contatos inúteis, e o feedback do destinatário por decisão cega. As versões push compartilham a mesma relação entre tráfego m e resíduo s: s = e⁻ᵐ. Contadores e feedback melhoram o atraso, e contadores pesam mais. Pull faz melhor que isso quando a taxa de updates é alta, porque um pedido tende a achar alguém com rumor na lista.
Deleção usa death certificates: o item apagado vira um registro com timestamp que se propaga como qualquer outro e cancela cópias antigas. Como guardá-las para sempre é caro, o esquema mantém dois limites, τ₁ e τ₂: passado τ₁, quase todos descartam, e r sites sorteados guardam uma cópia dormente. Se uma cópia dormente encontra um item obsoleto, ela é reativada — via um segundo timestamp, de ativação, para não cancelar por engano um update legítimo posterior.
Por fim, a distribuição espacial: em vez de sortear parceiros uniformemente, sorteia-se com probabilidade decrescente na distância. Numa linha, d⁻² é o ponto em que tráfego por link e convergência escalam bem ao mesmo tempo; numa malha de dimensão D, seria d⁻²ᴰ. Como a rede real não tem dimensão fixa, os autores usam Q(d), o número acumulado de sites a distância d ou menos, e escolhem por 1/Q(d)² — que se adapta sozinho à dimensão local.
o que isso custou
Consistência só na quiescência: os sites ficam plenamente iguais quando a atividade de update para. Antes disso, o que existe é a promessa de que todo efeito acaba refletido em todas as réplicas.
Por serem randomizados, os algoritmos não permitem prometer convergência em tempo proporcional ao diâmetro da rede. O máximo que se afirma é que a probabilidade de ainda não ter convergido cai exponencialmente com o tempo. Rumor mongering vai além: pode simplesmente falhar, com todos os infectivos virando removidos enquanto sobram suscetíveis — daí a necessidade de anti-entropy por baixo, rodando com pouca frequência, para garantir cobertura.
As death certificates dormentes não escalam indefinidamente, e os autores dizem isso com todas as letras. O tempo de propagação cresce com n; quando ele ultrapassa τ₁, reativações de certificados velhos ficam frequentes, carregam a rede, pioram a propagação, e o desfecho é falha catastrófica. τ₁ — e o espaço em cada servidor — precisa crescer como O(log n).
A combinação de distribuição espacial com topologia irregular também machuca. Com push-pull, aumentar k compensa. Com push ou pull puros, não: numa distribuição com expoente 1,2 foi preciso k=36 para cobrir 100% dos sites em 200 simulações, e para expoentes maiores as simulações não terminaram durante a noite. Os autores mostram dois exemplos patológicos — um par de sites isolados que só conversam entre si, uma árvore distante de um site solitário — e admitem não entender o fenômeno por completo.
onde isso aparece hoje
Este é o paper que deu nome ao gossip. Ele fixou o vocabulário (anti-entropy, rumor mongering, push, pull, push-pull) e a ideia de que difusão epidêmica é uma primitiva de sistema, não uma metáfora. O ganho medido é concreto: com a distribuição não uniforme, o tráfego de comparação no enlace transatlântico da rede da Xerox caiu de 75,71 para 2,38 por ciclo, com convergência menos de duas vezes mais lenta — e a versão implantada rodou na rede inteira.
A linhagem mais direta é Dynamo, que usa gossip para propagar membership e anti-entropy para reconciliar réplicas, e Cassandra, construída sobre a mesma ideia. As death certificates viraram tombstones, com o mesmo problema não resolvido de quando descartá-las. E a pergunta que o paper deixa em aberto — como convergir sem que a ordem de chegada importe — é a que os CRDTs atacam pelo lado da estrutura de dados, em vez de pelo lado do timestamp.