Distributed System

Reasons for Replication

Replicating data improves reliability, availability, performance, and scalability but makes consistency harder.

Data Store

A logical collection of data items that is physically distributed and replicated across multiple machines.

Consistency Model

A rule set defining what values reads can return and how writes appear across replicas.

Sequential Consistency

All operations appear in one global order that respects each process's program order.

Causal Consistency

Causally related writes must be seen in the same order everywhere; concurrent writes may differ.

Continuous Consistency

Allows bounded differences in values, staleness, and update ordering between replicas.

Conit

A consistency unit that defines how much deviation is allowed for a specific piece of data.

Vector Clock

A timestamp vector used to track causality and detect which operations happened before others.

Eventual Consistency

If no new updates happen, all replicas eventually converge to the same state.

Numerical Deviation

A limit on how far numeric values of replicas may differ.

Staleness Deviation

A limit on how old a replica’s data is allowed to be.

Ordering Deviation

A limit on how many updates a replica can be ahead or behind another.

Remote-Write Protocol

All writes go to one primary replica, ensuring consistency but causing client blocking.

Local-Write Protocol

The primary moves to the client doing the write, reducing blocking but adding migration overhead.

Data-Centric Consistency

Consistency guarantees defined from the data system’s perspective (e.g., sequential, causal, eventual).

Partial Failure

Some components fail while the rest of the distributed system keeps running.

Fault Tolerance

The ability to keep operating correctly even when some components fail.

Dependability

A system’s trustworthiness made up of availability, reliability, safety, and maintainability.

Availability

The system is ready to provide correct service at any moment.

Reliability

The system runs continuously without failure over time.

Safety

Failures must not cause catastrophic or dangerous outcomes.

Maintainability

Failed components can be repaired or restored easily.

Failure Models

Describes different types of failures: crash, omission, timing, response, and Byzantine.

Redundancy

Extra information, time, or hardware used to mask or recover from failures.

Information Redundancy

Extra bits like parity or Hamming code used to detect or correct errors.

Time Redundancy

Repeating operations to recover from temporary faults.

Physical Redundancy

Adding backup hardware or processes to tolerate failures.

Triple Modular Redundancy (TMR)

Three modules vote so the system works even if one fails.

Process Resilience

Replicating processes so others can take over when one fails.

Process Groups

A set of replicated processes acting as a single logical unit for reliability.

k-Fault Tolerance

A system that can survive k failures; needs k+1 replicas for silent faults or 3k+1 for Byzantine.

Byzantine Failure

Arbitrary or malicious behavior where components send incorrect or conflicting information.

Consensus Problem

All correct processes must agree on a value even with failures or delays.

Byzantine Generals Problem

Loyal nodes must agree despite traitors sending incorrect messages.

Byzantine Agreement Requirements

Loyal nodes must decide the same value, and traitors must not force a bad result.

Agreement in Faulty Systems

Feasibility depends on timing guarantees, message ordering, and communication model.

Replication for Fault Tolerance

Replicas keep the system running smoothly even when some components fail.