Messages, Models, and Agreement
Assistant Professor, IIT Indore
From your phone to the cloud — making many computers act as one
Work is spread across machines that do not share one memory.
Each machine learns about the world by receiving messages from others.
Somehow they must still agree, coordinate, or elect one process to act.
That tension — local communication, global coordination — is the heart of distributed algorithms.
Pick one system from the previous slide. Before algorithms, name the one fact that many machines must agree on.
For UPI, WhatsApp, search, games, or blockchains: what is the single shared outcome the users expect?
What could go wrong if two machines temporarily believe different versions of that outcome?
Which details would you throw away to get a clean graph-and-message model, and which details feel too important to ignore?
If the system is allowed to be briefly inconsistent, what extra rule must eventually repair the disagreement?
The same real system may need broadcast, leader election, ordering, and fault tolerance at different layers.
The whole subject begins with one structural choice.
Left: everyone talks to one server. Right: peers talk to each other directly.
One machine holds the truth; everyone asks it. There is a global clock and a single memory — the easy world.
But: if it's down, everything stops. It can't grow past one machine, and it can't be everywhere at once.
Many machines, each with its own memory and clock, cooperating only by sending messages.
Gains: scale, fault-tolerance, closeness to users. Price: no one sees the whole picture — coordination becomes the hard part.
Once you give up a shared clock and shared memory, even simple-sounding tasks — “tell everyone,” “pick one leader” — need real algorithms. That's what we'll build today.
Suppose a distributed system first elects one coordinator, then everyone follows that coordinator for the next minute.
Is the system now centralized, distributed, or temporarily both? What would you count as the algorithmic boundary?
What do we gain by having one coordinator, and what new failure point have we created?
If the coordinator crashes, what information must survive so the rest can choose a replacement?
Can the coordinator be a role rather than a machine? How would that change your proof obligations?
Many practical systems are distributed precisely because the identity of the "central" actor can change.
A simple, precise picture of a distributed system: nodes and messages.
A network is a graph: dots = computers, lines = links.
A distributed network is an undirected graph G = (V, E).
Nodes are processes; edges are communication links. We write n = |V| and m = |E|.
Messages travel only along edges, so information spreads one hop at a time.
Process v knows its identifier id(v), its incident links, and the messages it has received so far.
It does not start with the full graph G, and there is no shared memory to inspect.
dist(u,v) is hop-distance. The diameter D is the largest such distance in the graph.
Unique identifiers (IDs) come from a totally ordered set and fit in O(log n) bits. They are the only thing distinguishing otherwise-identical nodes — a theme that returns in leader election.
You are node v. After two synchronous rounds, you know everything within distance two, but nothing beyond that frontier.
Draw two different graphs whose radius-2 view around v is identical. What decision must v make the same way in both?
If a decision depends on a node at distance d, what lower bound on rounds follows immediately?
Do unique IDs help v see farther, or only help it compare names inside the part it has already seen?
Can two graphs have the same radius-t view around every node but require different global answers?
This is the seed of indistinguishability proofs: same local view forces same local behaviour.
Time advances in rounds t = 1, 2, …. In each round every process simultaneously (i) sends a message on each incident link, (ii) receives that round's incoming messages, (iii) updates its state by a transition function.
A message sent in round t arrives by round t+1. (Real systems are asynchronous; rounds just keep the ideas clean.)
A configuration is the tuple of all local states; an execution is the sequence C0, C1, C2, … the round function produces.
Local computation is unbounded and free — only communication is counted.
Now messages still arrive eventually, but with unpredictable delays; a process cannot tell "slow" from "silent".
Which line of the synchronous-round model breaks first? Sending, receiving, or deciding when to halt?
If no message arrives for one second, did a neighbour crash, or is the network just slow?
What extra mechanism might replace rounds: acknowledgements, clocks, failure detectors, or none of these?
Which theorem or impossibility result would you expect to become harder once timing is unreliable?
Synchronous rounds are a teaching scaffold; removing them turns timing into part of the problem.
There the scarce resource is time, and computation is the adversary. Here computation is free — the bottleneck is information: what a node can possibly know from local messages alone.
A distributed lower bound usually says: after this many rounds, some node still cannot have learned enough to distinguish two possible worlds.
Two simple questions we ask of every distributed algorithm.
Rounds until every process has halted, worst-case over all inputs (id assignments, graphs in the class). When information must cross the whole network, this is bounded below by the diameter D — the largest hop-distance between any two nodes.
Total messages sent over the whole execution, again worst-case. (Refine to bit complexity when message size matters.)
Same O, Θ, Ω asymptotics as always — but now in two resources that can trade off against each other.
In a centralized algorithm, the usual question is how many steps or comparisons one machine needs. In a distributed algorithm, the scarce resource is communication: what information can reach which node, and how many rounds or messages it takes.
The technique rhymes: adversary and indistinguishability arguments. We'll meet one on the ring.
Concept ① — Broadcast. One node has news; everyone must hear it.
The source tells its neighbours. The first time a node hears M, it relays to all other neighbours, then goes silent — gossip through a crowd.
if v is the source: send M to all neighbours; halt.
on first receipt of M from neighbour p:
parent(v) ← p # a tree edge
send M to all neighbours except p
ignore every later copy of M
First receipt sets the parent; later copies are ignored. Watch it run — press ▶ next.
Now that flooding's relay rule is clear, test the channel assumption: each link must actually deliver the messages sent on it.
If two neighbours transmit to the same receiver at once and both messages are lost, does flooding still guarantee broadcast?
Would random backoff, acknowledgements, or a fixed schedule restore the proof? Which one changes time complexity most?
If every failed transmission is counted as a message attempt, what happens to the clean 2m bound?
Can you define a collision model precise enough that the theorem statement becomes true or false, not vague?
Many "obvious" algorithms depend on hidden channel assumptions.
Synchronous flooding from s reaches every node, finishing in exactly ecc(s) rounds — the distance to the farthest node, at most the diameter D — and sending at most 2m messages. The parent pointers form a BFS (breadth-first search) tree rooted at s.
Induction on d: a node at distance d from s first receives M in round d — a shortest path delivers it by round d, and nothing is faster since each hop costs one round. The last node sits at distance ecc(s). Each edge carries M at most once per direction ⇒ ≤ 2m messages. ∎
Change exactly one assumption in the proposition and decide whether the statement survives.
One message may be lost, but processes do not know which one. What is the smallest repair that guarantees delivery?
The network may duplicate messages. Does the "first receipt sets parent" rule still produce a tree?
If each node can store only one unseen message at a time, can flooding overload a high-degree node?
Which assumption affects correctness, and which only affects the cost bound?
A theorem is always a theorem about a model; changing the model changes the contract.
The spanning tree informs all n nodes with only n−1 messages. Every other message is a duplicate — a copy arriving where the news already reached.
Counting both directions of every edge gives the clean bound 2m.
Broadcast is cheap. Electing one leader is where locality starts to bite.
Concept ② — Leader election. The network must single out exactly one node.
Each process has an output variable. In the final configuration exactly one process outputs leader; all others output non-leader.
Why bother? A leader becomes the coordinator — it holds the lock, sequences events, or starts the next phase. Many protocols begin by electing one.
We take the canonical setting: a ring of n nodes with unique IDs.
On a ring all nodes are structurally identical. Without distinct names, a deterministic algorithm cannot break the tie — we'll prove this at the end of the section.
Unique IDs supply the asymmetry; the algorithm only exploits it.
init: send id(v) clockwise.
on receiving value m:
if m > id(v): forward m # larger survives
if m < id(v): discard m # smaller dies
if m = id(v): output leader
# my id came home
We analyze LCR synchronously for clarity; Chang–Roberts originally runs asynchronously, with the same message counts.
Let v* = arg max id. Then exactly v* outputs leader.
A token m is discarded at the first node whose id exceeds it. Since id(v*) is maximum, its token is never discarded.
The maximum token is forwarded n times and returns to v*, which sees m = id(v*) and elects. Every other token dies before completing the lap. ∎
Press ▶ Play — or Step ▶ to advance round by round.
LCR has now used the phrase "send clockwise" as a real algorithmic assumption. Suppose neighbouring nodes may name their two ports inconsistently.
Can the exact LCR code still run? Where does the phrase send clockwise become ambiguous?
Try sending each ID in both directions. What new problem appears when the same ID returns from two sides?
Could leader election itself be used to orient the ring afterward? What circularity does that reveal?
With unique IDs, is unoriented leader election impossible, or just more expensive and more delicate?
Orientation is not a cosmetic detail; it is part of the distributed input.
Θ(n) rounds — the winning token needs n hops to close the lap.
Θ(n²). Adversarial input: IDs decreasing along the travel direction, so the token from the k-th node survives k hops — total 1+2+⋯+n = n(n+1)/2.
Θ(n log n) over uniformly random ID orderings (expected total ≈ n·Hn). We counted 15 in the demo.
LCR wastes messages because many small IDs travel several hops before a larger ID kills them.
What local evidence tells a process that its own ID is too small to keep competing?
What if nodes explore in phases of length 1, 2, 4, 8, ... before continuing? How might that save messages?
Even with clever phases, why should every "region" of the ring need to reveal at least one strong candidate?
Which algorithms are ruled out by the comparison-based lower bound, and which escape by using more than comparisons?
The jump from quadratic to n log n comes from killing hopeless candidates earlier.
Every comparison-based ring leader-election algorithm sends Ω(n log n) messages in the worst case (Frederickson–Lynch 1987; cf. Burns 1980 for asynchronous rings).
Hirschberg–Sinclair (1980) attains O(n log n), so the bound is tight.
No deterministic algorithm elects a leader on an anonymous ring — even synchronous, even with n known to all.
Induction on the round t. All nodes start in identical states and run identical code; by the ring's symmetry they receive identical messages, so after every round they remain in identical states. If one node ever outputs leader, all do at once — never exactly one. ∎
Same shape as the selection lower bounds: exhibit executions a node cannot tell apart, forcing identical behaviour. Here symmetry itself is the adversary.
Two escape hatches: unique IDs (what LCR uses) or randomization — break symmetry with high probability.
The anonymous-ring proof blocks deterministic algorithms because identical nodes stay identical forever.
If each node privately flips coins, are the states still forced to remain identical?
What if all nodes know n, a common orientation, or a distinguished edge? Which of these actually breaks symmetry?
Would you accept an algorithm that elects exactly one leader with probability at least 1 - 1/n?
How would the specification change if "eventually one leader with high probability" replaced deterministic certainty?
Impossibility results often point to the exact extra power needed to escape them.
So far everyone was honest. One last problem — to leave you thinking.
A traitor (coral) can tell different generals different things.
n processes; up to f are Byzantine — arbitrarily faulty, even malicious. A commander holds a value x ∈ {attack, retreat} and sends orders; every correct process must decide.
All correct processes decide the same value, no matter how the faulty processes behave.
If the commander is correct, every correct process decides the commander's value x.
For which n, f is this possible? That is where the next lecture begins.
Try the smallest nontrivial case: one Byzantine process, and everyone else follows the protocol.
Can two honest processes always tell whether the commander lied, or whether the other lieutenant is lying about the command?
What extra cross-check becomes possible when there are three honest processes instead of two?
Based on these cases, guess a threshold relating n and f.
Which assumption would change the threshold: digital signatures, synchrony, private channels, or authenticated sender IDs?
This is the gateway to Byzantine agreement: the model decides what "trust" means.
Whether agreement is even possible turns on n versus the number of liars f — sometimes it simply cannot be done. The proofs are, again, indistinguishability arguments. (Next lecture.)
Behind blockchains, avionics, and fault-tolerant databases. Proving such protocols correct is a prime target for model checking (Govind's lecture).
Graph model, rounds, two-resource complexity, broadcast, leader election, and one impossibility proof — enough to read on.
Three ideas to keep: a precise model, broadcast, and leader election — and the habit of asking “is this even possible?”
Many computers, no shared memory—
only messages, and they agree.
Thank you. Questions?
Debasish Pattanayak · IIT Indore · drdebmath.github.io