Project Companion — Distributed Systems

What the exam asks

From the course introduction (A0):

Oral discussion of a project. The final exam is a discussion, held once the project artefacts (doc and code) have been checked and judged satisfactory by the professor or tutor.
Tied to the course. The project must cover, or follow from, a specific topic of the course. It may be theoretical, technological or methodological, and its focus on distributed systems and its feasibility are negotiated in advance.
Understanding shows in the artefacts. Following and understanding classes and labs is “practically required” and “typically needs to show up in the project artefacts”. The professor and tutor help you see where and how to display it, but the final responsibility is yours, and it is checked in the discussion if doubts arise.

In practice: every design decision in the report should be named with the course vocabulary, justified by a course concept, and honest about its assumptions.

Thunk in one picture

Fig. P.1 — Thunk's work stealing as described in its README and Thunk.Scheduler.Distributed. The owner of a piece is the only authority for its result.

Programs are S-expressions; dc (divide and conquer) is the only parallel form. Solving a piece splits it, pushes the right half on the local deque and solves the left half. The right half is then taken back if nobody stole it, or awaited from the thief. A lost thief (crashed process or lost node, reported by a monitor) makes the owner solve the piece again. A language error is re-raised instead, because a deterministic program would fail again.

Around this core: a node joins a running cluster knowing a single seed and learns the other members by gossip, then starts stealing at once, even from a job already running. A dashboard node polls every worker's counters (deque length, steals, pieces evaluated and recovered) twice a second without evaluating anything. The demos (mergesort, word count, a ray-traced cube, a Mandelbrot set whose rows cost very different amounts of work) exercise the stealing.

Concept map: where the course shows up in Thunk

