Saltar al contenido ForoHackers

Consensus: start here

Consenso
#2927 · · Citar · Denunciar

Consensus is the problem of getting several machines to agree on one value, or one sequence of values, even when some crash and messages go astray. It sits under replicated databases, lock services and configuration stores: whenever many nodes must act as one, something runs a consensus protocol.

Key concepts

  • Safety and liveness: nothing wrong is ever decided, and something is eventually decided; protocols guarantee the first always and the second only under good conditions.
  • FLP impossibility: in a fully asynchronous system, no deterministic protocol can guarantee agreement if even one node may crash.
  • Leader election and terms: Paxos and Raft pick a leader for a numbered term, and a higher term replaces a stale leader.
  • Replicated log: the nodes agree on an ordered log of commands and apply it in the same order, forming a replicated state machine.
  • Failure models: crash faults need a majority of nodes; Byzantine faults, where nodes lie, need more than two thirds honest.

Vocabulary

  • Quorum: a majority whose overlap guarantees two decisions cannot conflict.
  • Term or ballot: a number that orders leaders in time.
  • Commit: the point after which an entry can never be lost.
  • Replicated state machine: identical copies of a deterministic program fed the same log.
  • Byzantine fault: a node that behaves arbitrarily, including maliciously.

What to study, in order

  1. Distributed-systems basics: asynchrony, crash faults, quorums.
  2. Read the Raft paper, which was written to be understood, and follow its figures with a pencil.
  3. Implement leader election, then log replication, then test with a simulator that drops and delays messages.
  4. Read about Paxos and compare it with Raft: where do they differ, and why?
  5. Learn what Byzantine fault tolerance costs, and when it is worth it.

Related tags

#distributed-systems #blockchain #formal-methods #concurrency

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder