Chapter 2: System models, order, and time

Introduction

The chapter introduces system models, order, and time as tools for reasoning about what distributed-system behavior can and cannot reveal.

• Timing guarantees and missing messages: Distinguish what a missing message tells us in synchronous and asynchronous systems: a known delivery bound makes a missed deadline evidence of failure, while without timing guarantees the message may simply be delayed.
  Why it matters: The timing model determines whether silence is evidence of failure or leaves the cause uncertain.
• Models order and time: Describe the chapter's scope: it examines system models, including component and network behavior, alongside order, physical time, and logical time to understand what constrains distributed-system behavior.
  Why it matters: These are the perspectives the chapter uses to make distributed-system behavior easier to reason about.

Key terms: synchronous system, asynchronous system, timing guarantees, known bound, system models, component and network behavior, order, physical time, logical time

2.1 System models

This section defines a system model and explains why a distributed algorithm’s correctness depends on its assumptions.

• System model assumptions: Describe a system model as the assumptions about a distributed system’s components, network, and timing behavior under which an algorithm or protocol is considered.
  Why it matters: Naming the assumptions makes it possible to discuss when an algorithm applies.
• Correctness depends on the model: Explain that an algorithm or protocol can be correct under one system model but incorrect under another because changing an underlying assumption can invalidate it.
  Why it matters: A correctness claim is meaningful only alongside the conditions under which it holds.

Key terms: system model, components, network, timing behavior, algorithm, protocol, correct

2.1.1 Theory and practice

This section distinguishes theoretical and practical system models while showing that some models are useful for both.

• Theoretical and practical system models: Distinguish how theoretical and practical system models are used: theoretical models examine feasibility, impossibilities, and bounds, while practical models assess possible solutions against engineering concerns.
  Why it matters: The distinction helps you explain what question a system model is meant to answer.
• Overlap between model uses: Explain that some system models are relevant to both theory and practice, including models underlying consensus algorithms such as Viewstamped Replication, Paxos, and Raft.
  Why it matters: Theoretical and practical models are not mutually exclusive categories.

Key terms: theoretical system models, practical system models, impossibilities, possibilities, intersection, consensus algorithms, Viewstamped Replication, Paxos, Raft

2.1.2 Synchronous distributed systems

This section defines synchronous distributed systems by their clock and timing guarantees while separating those guarantees from assumptions about failures and message loss.

• Synchronous timing guarantees: Explain that a synchronous distributed system assumes clocks are perfectly synchronized or differ by at most a known bound, and that events occur at strict times or within bounded delays. Distinguish models with no timing uncertainty from those with bounded timing uncertainty.
  Why it matters: These timing guarantees provide a basis for comparing different system models.
• Timing and failure assumptions: State that a synchronous system model does not, by itself, specify whether components fail or messages are lost; those assumptions are treated separately.
  Why it matters: Keeping timing guarantees separate from failure assumptions prevents the model from implying guarantees it does not make.

Key terms: synchronous distributed systems, physical time, bounded delay, bounded uncertainty, synchronous system model, component failure, message loss

2.1.3 Asynchronous distributed systems

Distinguishes two asynchronous system models by their treatment of time and explains why that difference matters for timeouts and solvability.

• Asynchronous time models: Distinguish an asynchronous model with no notion of time from one with a weak notion of time: neither bounds event timing or delays, but only the weak-time model gives components access to clocks, which are unsynchronized and have unknown deviation.
  Why it matters: The word asynchronous alone does not tell you what timing tools a component has.
• Timeouts and problem solvability: Explain that components cannot use timeouts when they have no notion of time, but can use them with a weak notion of time. State that this distinction can determine whether a problem has a solution, so the meaning of asynchronous must be checked in context.
  Why it matters: A seemingly small change in clock assumptions can change what a system can accomplish.
• Independent failure assumptions: State that an asynchronous system model, like a synchronous one, does not by itself specify whether components fail or messages are lost; those require separate assumptions.
  Why it matters: Timing assumptions should not be mistaken for failure or message-loss assumptions.