Chapter	Concept	In Thunk
1	distributed concurrent computing (S ≠ S′, T ≠ T′); transparency; decentralised algorithms; fallacies	Peers on different nodes, each with its own evaluators. “Which node solves each piece is up to the scheduler; the result is the same” is location and replication transparency for the programmer. No coordinator, following Raynal's point that only decentralised algorithms scale. The fallacies “the network is reliable” and “topology doesn't change” are exactly what monitors, re-execution and seed-plus-gossip membership address; joining at run time is openness.
2	no global clock; physical time only for intervals; happens-before	No clock synchronisation anywhere. Physical time enters only through failure detection (the BEAM's distribution heartbeat, a timeout). A piece's result happens-before the merge that uses it: the task tree is a causal structure.
3	code mobility; weak vs strong; receiver-initiated; resource binding	Pieces travel as data, and program definitions are fetched on demand by a thief that lacks them. This is weak mobility: no execution state moves, the piece restarts from its description. It is receiver-initiated, because the thief pulls. Pure pieces bind no local resources, which is why moving them is trivial.
4	failure models; recovery without checkpoints; logging	Assumed failures: process crashes and node loss (crash failures). Recovery keeps the input (the piece) at its owner until the result arrives. That is close in spirit to sender-based logging: re-execution replaces checkpoint and rollback, and purity makes it correct.
5	consistency; CAP; caching immutable data	No mutable shared state, so there are no replica-consistency problems for results. The one replicated state is membership: each node's member list is refreshed by gossip, so views are eventually consistent and stealing tolerates them being stale. Under a partition the owner re-solves locally: the job completes at the cost of duplicate work, and the value cannot be wrong because it is deterministic.
6	consensus; FLP; crashed vs slow	Thunk needs no consensus: each piece has exactly one owner. FLP's core difficulty, a crashed process looking like a slow one, is harmless here. A wrong suspicion only duplicates pure work.
7	ledgers as middleware	Not relevant to Thunk. Say so if asked, rather than forcing a connection.
8	architectural styles; process algebra	Decentralised peer-to-peer over message passing (BEAM processes); the dashboard is an observer that joins the cluster and polls, outside the computation. The steal protocol is small enough to model as a process term or a worker state machine in the report.
9	orchestration; reconciliation; self-healing	The Compose cluster could move to Kubernetes via Kompose (the tool used in the lecture). Kubernetes restarts a crashed node's container; Thunk's own mechanism recovers the work that was in flight. Two layers of self-healing, each with its own job.

Five design arguments

These are the points that show understanding best, because each one uses a course concept to explain a design choice.

Purity makes re-execution safe. A pure piece evaluated twice gives the same value, so at-least-once execution is as good as exactly-once. Recovery needs no checkpoints and no rollback of other processes (no domino effect, Ch. 4). The owner just solves the piece again.
False suspicion is harmless. In an asynchronous system a crashed node cannot be told apart from a slow one (Ch. 6). Most protocols must be careful here. In Thunk the worst case of a wrong suspicion is duplicate work, so safety never depends on timing and timeouts only affect performance.
One owner per piece: no agreement needed. Authority is structural (the process that split the work owns its halves), so there is nothing to vote on. Contrast this with replicated mutable state, which would need a consistency model (Ch. 5) or consensus.
Completion flows up the task tree. Every owner waits for its stolen halves, so the root's evaluation returning means the whole job is done. This plays the role that a termination-detection algorithm plays in a diffusing computation (Dijkstra–Scholten keeps a similar tree of acknowledgements). Explaining the analogy is a good use of the optional extension.
Decentralised scheduling. Idle workers pull from random peers; there is no central queue to become a bottleneck or a single point of failure. Stealing the oldest piece takes the largest remaining chunk, so fewer steals are needed. That is a classic work-stealing property, beyond the slides but easy to justify.

Limits to state yourself

The node that submitted the job holds the root of the tree, and if it dies the job is lost: a single point of failure per job. If an owner (not the root) dies, its own owner re-solves the whole enclosing piece, so the cost of a failure grows with the height of the lost subtree. Purity is an assumption about programs: side effects (I/O, randomness) would break arguments 1–3.

Questions to rehearse

Which failure model do you assume, and how are failures detected?

Crash failures of evaluator processes and whole nodes (Ch. 4). Detection comes from BEAM monitors: a DOWN message when a monitored process dies, or when the connection to its node is lost (heartbeat timeout). A partition therefore looks like node loss. Language errors are not faults to mask: they are deterministic, so they are re-raised.

A thief is slow, not dead, and the owner re-solves its piece. What happens to the late result?

Both computations produce the same value, so correctness is safe either way. Be ready to point to the code that shows what happens to the late reply (it is keyed by a reference, and the owner is no longer waiting for it). The cost is only duplicated work.

Why is there no consensus or leader election in Thunk? When would you need one?

Each piece has a single owner, and pure results need no agreement: any correct evaluation is the result. You would need agreement if nodes had to decide on shared mutable state or on exactly-once side effects, e.g. a job queue that must never run a job twice, or dynamic membership with a consistent view.

How does Thunk know a job has terminated?

Termination is detected structurally: every piece's owner waits for its halves, and the job ends when the root returns. Compare with Dijkstra–Scholten, where a diffusing computation keeps a tree of acknowledgements and the root knows the computation is over when all its children have acknowledged.

How does a node join, and does the cluster agree on who is in it?

A node needs one reachable seed; it retries its seeds every second until it knows a member, then pulls a random peer's member list every 2–3 s and connects to the nodes it did not know. A node that goes down is dropped on nodedown. There is no agreement: views are eventually consistent (Ch. 5), and that is enough, because a stale view only makes a steal request fail. Agreement would be needed if a decision had to rest on one consistent view (Ch. 6).

What moves between nodes, and what kind of mobility is it?

Pieces (work described as data, with a job id) and, on demand, the job's definitions. It is weak mobility (code plus data, no execution state), receiver-initiated (the thief pulls), with no bindings to local resources. Avoiding serialised closures keeps pieces self-describing and independent of the sender's runtime (Ch. 3).

Where does time matter in Thunk?

Nowhere for correctness. Physical time appears in failure detection (heartbeat timeouts) and in performance measurement. If you add a dashboard that merges logs from several nodes, order the log with Lamport timestamps plus node id, so that a result never appears before its piece (Ch. 2).

What limits scalability?

The split threshold (too fine means too much messaging), random stealing when little work is left, fetching definitions on first steal, and the fan-in at owners. Measure speedup as nodes are added, and show the curve in the report.

What would change if programs could have side effects?

Re-execution could repeat effects, so recovery would need exactly-once delivery or output commit (Ch. 4), caches could go stale (a consistency model would be needed), and false suspicions would become dangerous. The difference shows how much work purity does.

Artefact checklist

A report that makes the concepts visible:

System model. Processes and nodes, channels (BEAM messaging: reliable and FIFO between a pair of processes while the connection is up), failure model (crash), timing assumption (asynchronous, with timeouts used only for detection).
Architecture diagram (peers, deques, evaluators) with the style named: decentralised peer-to-peer.
Protocol. A sequence diagram of one steal: request, piece, definitions fetch, result, and the failure branch (DOWN, re-solve).
Worker state machine (idle / stealing / evaluating / waiting), optionally as a small process term.
Failure table: what fails, how it is detected, how it is recovered, and what it costs (thief process, thief node, owner, submitter).
Evaluation: speedup against nodes and threshold (Mandelbrot is the fair test, because its rows are unbalanced); the demo that kills a node mid-job and still finishes; a node joining mid-job and stealing at once, shown on the dashboard.
Limits and extensions: the submitter as a single point of failure, what purity assumes, and which optional extensions (termination detection, memoisation) would change which argument.

One sentence to be able to say

“Thunk replaces agreement with ownership and replaces rollback with re-execution. Both are correct because pieces are pure, so wrongly suspecting a slow node costs time, never correctness.”