# Deadlock freedom > How Brine proves at compile time that every rank of a world program makes the same communication calls in the same order, the uniform and varying values behind it, errors E0510, E0511 and E0512, and what the check allows. Source: https://docs.brinelang.org/parallelism/deadlock-freedom/ A `world` program can’t deadlock. Every `world` call is collective, so a program could only hang if some ranks skipped a call that others made. The compiler rules that out: a communication call may not depend on anything that can differ between ranks, such as `world.rank()`, and the arguments that steer communication must be the same on every rank. ## Why collectives are enough [Section titled “Why collectives are enough”](#why-collectives-are-enough) In MPI-style code, deadlocks come from unmatched messages: rank 0 waits in `recv` for a message rank 1 never sends, or both ranks wait for each other. Brine has no `send` and `recv` ([E0512](/reference/errors/#e0512)). Every call in the [`world` API](/parallelism/world/#the-api) involves every rank, and point-to-point messages are written with `shift` and `exchange`, which are collectives too. So if every rank makes the same sequence of `world` calls, every receive has a matching send: all ranks run the same program, and the static types make the messages agree. The compiler’s job is to make sure the sequence can’t differ. ## Uniform and varying values [Section titled “Uniform and varying values”](#uniform-and-varying-values) The check, in `compiler/uniform.br`, classifies every value: * **Uniform:** the same on every rank. Constants, `world.size()`, `args()`, `os.name()`, `os.arch()`, and the results of `world.sum`, `min`, `max`, `broadcast` and `gather_all` (every rank gets the same result). * **Varying:** may differ between ranks. The sources are: * `world.rank()`; * the results of `world.shift` and `world.exchange` (each rank receives something different); * `clock()`; * files and processes: `read_file`, `file_exists`, `getenv`, `run`; * the `os` functions, except `os.name()` and `os.arch()`; * C functions declared with `extern fn`. Anything computed from a varying value is varying, and so is a variable assigned under a varying condition (`if world.rank() == 1: root = 1` makes `root` varying). Then two rules: 1. **A communication call can’t be controlled by a varying value** ([E0510](/reference/errors/#e0510)): not by an `if`, `while`, `for` or `match`, not by `and`/`or` or a conditional expression, and not by an early `return`, `break` or `continue` before it. 2. **Arguments that steer communication must be uniform** ([E0511](/reference/errors/#e0511)): the root of `world.broadcast`, the distance of `world.shift`, and any parameter that decides whether a function communicates. The *values* sent can vary freely: `world.sum(local)` with a different `local` on each rank is the point of the call. ## Communication under a rank-dependent branch [Section titled “Communication under a rank-dependent branch”](#communication-under-a-rank-dependent-branch) branch.br ```brine fn main(): if world.rank() == 0: let total = world.sum(1) print(total) ``` ```text error[E0510]: some ranks might not reach this communication --> branch.br:3:21 | 3 | let total = world.sum(1) | ^^^^^^^^^^^^ calls `world.sum` 2 | if world.rank() == 0: | ----------------- this may differ between ranks | = note: every rank must make the same `world` calls in the same order, otherwise the program could hang = help: move the call out of the rank-dependent branch or loop; compute rank-specific values first, then communicate on every rank = run `brine explain E0510` for more about this error error: could not compile due to 1 error ``` Rank 0 would wait in `world.sum` for ranks that never call it. Compute the rank-specific part first, then communicate on every rank, and branch on the rank only for what doesn’t communicate: ```brine fn main(): let mine = 1 if world.rank() == 0 else 0 let total = world.sum(mine) if world.rank() == 0: print(total) ``` brine run --ranks 3 ```text 1 ``` ## Loops whose length varies [Section titled “Loops whose length varies”](#loops-whose-length-varies) A loop whose condition or range depends on the rank runs a different number of times on each rank: loop.br ```brine fn main(): let rank = world.rank() var steps = 0 while steps < rank: world.barrier() steps += 1 ``` ```text error[E0510]: some ranks might not reach this communication --> loop.br:5:9 | 5 | world.barrier() | ^^^^^^^^^^^^^^^ calls `world.barrier` 4 | while steps < rank: | ------------ this may differ between ranks | = note: every rank must make the same `world` calls in the same order, otherwise the program could hang = help: move the call out of the rank-dependent branch or loop; compute rank-specific values first, then communicate on every rank = run `brine explain E0510` for more about this error error: could not compile due to 1 error ``` The same goes for `for i in 0..n` with a varying `n`, and for a `continue` or `break` under a varying condition before the call. ## Short-circuits and other sources [Section titled “Short-circuits and other sources”](#short-circuits-and-other-sources) `and`, `or` and conditional expressions decide whether their right side runs, so they count as branches. `clock()` differs between processes: timer.br ```brine fn main(): let t = clock() if t > 1.0 and world.sum(1) > 0: print("ok") ``` ```text error[E0510]: some ranks might not reach this communication --> timer.br:3:20 | 3 | if t > 1.0 and world.sum(1) > 0: | ^^^^^^^^^^^^ calls `world.sum` | ------- this may differ between ranks | = note: every rank must make the same `world` calls in the same order, otherwise the program could hang = help: move the call out of the rank-dependent branch or loop; compute rank-specific values first, then communicate on every rank = run `brine explain E0510` for more about this error error: could not compile due to 1 error ``` ## Branching on received values [Section titled “Branching on received values”](#branching-on-received-values) `shift` and `exchange` give each rank a different value, so their results are varying too: received.br ```brine fn main(): let got = world.shift(world.rank(), 1) if got == 0: world.barrier() ``` ```text error[E0510]: some ranks might not reach this communication --> received.br:4:9 | 4 | world.barrier() | ^^^^^^^^^^^^^^^ calls `world.barrier` 3 | if got == 0: | -------- this may differ between ranks | = note: every rank must make the same `world` calls in the same order, otherwise the program could hang = help: move the call out of the rank-dependent branch or loop; compute rank-specific values first, then communicate on every rank = run `brine explain E0510` for more about this error error: could not compile due to 1 error ``` To decide together, turn the local fact into a uniform one with a reduction. Every rank then gets the same answer and takes the same branch: ```brine fn main(): let got = world.shift(world.rank(), 1) # ask every rank, and get the same answer everywhere let someone_got_zero = world.max(1 if got == 0 else 0) == 1 if someone_got_zero: world.barrier() if world.rank() == 0: print(f"rank 0 got {got}, someone got 0: {someone_got_zero}") ``` brine run --ranks 3 ```text rank 0 got 2, someone got 0: true ``` ## What’s allowed [Section titled “What’s allowed”](#whats-allowed) Results of `world.sum`, `min`, `max`, `broadcast` and `gather_all` are uniform, so conditions built from them are fine. That covers the usual iterative patterns: loop until the largest error on any rank is small, let rank 0 choose a value and broadcast it, take turns as the root: allowed.br ```brine fn main(): let rank = world.rank() let size = world.size() # every rank keeps going until the largest error is small var x = float(rank + 1) * 100.0 var rounds = 0 while world.max(abs(x - 1.0)) > 0.001: x = (x + 1.0) / 2.0 rounds += 1 # a value chosen on rank 0, then the same everywhere let seed = world.broadcast(0, rank * 7 + 3) if seed > 0: world.barrier() # each rank takes a turn as the root: `r` is uniform var total = 0 for r in 0..size: total += world.broadcast(r, rank * 10) if rank == 0: print(f"{size} ranks: {rounds} rounds, seed {seed}, total {total}") ``` brine run allowed.br --ranks 4 ```text 4 ranks: 19 rounds, seed 3, total 60 ``` Branching on the rank is fine when no communication depends on it: printing on rank 0, doing rank-specific work before a collective, or returning early *after* the last call. ## Functions that communicate [Section titled “Functions that communicate”](#functions-that-communicate) The check is modular. For every function it records a summary: whether the function communicates, and which of its parameters must be uniform because the function branches on them around a communication. Call sites are checked against the summary, so the rules hold across calls, modules and recursion. Calling a communicating function under a varying condition, here an early `return` before it, is E0510, and the error shows where the function communicates: early.br ```brine fn report(x: int): let total = world.sum(x) print(total) fn main(): if world.rank() == 0: return report(1) ``` ```text error[E0510]: some ranks might not reach this communication --> early.br:8:5 | 8 | report(1) | ^^^^^^^^^ calls `report`, which communicates with other ranks 6 | if world.rank() == 0: | ----------------- this may differ between ranks 2 | let total = world.sum(x) | ------------ communicates here | = note: every rank must make the same `world` calls in the same order, otherwise the program could hang = help: move the call out of the rank-dependent branch or loop; compute rank-specific values first, then communicate on every rank = run `brine explain E0510` for more about this error error: could not compile due to 1 error ``` A parameter that controls communication inside the function must get a uniform argument: rounds.br ```brine fn rounds(n: int) -> int: var total = 0 for i in 0..n: total += world.sum(i) return total fn main(): print(rounds(world.rank())) ``` ```text error[E0511]: argument `n` of `rounds` must be the same on every rank --> rounds.br:8:18 | 8 | print(rounds(world.rank())) | ^^^^^^^^^^^^ might differ between ranks | = help: compute it from values that are the same everywhere, e.g. `world.size()`, constants, or the result of `world.broadcast` = run `brine explain E0511` for more about this error error: could not compile due to 1 error ``` Make the argument uniform first, for example with `world.broadcast`: ```brine fn rounds(n: int) -> int: var total = 0 for i in 0..n: total += world.sum(i) return total fn main(): let n = world.broadcast(0, world.rank() + 3) let r = rounds(n) if world.rank() == 0: print(f"{world.size()} ranks, {n} rounds: {r}") ``` brine run --ranks 3 ```text 3 ranks, 3 rounds: 9 ``` A parameter that is only *sent* may vary. Here `v` differs on every rank and `levels` is uniform, and the recursion is fine: ```brine fn tree_sum(v: int, levels: int) -> int: if levels == 0: return v return tree_sum(world.sum(v), levels - 1) fn main(): let r = tree_sum(world.rank(), 3) if world.rank() == 0: print(r) ``` brine run --ranks 4 ```text 96 ``` ## Roots and distances [Section titled “Roots and distances”](#roots-and-distances) `world.broadcast(root, v)` needs every rank to agree on the root, and `world.shift(v, by)` on the distance: root.br ```brine fn main(): let root = world.rank() let v = world.broadcast(root, 42) print(v) ``` ```text error[E0511]: the root rank of `world.broadcast` must be the same on every rank --> root.br:3:29 | 3 | let v = world.broadcast(root, 42) | ^^^^ might differ between ranks 2 | let root = world.rank() | ------------ because this depends on which rank is running | = help: compute it from values that are the same everywhere, e.g. `world.size()`, constants, or the result of `world.broadcast` = run `brine explain E0511` for more about this error error: could not compile due to 1 error ``` ## No send or recv [Section titled “No send or recv”](#no-send-or-recv) recv.br ```brine fn main(): let x = world.recv(0) ``` ```text error[E0512]: `world.recv` doesn't exist: unmatched sends and receives can deadlock --> recv.br:2:19 | 2 | let x = world.recv(0) | ^^^^ not available | = note: run `brine explain E0512` for how to express point-to-point patterns = help: every rank takes part in each communication: `world.shift(v, 1)` sends `v` to the next rank and returns the value from the previous one; `world.exchange(xs)` sends `xs[j]` to rank `j` = run `brine explain E0512` for more about this error error: could not compile due to 1 error ``` “Rank 0 sends a message to rank 1” is an `exchange` in which every other slot is empty. Filling the outbox under a rank-dependent `if` is fine, since the `if` doesn’t communicate: ```brine fn main(): var outbox = [""] * world.size() if world.rank() == 0 and world.size() > 1: outbox[1] = "hello" let inbox = world.exchange(outbox) if world.rank() == 1: print(f"rank 1 got {inbox[0]}") ``` brine run --ranks 4 ```text rank 1 got hello ``` A ring (each rank to its neighbour) is `world.shift(v, 1)`; a halo exchange in both directions is `shift(v, 1)` and `shift(v, -1)`. ## Communication inside par [Section titled “Communication inside par”](#communication-inside-par) `world` calls can’t appear in a `par` body ([E0503](/reference/errors/#e0503)): iterations run in no fixed order, so the ranks’ calls couldn’t line up. inpar.br ```brine fn main(): let total = par sum(world.sum(i) for i in 0..10) print(total) ``` ```text error[E0503]: `world` operations can't be used inside a `par` body --> inpar.br:2:25 | 2 | let total = par sum(world.sum(i) for i in 0..10) | ^^^^^^^^^^^^ not allowed here | = help: communicate before or after the parallel section = run `brine explain E0503` for more about this error error: could not compile due to 1 error ``` Reduce locally with `par`, then communicate once: `world.sum(par sum(f(i) for i in lo..hi))`. See [combining world with par](/parallelism/world/#combining-world-with-par). ## What the check doesn’t cover [Section titled “What the check doesn’t cover”](#what-the-check-doesnt-cover) The compiler proves that ranks can’t disagree about which calls to make. It can’t make a rank reach the next call: * **A rank that crashes** never sends its next message. The others stop with an error naming it instead of waiting forever (`panic (rank 0): rank 1 exited before sending the expected message`); see [when a rank fails](/parallelism/world/#when-a-rank-fails). * **A rank that loops forever** before a collective keeps the others waiting, as a slow rank would. * **Message sizes** can differ: `gather_all` of a string or an array works with a different length on each rank. `exchange` needs exactly `world.size()` elements on every rank, and panics otherwise. ## Rules [Section titled “Rules”](#rules) * Every `world` call except `rank()` and `size()` is collective. * No communication under a condition, loop, short-circuit or early exit that depends on a varying value ([E0510](/reference/errors/#e0510)). * `broadcast` roots, `shift` distances and parameters that steer communication must be uniform ([E0511](/reference/errors/#e0511)). * No `send` or `recv` ([E0512](/reference/errors/#e0512)); use `shift` and `exchange`. * No communication in `par` ([E0503](/reference/errors/#e0503)). * Make a local fact uniform with `world.sum`, `min`, `max`, `broadcast` or `gather_all`, then branch on it.