Key terms: asynchronous system model, no notion of time, weak notion of time, arbitrary delay, unknown deviation, timeouts, failure detection, failure mitigation, asynchronous system, component failure

2.1.4 Partially synchronous systems

This section introduces partial synchrony as a realistic system model and explains how protocol guarantees change when a system behaves asynchronously.

• Partially synchronous system model: Explain that real distributed systems are neither entirely synchronous nor entirely asynchronous: components and networks usually behave as expected but sometimes become slow or time out.
  Why it matters: Partial synchrony gives you a model for reasoning about systems whose behavior changes over time.
• Safety and liveness priorities: Describe the typical protocol-design approach: seek both safety and liveness during synchronous operation, but prioritize safety over liveness during asynchronous operation so that nothing bad happens even if progress stops.
  Why it matters: This distinction explains why a protocol may stop making progress rather than risk an unsafe result.

Key terms: partially synchronous system model, synchronous, asynchronous, safety, liveness, safety and liveness guarantees

2.1.5 Component and network behavior

This section defines common component and network failure behaviors used to describe a distributed system model.

• Stopping and resuming components: Distinguish Crash-Stop, Omission, and Crash-Recovery failures by whether a component resumes and whether it may lose state.
  Why it matters: These distinctions determine what a system can expect from a component after it stops taking steps.
• Arbitrary component behavior: Explain that a Byzantine failure allows a component to behave arbitrarily, including deceptively deviating from its intended algorithm.
  Why it matters: It describes a broader kind of component failure than simply stopping or losing state.
• Unreliable network behavior: Describe message reordering, duplication, and loss, and state the section's assumption that a network cannot lie by delivering a message no component sent.
  Why it matters: These behaviors set the limits on what message delivery can be assumed to do.

Key terms: Crash-Stop failure, Omission failure, Crash-Recovery failure, internal or external steps, state, Byzantine failure, message reordering, message duplication, message loss, unreliable network

2.1.6 Realistic system models

The section combines timing, failure, and network assumptions into the practical system model used throughout the book.

• Practical timing assumptions: Explain that distributed systems are usually synchronous but can be asynchronous at times, so the practical model is partially synchronous.
  Why it matters: This timing assumption sets expectations for how a distributed system behaves.
• Component and network failures: Describe the model's component failures and unreliable network: components can crash, omit actions, or recover with volatile state lost and durable state retained; messages can be reordered, dropped, or duplicated. State that the book largely sets aside Byzantine failures.
  Why it matters: These assumptions define which failures the book's later discussions must account for.

Key terms: synchronous, asynchronous, partially synchronous, Crash-Stop failure, Omission failure, Crash-Recovery failure, volatile, durable, unreliable network

2.2 Order and time

The section uses a proposer–acceptor example to show why distributed systems need a shared order for dependent actions, what makes an ordering problem a race condition, and how a coordinator can establish an order.

• Order of dependent actions: Explain why collaborating components may need to apply actions in the same order, using the section’s addition and multiplication example.
  Why it matters: When actions do not commute, different delivery orders can leave components with different results.
• Race conditions as execution outcomes: Define a race condition in the section’s terms and relate it to the possible delivery orders in the proposer–acceptor example.
  Why it matters: This definition identifies races by their possible correct and incorrect outcomes, not by a particular programming mechanism.
• Coordinator-established request order: Trace how the coordinator assigns an order to requests and how acceptors use that order despite out-of-order delivery. Explain why the coordinator need not preserve the order in which proposers sent their requests.
  Why it matters: A shared assigned order lets acceptors apply noncommutative operations consistently without relying on network arrival order.

Key terms: commutative, order, proposers, acceptors, race condition, possible executions, delivery order, coordinator, tag, missing requests

2.2.1 The happened-before relationship

This section defines happened-before as a partial order of distributed events and uses it to distinguish causal order and concurrency from physical-time parallelism.

• Happened-before ordering rules: Explain how events are ordered within a component, across a message send and its corresponding receive, and transitively through other events.
  Why it matters: These rules let you reason about event order without assuming a single global sequence.
