Daí meus queridos, boa noite!
Estamos de volta com a tradução de “Advances In Distributed Security”, essa é a terceira parte. No último versículo vimos a segunda.
Ordens Parcial e Total
Um problema básico de segurança e tolerância à falhas que deve ser resolvido é a determinação de segurança de qual ordem os eventos aconteceram. Se um contrato especifica uma data limite e fica pra cima da hora, como uma parte confiada ou um adjudicador terceiro vai determinar se o prazo foi cumprido? O resultado em si, e sua justiça, pode depender em decidir justamente quem chegou primeiro. Se Alice tenta gastar duas vezes um pedaço de dinheiro digital [C82], apenas o destinatário que verifica com o banco primeiro é que terá direito ao seu valor. Mas se os servidores do banco são replicados, qual dos dois destinatários Bob ou Charles consultou o banco primeiro? No caso de um serviço de título de propriedade replicado [S98], temos um problema semelhante – se Alice transfere seu título para outros dois proprietários, qual novo proprietário realmente recebeu a escritura? Se a propriedade for herdada por ordem de chegada, qual dos dois ou mais “corredores de terras” [land rushers] que competem por uma parcela lucrativa tem direito à terra?
Ordem de Lamport (Causal)
Imagine uma rede onde computadores não sabem como contar o tempo muito bem – eles estão sempre saindo da sincronização. (Infelizmente, tudo o que você precisa realmente pensar aqui é a internet atual com PC’s. Tal rede, chamada de rede assíncrona, carece de de um relógio global preciso e seguro pelo qual os computadores podem determinar a ordem na qual os eventos, que podem ser mensagens enviadas ou instruções executadas em uma máquina local em particular, aconteceram. Lamport [L78] estava entre os primeiros a abordarem o problema de como determinar a ordem de eventos em uma rede assim.
Uma ordem parcial significa que sabemos em que ordem alguns dos elementos estão, mas não temos certeza sobre alguns dos outros, ou alguns dos outros podem ser iguais. Um exemplo é a relação “menor ou igual à” entre grupos de números inteiros, alguns dos quais podem se repetir. Alguns dos inteiros que conhecemos são menores que alguns outros, mas um inteiro pareado consigo mesmo é igual. Uma ordem total, por outro lado, é como uma relação “menor que” entre inteiros únicos – podemos sempre saber a quando um inteiro é menor que outro – não resta ambiguidade. No caso de eventos, uma ordem parcial significa que, para alguns pares de eventos, sabemos se um ocorreu antes de outro e para outros não. Usamos os mesmos símbolos como usaríamos para o caso análogo dos inteiros, de modo que “x <= y “ significa “x ou ocorreu antes de y ou não sabemos se ocorreu antes ou depois de y”. Em um total de eventos, sabemos para quaisquer dois eventos qual ocorreu primeiro. Nós escrevemos “x < y” significando “x ocorreu antes de y.”
A resposta de Lamport para o problema do ordenamento de eventos foi mostrar que as partes (ou, usamos os termos equivalentes aqui, nodos na rede) podem concordar em uma ordem parcial de eventos baseado em relações causais entre esses eventos – ou pelo menos o subconjunto de eventos onde podemos determinar que a causação poderia ocorrer. Em uma rede, as partes influenciam umas às outras ao conversar umas com as outras – em outras palavras, ao mandar mensagens umas às outras. Lamport usou essas mensagens como o bloco básico de construção para sua ordem parcial, de acordo com as seguintes regras:
- Se um evento é local no nodo P, todos nodos não faltosos concordam na opinião do nodo P sobre ele.
- Todo nodo correto concorda que toda mensagem foi enviada antes de ser recebida.
- Se concordamos que o evento A ocorreu antes do evento B e que o evento B ocorreu antes do evento C, então concordamos que o evento A ocorreu antes do evento C. Em outras palavras, essa ordem parcial é transitiva.
[L78] L. Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System”, Communications of the ACM 21(7):558-565, Julho 1978.
[S98] N. Szabo, “Secure Property Titles with Owner Authority”
Foi essa a terceira parte da obra, no próximo versículo a quarta. Ricas Bençãos!
