Computer Science › Software + Computação Distribuída
`crash-faults-vs-byzantine-faults` nomeou o modelo de falha bizantina, mas deliberadamente parou na definição; este conceito constrói o problema de fato que Lamport, Shostak e Pease formalizaram em 1982, generais que têm de concordar sobre atacar-ou-recuar trocando só mensageiros que um traidor pode forjar ou sobre os quais um general traidor pode mentir, prova com um cenário concreto de três generais e um traidor que nenhuma solução existe com mensagens orais (não assinadas) a menos que haja estritamente mais do que três vezes o número de traidores no total de participantes, e esboça o algoritmo recursivo de Mensagem Oral que atinge esse limite exatamente, a fundação formal sobre a qual todo protocolo tolerante a falhas bizantinas prático nesta disciplina se constrói.
O algoritmo de Castro e Liskov de 1999 é a resposta real e prática ao limite teórico que o conceito anterior provou: um cluster de 3f+1 réplicas tolera f réplicas bizantinas rodando três fases de mensagem por requisição, pre-prepare (o primário atribui uma ordem), prepare (toda réplica transmite e coleta 2f+1 prepares que batem para concordar sobre aquela ordem sem confiar só no primário) e commit (2f+1 commits que batem antes de qualquer réplica executar), mais um subprotocolo de troca de visão que substitui um primário que trava ou se comporta de forma suspeita, entregando, pela primeira vez, um protocolo de replicação de máquina de estado tolerante a falhas bizantinas rápido o bastante para sistemas reais, em vez de uma construção puramente teórica.
O PBFT assume algo que o design de Nakamoto de 2008 deliberadamente se recusa a assumir, uma lista de membros fixa e conhecida dentro da qual um protocolo de troca de visão pode votar; o consenso de Nakamoto em vez disso deixa qualquer um entrar anonimamente e substitui a identidade por custo computacional, propor o próximo bloco exige vencer uma loteria de prova-de-trabalho, e a segurança é só probabilística, um bloco é tratado como final uma vez que blocos posteriores suficientes são encadeados sobre ele, não no instante em que um quórum concorda, que é exatamente por que este conceito se delimita honestamente, este é um modelo de confiança genuinamente diferente (sem permissão, finalidade probabilística) que vale nomear com precisão pelo que ele troca contra o do PBFT (com permissão, finalidade determinística), não uma razão para transformar uma disciplina de sistemas distribuídos num curso de mecânica de blockchain.
`the-cap-theorem-a-precise-statement` provou um trade-off que só dispara durante uma partição de rede de fato, deixando sem resposta uma pergunta que importa todo dia que um sistema roda sem nenhuma partição, você ainda espera que toda réplica concorde antes de responder; a formulação PACELC de Abadi de 2012 nomeia esse segundo trade-off, sempre presente, explicitamente, se Particionado, escolha Disponibilidade ou Consistência (exatamente CAP), Senão, escolha Latência ou Consistência, e este conceito a usa para explicar, com precisão, por que as stores no estilo Dynamo que esta disciplina estuda a seguir escolhem consistência fraca mesmo quando a rede está saudável, não só quando ela está particionada, a motivação real sobre a qual o resto do material de banco de dados distribuído desta disciplina se constrói.
O relógio escalar de Lamport consegue provar que a aconteceu-antes de b, mas um sistema que aceita escritas em toda réplica, exatamente o que um sistema escolhendo Disponibilidade sob PACELC faz, precisa de uma ferramenta estritamente mais forte, uma que também consiga provar que duas escritas são genuinamente concorrentes (nenhuma causou a outra) em vez de só lhes atribuir alguma ordem total arbitrária; um relógio vetorial, um contador por réplica, incrementado no próprio evento daquela réplica e mesclado tomando o máximo componente a componente no recebimento de mensagem, recupera exatamente a ordem parcial que os relógios de Lamport achatam, deixando uma store comparar os vetores de duas escritas e decidir, com certeza, se uma domina a outra ou se ambas têm de ser mantidas como um conflito genuíno e não resolvido, a exata capacidade da qual a replicação sem líder dos próximos três conceitos depende.
`primary-backup-vs-quorum-based-replication` introduziu quóruns no nível de máquina de estado replicada, uma maioria concordando sobre um log ordenado; o Dynamo pega a mesma ideia de sobreposição e a aplica sem líder e sem log ordenado de forma alguma, uma chave replica para N nós (a sua lista de preferência, tipicamente os próximos N nós no sentido horário num anel de hashing consistente), uma escrita tem sucesso uma vez que W deles a reconhecem e uma leitura consulta R deles, e este conceito prova, só pelo princípio da casa dos pombos, que R + W > N garante que o quórum de leitura e o quórum de escrita sempre compartilham pelo menos um nó, então pelo menos uma réplica que a leitura toca viu a última escrita, a exata propriedade estrutural da qual cada uma das implantações de consistência ajustável do Dynamo (N=3, R=2, W=2 sendo o próprio exemplo condutor do artigo) de fato depende.
A prova de R + W > N do conceito anterior tem uma suposição silenciosa embutida, a de que os W reconhecimentos de uma escrita vêm dos nós de fato da lista de preferência da chave; o quórum relaxado do Dynamo deliberadamente quebra essa suposição por disponibilidade, se nós suficientes da verdadeira lista de preferência estão inalcançáveis, a escrita é aceita por quaisquer nós saudáveis que estejam a seguir na fila em vez disso, cada um armazenando o valor com um hint registrando a quem ele realmente pertence, e retransmitindo-o uma vez que aquele nó se recupera (hinted handoff), que é a escolha de Consistência versus Disponibilidade do CAP tornada concreta e operacional em vez de abstrata, uma escrita durante todo cenário deste conceito sempre tem sucesso, ao custo honesto de que a garantia de interseção de quóruns que o conceito anterior provou não mais se mantém estritamente até o hint ser entregue.
`eventual-consistency-and-its-real-guarantees` nomeou gossip e anti-entropia genericamente como o modo pelo qual as réplicas convergem; este conceito cobre os dois mecanismos concretos que o Dynamo de fato roda uma vez que o hinted handoff e os quóruns relaxados deixaram as réplicas genuinamente divergidas, o read repair (uma leitura voltada ao cliente que toca R réplicas e nota que elas discordam empurra o valor vencedor de volta para as obsoletas na hora, usando a mesma comparação de relógio vetorial de dois conceitos atrás) e a sincronização em segundo plano por árvore de Merkle (duas réplicas que seguram uma faixa de chaves inteira comparam um hash de raiz primeiro, e só recorrem em subárvores cujos hashes diferem, encontrando toda chave de fato divergida numa faixa de n chaves em O(log n) comparações em vez de comparar todas as n), e faz links cruzados para a construção completa e a prova de correção da própria estrutura de dados em vez de rederivá-la.
Todo conceito até aqui nesta disciplina replicou uma única chave; `acid-properties-precisely-defined` e `two-phase-locking-and-conflict-serializability` (`database-systems`) já provaram a Atomicidade para uma transação confinada ao gerenciador de travas de um nó, e este conceito estende esse mesmo requisito de tudo-ou-nada por entre nós, um coordenador pede a todo participante que prepare (trave as suas linhas e vote sim ou não) na fase um, depois diz a todos para fazer commit ou abortar na fase dois, e trabalha, com precisão, a única falha real do protocolo, se o coordenador falha depois de coletar votos todos-sim, mas antes de a decisão da fase dois alcançar todo participante, cada participante preparado fica travado segurando as suas travas indefinidamente, incapaz de unilateralmente fazer commit ou abortar sem arriscar discordar de uma decisão que o coordenador pode já ter tomado, o problema de bloqueio de fato e comprovável que os próximos dois conceitos existem para abordar.
O protocolo de commit em três fases de Skeen de 1981 é uma tentativa genuína e deliberada de remover exatamente o caso de bloqueio que o conceito anterior provou, ele insere uma fase de pre-commit entre votar e fazer commit para que qualquer participante que alcança o pre-commit já saiba que todo outro participante votou sim, deixando um coordenador recém-eleito fazer commit com segurança em nome de um participante travado em vez de forçá-lo a esperar para sempre; este conceito trabalha com precisão por que esse conserto só se mantém sob uma suposição que redes reais não satisfazem honestamente, atraso de mensagem limitado, mostrando um cenário concreto de partição de rede (não crash) onde dois grupos disjuntos de participantes cada um conclui com segurança uma decisão diferente e contraditória, que é exatamente por que o veredito honesto, enunciado de forma clara aqui, é que o 3PC resolve o bloqueio sob uma suposição de sincronia sem resolvê-lo sob o modelo assíncrono e propenso a partições que toda esta disciplina de resto assume, e por que os sistemas de produção recorrem ao conserto muito diferente que o próximo conceito cobre em vez dele.
A percepção real de Gray e Lamport em 2006, tornada explícita neste conceito, é que o coordenador do 2PC e a suposição de atraso limitado do 3PC nunca foram as únicas opções, já que esta disciplina (via `distributed-systems-i`) já tem um mecanismo que alcança acordo corretamente sempre que qualquer maioria de participantes está de pé e alcançável, e não mais, o próprio Paxos; o Paxos Commit substitui o coordenador único por um pequeno grupo Paxos (ou, numa implementação moderna, Raft) que decide o voto de prepare de cada participante, de modo que uma falha de coordenador não mais bloqueia ninguém, qualquer maioria sobrevivente do grupo de commit pode continuar com segurança, e este conceito rastreia essa exata ideia adiante até como o Google Spanner e o CockroachDB de fato rodam transações distribuídas de produção hoje, um grupo Raft ou Paxos por shard de dados decidindo os desfechos de commit, fechando o laço entre os próprios conceitos de consenso desta disciplina e o material de transações que abriu este tópico.
`eventual-consistency-and-its-real-guarantees` deixou a convergência inteiramente como uma esperança, o gossip normalmente a alcança, sem prova de que ela sempre tenha de; o artigo de 2011 de Shapiro, Preguica, Baquero e Zawirski a fortalece em Consistência Eventual Forte (SEC), quaisquer duas réplicas que entregaram o exato mesmo conjunto de atualizações estão no exato mesmo estado imediatamente, sem espera, sem passo de resolução de conflito necessário, e prova que um CRDT baseado em estado (CvRDT) alcança isso por construção sempre que os seus estados formam um semirretículo de junção (uma ordem parcial com uma mesclagem de menor-cota-superior que é comutativa, associativa e idempotente) e toda atualização só move uma réplica para cima nessa ordem; este conceito trabalha a prova concretamente no G-Counter (um contador só de incremento por réplica, a mesclagem toma o máximo componente a componente, o total é a soma) e no PN-Counter (dois G-Counters, incrementos e decrementos, o valor é a diferença deles), os dois CRDTs mais simples e a fundação direta sobre a qual os tipos de dados mais difíceis do próximo conceito se constroem.
Um CRDT baseado em estado envia o seu estado inteiro a cada mesclagem, desperdiçador uma vez que esse estado é um conjunto ou documento grande; um CRDT baseado em operação (CmRDT) envia só a própria operação e depende de uma garantia diferente e igualmente rigorosa provada no mesmo artigo de 2011, se todas as operações concorrentes comutam (o seu efeito não depende da ordem de entrega) e a rede fornece entrega confiável em ordem causal (uma operação nunca é aplicada antes das operações das quais ela causalmente depende), toda réplica ainda converge para o estado idêntico sem jamais comparar estados inteiros; este conceito trabalha essa garantia em dois tipos de dados que as stores da família Dynamo de fato entregam, o OR-Set (adição vence: toda adição é marcada com um identificador único novo, para que uma adição e uma remoção concorrentes do mesmo elemento resolvam mantendo a adição, resolvendo a ambiguidade clássica da corrida adição/remoção que um conjunto simples não consegue) e o Last-Write-Wins Register (usando os próprios relógios vetoriais desta disciplina ou um timestamp físico como desempate), nomeando honestamente, em Equívocos Comuns, exatamente onde a garantia dos CRDTs para (eles garantem convergência, nunca que o valor convergido é o que qualquer usuário individual pretendeu, um LWW-Register pode silenciosa e corretamente descartar uma escrita concorrente real e sem ordem causal).
Este capstone rastreia o exato cenário que o próprio artigo do Dynamo usa por toda parte, o carrinho de compras de um cliente, por uma partição de rede genuína e de volta, nomeando o conceito preciso responsável por cada passo: uma escrita de adicionar-ao-carrinho durante a partição cai só nos nós alcançáveis de um quórum relaxado, marcada com um hint por `sloppy-quorums-and-hinted-handoff`; uma adição concorrente do outro dispositivo do mesmo cliente cai no outro lado, inalcançável, o valor do carrinho de cada lado divergindo exatamente como `vector-clocks-and-detecting-concurrent-writes` prevê que duas escritas verdadeiramente concorrentes têm de fazer; uma vez que a partição cura, a comparação por árvore de Merkle da anti-entropia (`anti-entropy-read-repair-and-merkle-tree-synchronization`) encontra a chave divergida, e como o carrinho é modelado como um CRDT OR-Set em vez de um valor sobrescrevível simples, a mesclagem em `operation-based-crdts-and-practical-data-types` deterministicamente une ambas as adições sem item perdido e sem resolução manual de conflito, o mesmo desfecho de o item nunca foi perdido, mas uma contagem obsoleta foi brevemente mostrada que o artigo real do Dynamo relata, fechando o laço que esta disciplina abriu, com o próprio capstone de `distributed-systems-i` rastreando uma escrita linearizável por consenso, na escolha oposta e deliberada do trade-off do CAP, tornada totalmente concreta em vez de abstrata.
Part of the Computer Science curriculum.
`crash-faults-vs-byzantine-faults` nomeou o modelo de falha bizantina, mas deliberadamente parou na definição; este conceito constrói o problema de fato que Lamport, Shostak e Pease formalizaram em 1982, generais que têm de concordar sobre atacar-ou-recuar trocando só mensageiros que um traidor pode forjar ou sobre os quais um general traidor pode mentir, prova com um cenário concreto de três generais e um traidor que nenhuma solução existe com mensagens orais (não assinadas) a menos que haja estritamente mais do que três vezes o número de traidores no total de participantes, e esboça o algoritmo recursivo de Mensagem Oral que atinge esse limite exatamente, a fundação formal sobre a qual todo protocolo tolerante a falhas bizantinas prático nesta disciplina se constrói.
O algoritmo de Castro e Liskov de 1999 é a resposta real e prática ao limite teórico que o conceito anterior provou: um cluster de 3f+1 réplicas tolera f réplicas bizantinas rodando três fases de mensagem por requisição, pre-prepare (o primário atribui uma ordem), prepare (toda réplica transmite e coleta 2f+1 prepares que batem para concordar sobre aquela ordem sem confiar só no primário) e commit (2f+1 commits que batem antes de qualquer réplica executar), mais um subprotocolo de troca de visão que substitui um primário que trava ou se comporta de forma suspeita, entregando, pela primeira vez, um protocolo de replicação de máquina de estado tolerante a falhas bizantinas rápido o bastante para sistemas reais, em vez de uma construção puramente teórica.
O PBFT assume algo que o design de Nakamoto de 2008 deliberadamente se recusa a assumir, uma lista de membros fixa e conhecida dentro da qual um protocolo de troca de visão pode votar; o consenso de Nakamoto em vez disso deixa qualquer um entrar anonimamente e substitui a identidade por custo computacional, propor o próximo bloco exige vencer uma loteria de prova-de-trabalho, e a segurança é só probabilística, um bloco é tratado como final uma vez que blocos posteriores suficientes são encadeados sobre ele, não no instante em que um quórum concorda, que é exatamente por que este conceito se delimita honestamente, este é um modelo de confiança genuinamente diferente (sem permissão, finalidade probabilística) que vale nomear com precisão pelo que ele troca contra o do PBFT (com permissão, finalidade determinística), não uma razão para transformar uma disciplina de sistemas distribuídos num curso de mecânica de blockchain.
`the-cap-theorem-a-precise-statement` provou um trade-off que só dispara durante uma partição de rede de fato, deixando sem resposta uma pergunta que importa todo dia que um sistema roda sem nenhuma partição, você ainda espera que toda réplica concorde antes de responder; a formulação PACELC de Abadi de 2012 nomeia esse segundo trade-off, sempre presente, explicitamente, se Particionado, escolha Disponibilidade ou Consistência (exatamente CAP), Senão, escolha Latência ou Consistência, e este conceito a usa para explicar, com precisão, por que as stores no estilo Dynamo que esta disciplina estuda a seguir escolhem consistência fraca mesmo quando a rede está saudável, não só quando ela está particionada, a motivação real sobre a qual o resto do material de banco de dados distribuído desta disciplina se constrói.
O relógio escalar de Lamport consegue provar que a aconteceu-antes de b, mas um sistema que aceita escritas em toda réplica, exatamente o que um sistema escolhendo Disponibilidade sob PACELC faz, precisa de uma ferramenta estritamente mais forte, uma que também consiga provar que duas escritas são genuinamente concorrentes (nenhuma causou a outra) em vez de só lhes atribuir alguma ordem total arbitrária; um relógio vetorial, um contador por réplica, incrementado no próprio evento daquela réplica e mesclado tomando o máximo componente a componente no recebimento de mensagem, recupera exatamente a ordem parcial que os relógios de Lamport achatam, deixando uma store comparar os vetores de duas escritas e decidir, com certeza, se uma domina a outra ou se ambas têm de ser mantidas como um conflito genuíno e não resolvido, a exata capacidade da qual a replicação sem líder dos próximos três conceitos depende.
`primary-backup-vs-quorum-based-replication` introduziu quóruns no nível de máquina de estado replicada, uma maioria concordando sobre um log ordenado; o Dynamo pega a mesma ideia de sobreposição e a aplica sem líder e sem log ordenado de forma alguma, uma chave replica para N nós (a sua lista de preferência, tipicamente os próximos N nós no sentido horário num anel de hashing consistente), uma escrita tem sucesso uma vez que W deles a reconhecem e uma leitura consulta R deles, e este conceito prova, só pelo princípio da casa dos pombos, que R + W > N garante que o quórum de leitura e o quórum de escrita sempre compartilham pelo menos um nó, então pelo menos uma réplica que a leitura toca viu a última escrita, a exata propriedade estrutural da qual cada uma das implantações de consistência ajustável do Dynamo (N=3, R=2, W=2 sendo o próprio exemplo condutor do artigo) de fato depende.
A prova de R + W > N do conceito anterior tem uma suposição silenciosa embutida, a de que os W reconhecimentos de uma escrita vêm dos nós de fato da lista de preferência da chave; o quórum relaxado do Dynamo deliberadamente quebra essa suposição por disponibilidade, se nós suficientes da verdadeira lista de preferência estão inalcançáveis, a escrita é aceita por quaisquer nós saudáveis que estejam a seguir na fila em vez disso, cada um armazenando o valor com um hint registrando a quem ele realmente pertence, e retransmitindo-o uma vez que aquele nó se recupera (hinted handoff), que é a escolha de Consistência versus Disponibilidade do CAP tornada concreta e operacional em vez de abstrata, uma escrita durante todo cenário deste conceito sempre tem sucesso, ao custo honesto de que a garantia de interseção de quóruns que o conceito anterior provou não mais se mantém estritamente até o hint ser entregue.
`eventual-consistency-and-its-real-guarantees` nomeou gossip e anti-entropia genericamente como o modo pelo qual as réplicas convergem; este conceito cobre os dois mecanismos concretos que o Dynamo de fato roda uma vez que o hinted handoff e os quóruns relaxados deixaram as réplicas genuinamente divergidas, o read repair (uma leitura voltada ao cliente que toca R réplicas e nota que elas discordam empurra o valor vencedor de volta para as obsoletas na hora, usando a mesma comparação de relógio vetorial de dois conceitos atrás) e a sincronização em segundo plano por árvore de Merkle (duas réplicas que seguram uma faixa de chaves inteira comparam um hash de raiz primeiro, e só recorrem em subárvores cujos hashes diferem, encontrando toda chave de fato divergida numa faixa de n chaves em O(log n) comparações em vez de comparar todas as n), e faz links cruzados para a construção completa e a prova de correção da própria estrutura de dados em vez de rederivá-la.
Todo conceito até aqui nesta disciplina replicou uma única chave; `acid-properties-precisely-defined` e `two-phase-locking-and-conflict-serializability` (`database-systems`) já provaram a Atomicidade para uma transação confinada ao gerenciador de travas de um nó, e este conceito estende esse mesmo requisito de tudo-ou-nada por entre nós, um coordenador pede a todo participante que prepare (trave as suas linhas e vote sim ou não) na fase um, depois diz a todos para fazer commit ou abortar na fase dois, e trabalha, com precisão, a única falha real do protocolo, se o coordenador falha depois de coletar votos todos-sim, mas antes de a decisão da fase dois alcançar todo participante, cada participante preparado fica travado segurando as suas travas indefinidamente, incapaz de unilateralmente fazer commit ou abortar sem arriscar discordar de uma decisão que o coordenador pode já ter tomado, o problema de bloqueio de fato e comprovável que os próximos dois conceitos existem para abordar.
O protocolo de commit em três fases de Skeen de 1981 é uma tentativa genuína e deliberada de remover exatamente o caso de bloqueio que o conceito anterior provou, ele insere uma fase de pre-commit entre votar e fazer commit para que qualquer participante que alcança o pre-commit já saiba que todo outro participante votou sim, deixando um coordenador recém-eleito fazer commit com segurança em nome de um participante travado em vez de forçá-lo a esperar para sempre; este conceito trabalha com precisão por que esse conserto só se mantém sob uma suposição que redes reais não satisfazem honestamente, atraso de mensagem limitado, mostrando um cenário concreto de partição de rede (não crash) onde dois grupos disjuntos de participantes cada um conclui com segurança uma decisão diferente e contraditória, que é exatamente por que o veredito honesto, enunciado de forma clara aqui, é que o 3PC resolve o bloqueio sob uma suposição de sincronia sem resolvê-lo sob o modelo assíncrono e propenso a partições que toda esta disciplina de resto assume, e por que os sistemas de produção recorrem ao conserto muito diferente que o próximo conceito cobre em vez dele.
A percepção real de Gray e Lamport em 2006, tornada explícita neste conceito, é que o coordenador do 2PC e a suposição de atraso limitado do 3PC nunca foram as únicas opções, já que esta disciplina (via `distributed-systems-i`) já tem um mecanismo que alcança acordo corretamente sempre que qualquer maioria de participantes está de pé e alcançável, e não mais, o próprio Paxos; o Paxos Commit substitui o coordenador único por um pequeno grupo Paxos (ou, numa implementação moderna, Raft) que decide o voto de prepare de cada participante, de modo que uma falha de coordenador não mais bloqueia ninguém, qualquer maioria sobrevivente do grupo de commit pode continuar com segurança, e este conceito rastreia essa exata ideia adiante até como o Google Spanner e o CockroachDB de fato rodam transações distribuídas de produção hoje, um grupo Raft ou Paxos por shard de dados decidindo os desfechos de commit, fechando o laço entre os próprios conceitos de consenso desta disciplina e o material de transações que abriu este tópico.
`eventual-consistency-and-its-real-guarantees` deixou a convergência inteiramente como uma esperança, o gossip normalmente a alcança, sem prova de que ela sempre tenha de; o artigo de 2011 de Shapiro, Preguica, Baquero e Zawirski a fortalece em Consistência Eventual Forte (SEC), quaisquer duas réplicas que entregaram o exato mesmo conjunto de atualizações estão no exato mesmo estado imediatamente, sem espera, sem passo de resolução de conflito necessário, e prova que um CRDT baseado em estado (CvRDT) alcança isso por construção sempre que os seus estados formam um semirretículo de junção (uma ordem parcial com uma mesclagem de menor-cota-superior que é comutativa, associativa e idempotente) e toda atualização só move uma réplica para cima nessa ordem; este conceito trabalha a prova concretamente no G-Counter (um contador só de incremento por réplica, a mesclagem toma o máximo componente a componente, o total é a soma) e no PN-Counter (dois G-Counters, incrementos e decrementos, o valor é a diferença deles), os dois CRDTs mais simples e a fundação direta sobre a qual os tipos de dados mais difíceis do próximo conceito se constroem.
Um CRDT baseado em estado envia o seu estado inteiro a cada mesclagem, desperdiçador uma vez que esse estado é um conjunto ou documento grande; um CRDT baseado em operação (CmRDT) envia só a própria operação e depende de uma garantia diferente e igualmente rigorosa provada no mesmo artigo de 2011, se todas as operações concorrentes comutam (o seu efeito não depende da ordem de entrega) e a rede fornece entrega confiável em ordem causal (uma operação nunca é aplicada antes das operações das quais ela causalmente depende), toda réplica ainda converge para o estado idêntico sem jamais comparar estados inteiros; este conceito trabalha essa garantia em dois tipos de dados que as stores da família Dynamo de fato entregam, o OR-Set (adição vence: toda adição é marcada com um identificador único novo, para que uma adição e uma remoção concorrentes do mesmo elemento resolvam mantendo a adição, resolvendo a ambiguidade clássica da corrida adição/remoção que um conjunto simples não consegue) e o Last-Write-Wins Register (usando os próprios relógios vetoriais desta disciplina ou um timestamp físico como desempate), nomeando honestamente, em Equívocos Comuns, exatamente onde a garantia dos CRDTs para (eles garantem convergência, nunca que o valor convergido é o que qualquer usuário individual pretendeu, um LWW-Register pode silenciosa e corretamente descartar uma escrita concorrente real e sem ordem causal).
Este capstone rastreia o exato cenário que o próprio artigo do Dynamo usa por toda parte, o carrinho de compras de um cliente, por uma partição de rede genuína e de volta, nomeando o conceito preciso responsável por cada passo: uma escrita de adicionar-ao-carrinho durante a partição cai só nos nós alcançáveis de um quórum relaxado, marcada com um hint por `sloppy-quorums-and-hinted-handoff`; uma adição concorrente do outro dispositivo do mesmo cliente cai no outro lado, inalcançável, o valor do carrinho de cada lado divergindo exatamente como `vector-clocks-and-detecting-concurrent-writes` prevê que duas escritas verdadeiramente concorrentes têm de fazer; uma vez que a partição cura, a comparação por árvore de Merkle da anti-entropia (`anti-entropy-read-repair-and-merkle-tree-synchronization`) encontra a chave divergida, e como o carrinho é modelado como um CRDT OR-Set em vez de um valor sobrescrevível simples, a mesclagem em `operation-based-crdts-and-practical-data-types` deterministicamente une ambas as adições sem item perdido e sem resolução manual de conflito, o mesmo desfecho de o item nunca foi perdido, mas uma contagem obsoleta foi brevemente mostrada que o artigo real do Dynamo relata, fechando o laço que esta disciplina abriu, com o próprio capstone de `distributed-systems-i` rastreando uma escrita linearizável por consenso, na escolha oposta e deliberada do trade-off do CAP, tornada totalmente concreta em vez de abstrata.