Leslie Lamport enviou um algoritmo errado. Um revisor o quebrou — então ele encontrou o Bakery Algorithm.

Leslie Lamport certa vez achou que o clássico problema de exclusão mútua parecia fácil. Escreveu uma solução curta, enviou para uma revista e um revisor rapidamente mostrou que ela estava errada.

O erro não encerrou a ideia.

Irritou Lamport o suficiente para que ele sentasse e resolvesse o problema de verdade.

O resultado virou o Bakery Algorithm — uma das ideias mais conhecidas da computação concorrente e ponto de partida para grande parte do trabalho posterior de Lamport em sistemas distribuídos.

O problema parece simples até duas coisas acontecerem ao mesmo tempo

Imagine vários processos tentando entrar na mesma seção crítica.

Somente um pode estar lá com segurança por vez.

Se dois entrarem juntos, dados compartilhados podem ser corrompidos.

Então cada processo precisa de uma forma justa de decidir quem entra primeiro, sem depender de um controlador central.

Lamport inicialmente achou as soluções publicadas desnecessariamente complicadas.

Escreveu um algoritmo mais simples.

O revisor encontrou o erro.

Mais tarde Lamport escreveu que aquilo o deixou bravo consigo mesmo o bastante para encontrar uma solução real e também despertou seu interesse duradouro em provar a correção de algoritmos concorrentes.

A solução parecia uma padaria

A metáfora era quase simples demais.

Entre numa padaria cheia.

Pegue um número.

Espere até que seu número seja o menor entre os que ainda aguardam.

Então é sua vez.

Lamport transformou essa regra social em algoritmo.

Cada processo que quer entrar na seção crítica escolhe um número maior que os números que consegue enxergar.

Os processos esperam em ordem numérica.

Se dois escolherem o mesmo número, um critério fixo — como o ID do processo — desempata.

Ninguém precisa ficar no centro coordenando todos.

A ordem emerge dos números.

A parte extraordinária era ainda mais forte que a metáfora

O Bakery Algorithm tem uma propriedade estranha que o próprio Lamport destacou depois.

Suponha que um processo esteja escrevendo um número na memória exatamente quando outro processo o lê.

Em muitos algoritmos, essa sobreposição seria perigosa sem uma leitura perfeitamente atômica.

O algoritmo de Lamport tolera uma situação muito mais fraca.

A leitura sobreposta pode ver um valor intermediário estranho e, mesmo assim, o algoritmo pode preservar a exclusão mútua dentro de seu modelo.

Lamport escreveu depois que não projetou essa propriedade de propósito.

Disse sentir que não tinha exatamente inventado o algoritmo, mas descoberto.

Uma analogia física revelou uma estrutura matemática

A metáfora da padaria funciona porque separa duas perguntas que engenheiros frequentemente misturam.

Primeira: quem quer acesso?

Segunda: em que ordem o acesso deveria acontecer?

O ticket não faz o trabalho.

Ele cria uma ordem que todos conseguem observar de forma independente.

É um padrão útil muito além de padarias.

Número de fila.

Timestamp.

Número de sequência.

Número de versão.

Contador monotônico.

Todos transformam uma discussão bagunçada sobre “quem chegou primeiro?” em algo sobre o qual o sistema consegue raciocinar.

Sistemas distribuídos estão cheios de filas invisíveis

Sistemas modernos raramente parecem uma padaria.

Parecem bancos de dados, job workers, message brokers, serviços replicados, microservices e infraestrutura cloud.

Mas o problema de coordenação está em toda parte.

Dois workers tentam atualizar o mesmo registro.

Dois líderes acreditam que deveriam controlar o mesmo recurso.

Várias requisições chegam sem um relógio global perfeito.

Máquinas diferentes veem eventos em ordens diferentes.

A parte difícil nem sempre é o cálculo.

É o acordo sobre a ordem.

O trabalho posterior de Lamport — logical clocks, causalidade, replicated state machines, Paxos, safety e liveness — continuou voltando a versões do mesmo problema.

O primeiro fracasso talvez tenha sido quase tão importante quanto a solução

A história da tecnologia costuma ser contada como se pessoas brilhantes enxergassem a resposta imediatamente.

O relato de Lamport é menos elegante e mais útil.

Ele olhou um problema famoso.

Achou fácil.

Enviou uma resposta errada.

Foi corrigido.

E passou a tratar correção com muito mais seriedade.

O revisor não apenas rejeitou um artigo.

Ajudou a mudar a direção do trabalho de Lamport.

Nas décadas seguintes, ele se tornou figura central na teoria e na prática de sistemas concorrentes e distribuídos.

Em 2013, a ACM concedeu a ele o Turing Award por contribuições fundamentais que incluem causalidade, logical clocks, safety e liveness, replicated state machines e consistência sequencial.

A lição não é “use tickets de padaria no código”

A lição profunda é sobre abstração.

Quando um problema de coordenação fica confuso, procure uma regra que cada participante consiga aplicar localmente.

Dê ao sistema um mecanismo observável de ordenação.

Torne os critérios de desempate explícitos.

Depois raciocine sobre o invariante que precisa ser preservado.

As ideias mais elegantes de sistemas distribuídos costumam parecer simples depois de descobertas.

Essa simplicidade não prova que o problema era fácil.

Prova que alguém encontrou o modelo certo.

Que problema complicado de coordenação no seu sistema ficaria mais simples se cada participante pudesse apenas “pegar um número”?

Fontes

• Microsoft Research — A New Solution of Dijkstra’s Concurrent Programming Problem
• Microsoft Research — Proving the Correctness of Multiprocess Programs
• Leslie Lamport — My Writings
• ACM — Leslie Lamport, 2013 A.M. Turing Award
• Microsoft Research — Leslie Lamport Receives Turing Award
• Retrato usado na imagem destacada — Leslie Lamport, foto de Andrej Bauer, CC BY-SA 2.5 SI via Wikimedia Commons. A composição gráfica e o derivado 16:9 são publicados sob a mesma licença.