Papers
Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services
Seth Gilbert, Nancy Lynch · ACM SIGACT News, 2002
O problema: uma conjectura informal virando prova formal
No ano 2000, Eric Brewer apresentou em uma palestra a ideia de que um serviço distribuído não conseguiria entregar simultaneamente três propriedades desejáveis: consistência, disponibilidade e tolerância a partições de rede. A observação era influente entre praticantes, mas permanecia como conjectura — sem uma definição precisa dos três termos nem uma demonstração matemática. Gilbert e Lynch escrevem este artigo justamente para fechar essa lacuna: dar definições formais, no vocabulário de sistemas distribuídos assíncronos, para consistência, disponibilidade e tolerância a partição, e então provar que as três não podem coexistir. O motivador prático é o boom de serviços web replicados no final dos anos 1990: à medida que dados passam a ser espalhados por múltiplos nós geograficamente distantes para escalar e sobreviver a falhas, mensagens entre esses nós podem se perder ou atrasar indefinidamente, e daí a pergunta deixa de ser teórica — arquitetos de sistemas reais precisavam saber que garantia abrir mão quando a rede falhasse. O artigo se posiciona como uma ferramenta de raciocínio, não como uma regra que probe combinações: ele deixa claro que a impossibilidade vale quando uma partição de fato ocorre, e que sistemas podem se comportar de formas diferentes antes, durante e depois dela.
As três propriedades definidas com precisão
O núcleo do artigo é dar significado exato a cada letra do CAP. Consistência é definida como um comportamento equivalente a ter uma única cópia atualizada dos dados: qualquer leitura, depois de uma escrita concluída, deve retornar aquele valor (ou um mais recente), como se as operações fossem executadas em uma ordem global única, mesmo havendo réplicas. Disponibilidade significa que todo pedido enviado a um nó não-falho do sistema precisa eventualmente receber uma resposta — o sistema não pode simplesmente ficar em silêncio para um cliente legítimo. Tolerância a partição significa que o sistema continua funcionando mesmo quando mensagens entre grupos de nós são perdidas ou arbitrariamente atrasadas pela rede, de forma que os nós não conseguem se comunicar entre si por um período. O artigo assume o modelo assíncrono: não há limite conhecido para quanto tempo uma mensagem pode demorar para chegar, o que é a formalização mais pessimista (e mais geral) de uma rede real. É essa definição de partição — perda ou atraso arbitrário de mensagens entre subconjuntos de nós, sem que o restante do sistema saiba se a mensagem foi perdida ou só está atrasada — que sustenta toda a prova seguinte.
A prova: por que não dá pra ter as três ao mesmo tempo
A demonstração usa um argumento por contradição com um cenário mínimo de dois nós que replicam o mesmo dado e ficam separados por uma partição de rede. Suponha que o sistema seja consistente, disponível e tolerante a partição. Durante a partição, um cliente escreve um novo valor no primeiro nó; como o sistema é disponível, esse nó precisa responder ao cliente mesmo sem conseguir avisar o segundo nó da atualização, já que a partição bloqueia a mensagem entre eles. Em seguida, outro cliente lê o dado no segundo nó; como o sistema também é disponível, esse segundo nó é obrigado a responder — mas ele nunca recebeu a atualização, então só pode devolver o valor antigo. Isso viola a consistência, porque a leitura deveria refletir a escrita mais recente. O ponto central da prova é que, durante a partição, cada nó isolado não tem como saber se o outro está apenas lento ou está realmente inalcançável; ele precisa decidir localmente entre responder com um dado possivelmente desatualizado (mantendo disponibilidade, perdendo consistência) ou recusar a resposta até ter certeza (mantendo consistência, perdendo disponibilidade). Como essa escolha é inevitável assim que a partição acontece, as três propriedades não podem ser garantidas simultaneamente nesse modelo.
Além da prova: o modelo parcialmente síncrono e o trade-off na prática
Depois de provar a impossibilidade no modelo assíncrono puro, o artigo discute um cenário mais próximo de redes reais: o modelo parcialmente síncrono, em que os nós têm relógios locais e podem usar timeouts para estimar se uma mensagem está apenas atrasada ou se houve mesmo uma partição. Nesse ambiente, os autores mostram que ainda não é possível fugir do teorema, mas os sistemas ganham uma ferramenta prática para gerenciar o trade-off de forma mais informada, ao invés de escolher cegamente entre consistência e disponibilidade. Isso significa que projetistas podem, por exemplo, tolerar inconsistência temporária durante o tempo estimado de uma partição e restaurar a consistência assim que a comunicação for restabelecida, em vez de simplesmente recusar todas as respostas. O artigo enfatiza que o resultado é sobre o que acontece durante e por causa da partição, não uma afirmação de que consistência e disponibilidade sejam sempre incompatíveis. Décadas depois, essa distinção fica ainda mais explícita numa extensão popular chamada PACELC, proposta por Daniel Abadi (2010/2012), que soma ao CAP a ideia de que mesmo sem partição alguma (E, 'else'), sistemas replicados ainda precisam escolher entre latência e consistência (L versus C) — reconhecendo o CAP como uma prova sobre o caso raro da partição, e não sobre todo o funcionamento diário de um sistema distribuído.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.