Core Distributed Theory

One server, the leader, is the only one allowed to accept writes. It records each change and sends a copy to the other servers (followers). Reads can be spread across the leader and followers. Teams do this to survive a server crash and to handle more read traffic than one machine could.

Followers apply changes slightly after the leader because copying and applying takes time, especially under load. Read-your-writes means a user should always see their own recent changes - you guarantee it by making sure that right after someone writes, their next read goes to the leader or to a follower confirmed to be caught up, instead of a random possibly-stale replica.

Synchronous means the leader waits for a follower to confirm it got the write before telling the client 'done' - safer but slower. Asynchronous means the leader tells the client 'done' immediately and sends the copy in the background - faster but a crash can lose the last few writes.

Multi-leader means more than one server can accept writes, usually one per data center or region, so users write to a nearby server instead of one far away, and the system stays writable even if one region goes offline. The catch: two leaders can accept conflicting writes to the same piece of data at nearly the same time, and someone has to decide which one wins.

There's no single leader - a client writes to several replicas at once and only needs a certain number (W) to confirm before it's considered done; reads similarly query several replicas (R) and use the newest answer. If W+R is more than the total number of replicas, at least one replica in any read overlaps with one in the write, so a recent write is very likely seen. Read repair fixes replicas caught with stale data during a read; hinted handoff lets a temporarily unreachable replica's write be held by another node and delivered later.

A majority is needed so any two quorums always share at least one node - that overlap is what stops two different decisions from being made at once.

The leader adds the write to its own list first, sends copies to the other servers, and once more than half of them have saved it, the leader tells everyone it's official.

Safety means 'nothing bad ever happens' (like two leaders both thinking they won), and liveness means 'something good eventually happens' (like a write eventually succeeding). A system can stay safe while briefly failing to make progress.

Every election bumps a counter called a term. The old leader's term is now lower than the new one's, so once they reconnect, everyone - including the old leader - recognizes the higher term and steps down; and the old leader couldn't commit any writes alone anyway since it needs majority acks it never got.

2PC is for getting several different services to agree on one all-or-nothing transaction right now; consensus (Raft/Paxos) is for keeping several copies of the same data in agreement over time, and it survives a coordinator crashing, while plain 2PC can freeze if its coordinator dies mid-transaction.

When two halves of a system can't talk to each other, you must pick: either every request works but might return old/wrong data (available), or requests wait/fail until the data is provably correct (consistent). You can't have perfect answers and instant answers at once during that outage.

PACELC says: if there's a network split (P), pick availability or consistency (A or C) — that's CAP. But Else (E), even when the network is fine, you still must pick between faster answers (Latency) or more correct answers (Consistency), because waiting to check with other machines always costs time.

Real networks break sometimes — cables get cut, switches fail, regions lose connection. A system that spans more than one machine over such a network WILL face a partition eventually, so it can't promise to just never deal with one. 'CA' usually really means 'we haven't seen a partition happen yet' or 'we treat the whole system as down if one does.'

For the lock service, two 'leaders' at once could break everything, so it's worth going offline rather than risk that (CP). For shopping carts, showing an old cart is annoying but rarely catastrophic, and going offline during checkout loses sales, so keep answering even with slightly stale data (AP).

Instead of the whole database picking 'always fast' or 'always safe' once, each individual read or write can choose: talk to just one copy (fast, might be stale) or talk to most copies (slower, more sure to be correct). Different parts of the app can pick differently. The risk is picking 'fast' for something that actually needed to be 'safe' and getting wrong data where it matters.

Range partitioning keeps keys in sorted order across nodes (A-M on node 1, N-Z on node 2), so range scans are fast but one busy range can overload a node. Hash partitioning scrambles keys by a hash function, spreading load evenly but killing range scans.

Consistent hashing places both nodes and keys on a circular number line (a ring) using the same hash function; each key belongs to the next node clockwise from it. Adding or removing a node only shifts the keys between it and its neighbor, not the whole dataset, unlike mod-N hashing where nearly everything gets reshuffled.

