O que é o Teorema do PAC?

Esta é apenas a minha noção e compreensão do teorema do PAC. Desde o momento em que saiu inicialmente, tem tido uma evolução justa. As pessoas identificaram algumas falhas, advertências, e tanto quanto sei, não há uma única explicação carimbada do teorema. Abaixo está minha tentativa de explicá-lo falando sobre alguns conceitos de sistemas distribuídos que envolvem o teorema.

O teorema CAP de Eric Brewer _originalmente_ afirma que qualquer sistema distribuído com dados compartilhados é susceptível de ver tensão entre as seguintes propriedades sistêmicas:

1. Consistência - Todas as réplicas estão em sincronia e mantêm o mesmo estado de qualquer objeto em qualquer ponto do tempo. Também conhecido como consistência sequencial.
   <
2. Disponibilidade - Um pedido irá eventualmente ser concluído com sucesso. Uma requisição de leitura/escrita em qualquer nó do sistema nunca será rejeitada enquanto o nó em particular estiver em funcionamento.
   li>li> Tolerância de Partição da Rede - Quando a rede que liga os nós cair, o sistema continuará a funcionar mesmo que alguns/todos os nós possam comunicar uns com os outros por mais tempo.
   

Alternately, o teorema afirma que é possível que o sistema satisfaça quaisquer duas, mas não todas as propriedades mencionadas acima.

Let's say the system comprises of 2 nodes interconnected with network.

If a data item is stored only at node N1, then that node will always have the consistent state of that data as all the updates are always serialized on the same node. Então, alcançamos a consistência "C".

Suponha, os dados no nó N1 são replicados no nó N2, e ambas as réplicas estão sempre em sincronia, mantendo cópias consistentes dos dados a qualquer momento. Isto implica que uma atualização acontecendo no nó N1 irá propagar-se atomicamente para o nó N2 e vice-versa. Assim, uma solicitação de leitura/esquecimento de um item de dados em qualquer uma das réplicas (N1 ou N2) nunca retornará uma cópia obsoleta ou desatualizada dos dados. Nosso sistema novamente alcança consistência "C".

Agora que entendemos brevemente "C" do teorema CAP, deixemos's assumir que nosso sistema distribuído de dois nós N1 e N2 é projetado e implementado de forma que os dados sejam replicados em ambos os nós, e o sistema mantenha uma cópia consistente dos dados.

Having said this, let's say that the network connecting both the nodes goes down (network gets partitioned), but both nodes N1 and N2 are up and running fine.

How will this impact the overall operations of the system ? As atualizações acontecendo no nó N1 não podem mais alcançar o nó N2 e vice-versa. Se agora :

1. Ambas as réplicas continuam a servir pedidos de atualização de um item de dados, e como o sistema é particionado em rede, estas atualizações não podem mais ser propagadas para as outras réplicas. Assim, ambas as réplicas divergem e acabam mantendo cópias conflitantes ou inconsistentes do item de dados. Portanto, o sistema não possui mais a propriedade consistência ("C"). Aqui escolhemos a disponibilidade ("A"), e continuamos as operações de serviço em um ambiente desconectado. Em outras palavras, preferimos a disponibilidade "A" em vez da consistência "C", e toleramos as partições de rede "P". Assim, o sistema fornece propriedades "A" e "P" do teorema CAP.

OR

2. Uma das réplicas (let's dizem N2) pára de atender pedidos de leitura/gravação ao detectar que a rede conectando o sistema foi particionada. Isto significa que o sistema trata o nó N1 como não mais disponível, e qualquer requisição neste nó será rejeitada. Neste caso, preservamos a propriedade de consistência, pois todas as atualizações serão serializadas apenas no nó N1, e não há possibilidade de divergência de réplicas, uma vez que a outra réplica não irá atender a nenhuma solicitação. Note que o N2 não deve atender nem mesmo uma solicitação de leitura/estipulação, pois acabará devolvendo a cópia antiga/estipulada dos dados. Portanto, este tipo de sistema fornece consistência "C" ao custo da disponibilidade "A", e como antes toleramos partições de rede "P".

OR

3. Ambas as réplicas N1 e N2 param de servir pedidos de atualização, mas continuam a fornecer operações de leitura/estiragem. Neste caso, o sistema está disponível para operações de leitura, mas não para atualizações. Aqui novamente preservamos a consistência "C" ao custo da disponibilidade "A", e toleramos as partições da rede "P".

Em todos os pontos acima, foi uma escolha entre "C" e "A". A partir da literatura que li e compreendi, sinto que é quase sempre o caso que o trade-off está entre "C" e "A". A tolerância de partição "P" não é realmente uma escolha. Considero-a como uma propriedade de base usada para fazer o trade-off entre consistência e disponibilidade, e consequentemente projetar o sistema.

Se a rede for particionada, eu não'não sei de uma maneira onde o sistema pode ser tanto consistente "C" quanto disponível "A".

"As réplicas no sistema são incapazes de se comunicar entre si, mas o sistema é fortemente consistente, o que requer que as réplicas propaguem as mudanças entre si através da rede, mas isto pode't acontecer à medida que a rede é particionada".

Hence, strong consistency (C) and availability (A) are not likely to coexist together.

A discussão acima também implica que "C", "A", and "P" can't together achieved in the distributed system with shared data, and this is in accordance with theorem.

A noção de consistência também evoluiu levando a sistemas com modelos fracos ou eventualmente consistentes. Por exemplo, no DynamoDB, as atualizações são permitidas nas réplicas em caso de falha da rede. A sincronização das réplicas em background é feita usando árvores Merkle para restaurar a consistência entre os dados mantidos nas réplicas. Isto significa que as atualizações eventualmente se propagam para todas as réplicas e, portanto, o sistema é "eventualmente consistente". Isto significa efetivamente que todas as três propriedades "C", "A", e "P" são fornecidas pelo armazenamento de dados. No entanto, a noção e definição de "C" é muito diferente.