Glossary of distributed systems

This is an attempted index of terms used in distributed system protocols.

Machines

  • Node: Any machine in the system.
  • Process: Originated from distributed protocols in the shared memory model. A process refers to a OS process. NOTE: Do not use unless in the shared memory model.
  • Server: A machine that is a part of the protocol in discussion.
  • Client: A machine that uses the outputs of the protocol in discussion.
  • User: A logical user (may consist of multiple clients) that uses the outputs of the protocol in discussion.
  • Replica: This has origins in the literature for crash fault tolerant systems and the primary-backup paradigm of state machine replication. This is a server that can be replicated and take a place of a server just by assigning a new identifier.
  • Leader: The designated node that drives progress in a protocol view or epoch. In classical protocols (e.g., Paxos, PBFT), the leader is stable across rounds within a view. Often conflated with proposer, but leader implies a persistent role.
  • Proposer: A node selected to propose a value in a given round. In blockchain protocols, "proposer" or "block producer" implies per-round selection (e.g., via VRF or round-robin). Distinguished from leader in that the role is ephemeral.
  • Learner: Originates from Paxos. A node that learns the decided value but does not participate in the agreement. In practice, often conflated with replicas or clients depending on context.
  • Dealer: Originates from threshold cryptography and MPC. A (possibly trusted) node that distributes shares of a secret to participants. In DKG protocols, the dealer role is distributed among the participants themselves, making the term ambiguous.
  • Validator: Originates from the blockchain literature. A validator is any node that validates the blockchain. E.g., a node that downloads the Bitcoin chain and verifies the proof of work. The (incorrect imho) usage in Proof of Stake systems is as the nodes that are a part of the SMR protocol. Further confusion: a "full node" verifies the chain but does not propose blocks, while a "validator" in PoS systems both verifies and participates in consensus, yet some systems use "validator" for both roles.

State

  • Operation: The unit of action on the state of a system. E.g., read, write, pay, readmany, etc.
  • Transaction: Originated from the database world. A transaction is a set of operations that a system executes atomically. These operations modify the state. Typically, they are deterministic.
  • Commit: Origin - databases. An action on the state where a transaction is accepted as successful and its effects are made visible to users.

Faulty Systems

  • Correct: A node is correct if it follows the protocol specification for a period under discussion. This node may be corrupted by the adversary but since it follows the protocol spec., it is deemed to be correct.
  • Honest: A node that is not under the influence of the adversary during the period under discussion.
  • Faulty: Any node that deviates from the protocol specification.
  • Non-faulty: All nodes that do not deviate from the protocol specification. Equivalent to Correct nodes.
  • BFT: A qualifier for the system. Often abused to mean BFT-SMR.
  • CFT: A qualifier for the system. Often abused to mean CFT-SMR or CFT-databases.
  • Fail-stop: It is an abstraction of a fault that will stop executing and fail. Note, others can detect the failure. ([1] [2])
  • Omission: A fault where some messages can be omitted (by the network or intentionally by the sender)
  • Crash: A fault where the node fails irreversibly, i.e., once a node crashes, it cannot come back alive in a protocol.
  • Commission: A fault where the node sends messages not specified by the protocol such as equivocating messages, invalid messages, and incorrect round messages.

Protocol Messaging

  • Send: A primitive where a message is sent to a neighboring node with a specific name. Implicitly assumes that the sending node knows its neighbors. In a partially connected system, the name must be one of the neighbors, otherwise it is undefined.
  • SendAll: A primitive where a message is sent to all neighbors. Implicitly assumes that the sending node knows its neighbors.
  • Multicast: A primitive where a message is sent to a subset of nodes in the system. Distinguished from SendAll in that the recipient set is explicit and may not include all neighbors.
  • Gossip/Epidemic Dissemination: A probabilistic messaging pattern where each node forwards a message to a random subset of peers. Convergence is probabilistic, not guaranteed per round. Often conflated with flooding, but gossip implies randomized fanout while flooding is deterministic.
  • Broadcast: This is a primitive that terminates, and ensures a consistent value is seen by all nodes in the protocol. Note: this conflates several distinct abstractions. Best-effort broadcast provides no guarantees if the sender crashes. Reliable broadcast ensures all correct nodes deliver the message if any correct node does. Byzantine broadcast (e.g., Bracha broadcast) additionally tolerates Byzantine senders.
  • Echo: A message pattern used in Byzantine broadcast protocols (e.g., Bracha). A node "echoes" a received value to amplify it, ensuring that enough correct nodes see it before delivering. Not a standalone primitive but frequently referenced as one.

Protocol Specification

  • Round: Originated from synchronous protocols. A round consists of one send and one wait action by a node. The wait action must terminate when all nodes finish their send action and messages are delivered. In synchronous protocols, a timeout is also a valid wait action.
  • Phase: A phase in a protocol changes the way messages are treated. If a message is handled in one way in a phase, in a different phase it should be handled differently. Example: View-change and steady-state phases. The proposals are handled differently in these phases.
  • Epoch: Technically, an epoch is a reference point from which some other time is measured. For instance, if you reset some counter, say round counter in a protocol, then this point marks a new epoch. Abused everywhere to mean a super-set of rounds, a time from which a new set of servers are used in a protocol, etc.

Protocols

  • Blockchain: Overloaded in the literature. Original meaning is a hash chain of data blocks. Widely used as a reference to cryptocurrency or its underlying agreement protocol. Use SMR, Atomic Broadcast, or the Ledger definitions.

Notes

  • I have gathered this after reading countless (does not imply large, just that I have lost count) papers with overloaded meanings.
  • As of 2024 May, I have lost all hope for standardization of the terminologies. This document serves to be aware.
  • I welcome all feedback at haxolotl dot research at gmail dot com
  • Acknowledgements:
    • Ittai Abraham

References

[1] Richard D Schlichting. “Fail-Stop Processors: An Approach to Designing Computing Systems.”
[2] Fred B. Schneider. 1987. “The fail-stop processor approach.”