Problema del consens
El problema del consens és un problema fonamental en els sistemes distribuïts. La resolució del problema tracta d'establir sistemes fiables en sistemes distribuïts encara que un cert nombre de components del sistema treballen amb fallida. Exemples d'aplicacions de consens són la sincronització de rellotges en la xarxa, les bases de dades distribuïdes, l'algorisme PageRank, l'estimació d'estat (Observador de Luenberger), els videojocs multijugador, el control d'un Vehicle aeris no tripulats, el balanç de càrrega i d'altres.
Descripció del problema
El problema de consens requereix un acord entre diversos processos (o agents) per obtenir un únic valor de dades. Alguns dels processos poden fallar o deixar de ser fiables, de manera que els protocols de consens han de ser tolerants o resistents a fallades. L'aproximació de consens als sistemes distribuïts passa per arribar a una majoria d'acord entre els agents a través d'un sistema de votacions i consensuar un estat final.
Formalment, en informàtica teòrica, el problema del consens requereix un protocol que compleixi els següents criteris:[1]
Terminació: Qualsevol procés correcte ha de decidir un valor.
Integritat: Tot procés decideix un valor que ha estat proposat per un dels processos.
Acord: Tots els processos acorden el mateix valor.
Un protocol que pot garantir aquestes propietats en presència de menys fracassos es diu que és robust.
Un protocol serà robust quan es pot garantir correctament el consens entre n processos dels quals, com a màxim, t processos són en fallida.
Per avaluar el rendiment dels protocols de consens els factors claus són el temps i la complexitat dels missatges. El temps d'execució es dona en la notació O sobre el nombre de rondes d'intercanvi de missatges per arribar al consens. La complexitat de missatges es refereix a la quantitat de trànsit de missatges que genera el protocol. Altres factors poden incloure l'ús de la memòria i la mida dels missatges.
El protocol de consens tractarà de mantenir l'estat consistent entre les múltiples rèpliques connectades asíncronament no confiables.[2]
Exemples de protocols de consens
S'han elaborat diferents protocols o algoritmes que solucionen el problema del consens. Cada un s'aplica per a cert tipus d'entorns i tenen les seves pròpies característiques. Vegem alguns exemples:
- Raft
- Paxos i Multipaxos
- Zookeeper Atomic Broadcast
- Viewstamped replication
Referències
Bibliografia
- Herlihy, M.; Shavit, N. «The topological structure of asynchronous computability». Journal of the ACM, 46, 6, 1999, pàg. 858. DOI: 10.1145/331524.331529.
- Saks, M.; Zaharoglou, F. «Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge». SIAM J. Comput., 29, 5, 2000, pàg. 1449–1483. DOI: 10.1137/S0097539796307698.
Enllaços externs
- Algorisme Raft.
- Llista d'implementacions de Raft.
- Algorisme Paxos.
- Implementació Paxos en Java.
- Projecte Zookeeper.
- Article: Viewstamped Replication Revisitede.