A local secondary index lives on the same partition as the data it indexes, so writes stay on one partition but a query has to check every partition to be complete. A global secondary index is its own separate partitioned structure, so a query can hit just the index's partitions directly, but every write now has to update two different partitions.

With few nodes, random ring placement can give one node a much bigger arc than another, so it gets more data and traffic. Virtual nodes give each physical machine many small positions scattered around the ring instead of one big one, averaging out into roughly equal shares.

Rebalancing is moving data between nodes so each one holds a fair share after the cluster changes size. One approach creates many more partitions than nodes up front and just reassigns whole partitions to nodes as they join/leave; another splits/merges partitions dynamically as they grow or shrink. Done badly, it can overload the network or serve stale/missing data mid-move.

Computer clocks aren't perfectly synced - they drift apart between corrections and can even jump backward during a correction, so timestamps from two different machines can't be trusted to show which event really happened first.

If the system's clock gets adjusted backward (say by a time-sync correction) while you're timing something, the 'end' reading can look earlier than the 'start' reading, giving a negative or nonsense duration. Use a monotonic clock instead - one guaranteed to only ever move forward.

NTP asks a time server what time it is, times how long the round trip took, and assumes the trip there and back took equally long to estimate the network delay and correct the local clock. If the trip isn't actually symmetric, the correction is a little off.

Instead of pretending to know the exact time, TrueTime admits 'the real time is somewhere in this small window,' using GPS satellites and atomic clocks spread across data centers to keep that window tiny. This gives the database a guaranteed, honest bound to reason with instead of a false, precise-looking number.

Spanner picks a commit timestamp for a transaction, then literally pauses before letting anyone see the result, until it's sure real-world clocks everywhere have caught up past that timestamp. This guarantees that anything starting after the commit will see it, at the cost of adding a little delay to every write.

A failure model is an assumption about how something can break. Crash-stop: a node dies and never comes back. Crash-recovery: it dies but can restart. Omission: messages get lost. Byzantine: a node can lie or act maliciously. Stronger assumptions need more expensive protection.

With W+R>N, any read set and any write set must share at least one replica, so a read always sees the latest write even if some nodes are down or slow. If W+R is not greater than N, like W=2,R=2 on N=5, reads and writes might miss each other entirely and return stale data.

Synchronous replication waits for a copy to confirm the write before telling the client it succeeded, so no acknowledged write is ever lost, but it's slower and can stall if a replica is unreachable. Asynchronous replication confirms instantly and copies data in the background, so it's fast, but a crash right after can lose the last few writes.

Fencing gives each lease a rising number; the resource itself refuses any write whose number is older than the newest it has seen. That way even a confused old client that thinks it still owns the lock physically can't write, because the resource, not the confused client, enforces the check.

FLP proves that, in theory, a perfectly asynchronous network can always delay messages just enough to stall a consensus algorithm forever. Real systems dodge this by accepting that consensus might occasionally stall for a while, never violating correctness, rather than promising it will always finish quickly - and by using timeouts that work well enough in practice even though they aren't a formal guarantee.

Different computers' internal clocks are never perfectly synchronized, so their timestamps can disagree about event order even when one event actually caused the other. You need a way to order events based on what actually influenced what, not on unreliable clock readings.

Each process keeps a counter it bumps for every local event, and includes it in messages; a receiver sets its counter to max(own, received)+1. Bigger numbers don't prove causation -- two unrelated events on different machines can just happen to get different counter values.

Each process keeps a list of counters, one per process, not just one number. On its own events it bumps its own slot; on receiving a message it takes the slot-by-slot maximum with the sender's vector, then bumps its own slot. If neither vector is fully >= the other, the events are concurrent -- that's the extra power a single Lamport number can't give you.

An HLC pairs a physical wall-clock reading with a small logical counter that only increments when needed to break ties or preserve causality. That gives timestamps that stay close to real time (useful for humans and TTLs) while still guaranteeing that causally related events get increasing values, which plain physical clocks alone can't guarantee under clock skew.

