Problema del consens

El problema del consens és un dels desafius fonamentals en els sistemes distribuïts. Consistix en conseguir que un conjunt de processos, que s'eixecuten en nodos independents i que solament poden comunicar-se per mig de l'intercanvi de mensages, acorden un únic valor. Alcançar consens és trivial en absència de fallos, pero es torna extremadament complex quan existixen factors com a fallos de nodos, pèrdua o retart de mensages, falta de sincronisació temporal i inclús comportaments maliciosos.

Per a resoldre este problema es dissenyen algoritmes o protocols de consens, que establixen les regles per mig de les quals els processos correctes (no maliciosos) es comuniquen, proponen valors i prenen decisions de manera coordinada.

Importància del consens

Els sistemes distribuïts són inherentemente propensos a fallos, ya siga per caigudes de nodos, comunicació no confiable o inclús fallos intencionats (fallos bizantins). Per a aumentar la confiabilidad d'estos sistemes, se sol recórrer a la replicació de senyes o estats, a on vàries còpies del mateix estat es mantenen en nodos distints.

No obstant, mantindre estes còpies consistents és un repte, especialment en entorns a on poden ocórrer fallos. Ací és a on intervenen els algoritmes de consens: permeten que les rèpliques acorden un orde comú d'operacions, garantisant que tots els nodos correctes mantinguen el mateix estat.

Per eixemple, en una base de senyes distribuïda, totes les rèpliques deuen aplicar les mateixes operacions en el mateix orde per a permanéixer sincronisades. Els protocols de consens implementen esta llògica per mig del paradigma de màquines d'estat replicades (State Machine Replication).

Models de fallos i dificultat del consens

El consens es veu afectat pel tipo de fallos considerats. Entre els models més comuns es troben:

• Fallos per caiguda (crash failures): un procés deixa de respondre.
• Fallos per omissió: es perden mensages.
• Fallos bizantins: els processos poden enviar mensages corruptes o comportar-se de manera arbitrària o maliciosa.

La dificultat del consens depén directament d'estos models. Un resultat clau en teoria de sistemes distribuïts és la teorema FLP (Fischer–Lynch–Paterson), que establix que:

En un sistema completament asíncrono, inclús si solament un procés pot fallar per caiguda, no existix un algoritme determinista que garantise sempre el consens.

Per això, molts protocols utilisen temporisadors, rondes, suposicions de sincronia parcial o mecanismes provabilístics per a sortejar esta llimitació.

Referències

• Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2), 374–382. https://doi.org/10.1145/3149.214121
• Lynch, N. (1996). Distributed algorithms. Morgan Kaufmann.
• Attiya, H., & Welch, J. (2004). Distributed computing: Fundamentals, simulations, and advanced topics (2.ª ed.). Wiley.
• Lamport, L. (1998). The part-clave parliament. ACM Transactions on Computer Systems, 16(2), 133–169. https://doi.org/10.1145/279227.279229
• Lamport, L. (2001). Paxos made simple. ACM SIGACT News, 32(4), 51–58. https://doi.org/10.1145/568425.568433
• Ongaro, D., & Ousterhout, J. (2014). In search of an understandable consensus algorithm (Raft). In Proceedings of the USENIX Annual Technical Conference (pp. 305–319).
• Oki, B. M., & Liskov, B. (1988). Viewstamped replication: A new primary copy method to support highly-available distributed systems. In Proceedings of the 7th Annual ACM Symposium on Principles of Distributed Computing (pp. 8–17). ACM. https://doi.org/10.1145/62546.62549
• Hunt, P., Konar, M., Junqueira, F. P., & Reed, B. (2010). ZooKeeper: Wait-free coordination for internet-scale systems. In Proceedings of the USENIX Annual Technical Conference (pp. 145–158).