• Partial order and potential causality: Describe happened-before as a partial order: either event can precede the other, or neither does. Explain that it captures possible influence, not proof of actual influence, and why causal order matters when reasoning about a system.
  Why it matters: Possible causal connections help you spot behavior that could violate the order the system relies on.
• Concurrency versus physical parallelism: Distinguish concurrency of events and operations from parallelism of operations. Describe an operation by its start and end events: operations are concurrent when neither ends before the other begins in happened-before order, whereas parallel operations overlap in physical time.
  Why it matters: The distinction keeps logical ordering separate from physical-time overlap.

Key terms: happened-before relationship, intracomponent, intercomponent, transitivity, partial order, concurrent, causality, concurrency, parallelism, logical clock

2.2.2 Time and clocks

This section introduces clock consistency as the condition that lets timestamps preserve the happened-before order of events across distributed components.

• Clock consistency and event order: Explain that distributed systems use clocks to timestamp events, and that clock consistency requires an earlier event to have a smaller timestamp than an event that happens after it, even when the events occur on different components.
  Why it matters: This condition makes timestamps useful for reasoning about causal order across components.

Key terms: clocks, timestamps, clock consistency, happened before, causal ordering

2.2.3 Physical time and physical clocks

This section explains why physical clocks cannot reliably order events across components and how synchronization and monotonic clocks address different parts of the problem.

• Wall clock and local clocks: Distinguish the hypothetical perfect wall clock available to a global observer from the imperfect physical clock a component actually uses to timestamp events.
  Why it matters: The distinction prevents a model’s global reference time from being mistaken for a clock a component can read.
• Clock skew and drift: Explain how clock skew is a difference between clock readings, while clock drift is a difference in tick rates that makes readings diverge over time, and why both complicate comparisons across components.
  Why it matters: Different timestamps do not necessarily reveal the true order or interval between events on separate components.
• Clock synchronization limits: Describe how NTP mitigates skew and drift by having an NTP server broadcast its clock reading and clients adjust their clocks, and explain why a backward adjustment creates a problem.
  Why it matters: Synchronizing clocks reduces disagreement but can make an adjusted clock appear to move backward.
• Time-of-day and monotonic clocks: Distinguish a time-of-day clock, which aims to track wall-clock time but can move backward during synchronization, from a monotonic clock, which is independent of wall time and does not move backward. Explain why monotonic readings can be compared within a component but not across components.
  Why it matters: Choosing the right clock depends on whether the task needs an approximate wall-clock timestamp or a reading that cannot go backward.

Key terms: physical clock, physical time, wall clock, clock skew, clock drift, Network Time Protocol (NTP), NTP server, NTP clients, clock synchronization, time-of-day clock

2.2.4 Logical time and logical clocks

This section explains how logical clocks order events and shows how Kafka offsets and etcd sequence numbers act as logical timestamps within limited scopes.

• Lamport clock event ordering: Explain how logical time uses the happened-before relationship to order events, and describe how Lamport clocks assign timestamps that increase across causally related events.
  Why it matters: This gives you a way to reason about event order without relying on physical clock readings.
• Scope of practical logical timestamps: Describe how Kafka partition offsets and etcd per-key sequence numbers resemble logical timestamps, including what each orders and why values from different partitions or keys cannot be compared.
  Why it matters: It helps you recognize useful logical clocks in real systems without assuming they provide a system-wide order.

Key terms: logical time, logical clocks, Lamport clock, happened-before relationship, logical timestamp, Apache Kafka, topic, partition, offset, etcd

2.2.5 Physical clocks vs. logical clocks

This section contrasts physical and logical clocks as complementary ways to reason about time and event order in distributed systems.

• Physical and logical clock roles: Distinguish how physical clocks measure the duration between events within a component, while logical clocks establish event order across components. Explain why logical clocks can provide consistent ordering when physical clocks drift or are out of sync.
  Why it matters: Choosing the right kind of clock prevents unreliable physical timestamps from being mistaken for a dependable system-wide event order.

Key terms: physical clocks, logical clocks, clock drift, clock skew, synchronization problems

2.3 Summary

This chapter summary connects system-model assumptions and failures to algorithm correctness, then recaps why event order and logical clocks matter.