A version vector has one counter per data replica/server, updated when a replica handles a write, rather than one counter per every client or process that ever touches the system. It's a cheaper, coarser-grained cousin of a full vector clock -- good enough to detect conflicting replica states without needing a slot for every client that ever connects.

Letting two computers both act as 'the boss' at once causes conflicts. Leader election is how a group agrees on exactly one boss. The Bully algorithm is simple: whichever live computer has the highest ID number always wins.

Every node waits a random amount of time to hear from the leader. Whoever times out first asks everyone to vote for it. Getting votes from more than half the nodes wins. The random wait stops everyone timing out together.

A lease is leadership with an expiration timer, like a rented spot you keep paying for. Renew before it runs out or lose leadership. Danger: a frozen leader might think its lease is still valid after someone else took over.

Even after everyone agrees on a new leader, the old leader may not know it's been replaced and could keep writing. Fix: storage refuses writes from anyone but the current leader, via a growing 'ticket number' that rejects old ones.

Nodes form a logical circle, each only talking to the next node. A node's ID gets passed around, each node swapping in its own ID if it's bigger, until the message returns carrying the biggest ID - that node wins.

2PC asks everyone 'can you commit?' first (prepare phase). Only if all say yes does it tell them to actually commit (commit phase). If anyone says no, everyone rolls back.

The participants can't tell if the coordinator had already decided to commit or abort before it died, so guessing wrong could break consistency. They're stuck holding locks — 'blocked' — until the coordinator comes back or someone intervenes.

2PC keeps everything locked until all three services agree, so it's always consistent but slow and fragile if one service is down. A Saga lets each step commit right away and fixes mistakes afterward with compensating actions, so it's faster and more resilient but briefly shows an inconsistent state.

A brief network blip cut the connection between the coordinator and a database right after it said 'ready to commit', so the database is stuck waiting and holding locks. An operator can wait for the coordinator to reconnect and resolve it automatically, or manually force a commit/rollback if it's urgent.

3PC adds a middle step so participants know 'everyone agreed to commit' before actually committing, letting them safely finish on their own if the coordinator dies. But if the network splits instead of the coordinator crashing, participants on different sides can still disagree, so it still gets stuck.

At-most-once means a message might get lost but never duplicated. At-least-once means it might arrive more than once but never lost. Exactly-once (arrives precisely one time) can't be truly guaranteed when networks can drop or delay messages - only faked using retries plus deduplication.

The client attaches a unique key to the request. The server remembers which keys it already handled and what it returned, so when the same key shows up again, it just replays the original result instead of charging the card a second time.

Both replicas might check the store, see nothing there yet, and both go ahead and process the request - so the action (like a charge) happens twice. The fix is to make 'claiming' the key an atomic, all-or-nothing step that only one replica can win.

The worker keeps a record of every event ID it has already handled. Before processing a new event, it checks that record; if the ID is already there, it skips the event instead of applying it again.

Instead of blindly repeating the action, redesign it so repeats do nothing extra: turn 'add 10 points' into 'record this specific +10 transaction with an ID', or check a 'have I already emailed this user for this event' flag before sending.

A short timeout catches crashes fast but often wrongly declares a slow-but-alive node dead. A long timeout avoids false alarms but takes longer to notice a real crash.

Phi is a number that grows the longer a node stays silent past its normal heartbeat rhythm; the app picks how high phi must get before acting, instead of one hard-coded timeout.

Because A's own path to B might just be a bad connection, not B actually crashing — asking others to check too avoids blaming B for a problem that's really just between A and B.

Push spreads new information fast at first but wastes messages once most nodes already know it; pull is good at catching stragglers but slow to start; push-pull combines both and converges fastest but costs the most bandwidth per round. Anti-entropy is a slower background pass that repairs anything the fast path missed.

Since gossip takes time to spread, nodes can briefly disagree about who's alive or dead; systems handle this by not trusting any single node's opinion alone and requiring agreement, refutation, or an explicit confirmation step before acting.