What does Zero-Courier Dispatch conclude, in numbers, about “Resource Locks: a Global Order against Deadlock, Leases for Orphaned Locks and Fencing Tokens”?

Answer: Chapter 4 shows a global locking order driving simulated deadlock rates of 0.1795 and 0.8655 to zero, and recovers orphaned locks with leases and fencing tokens.

Scope of the numbers: Its parameters are illustrative and all calculations are generated by its programs. It names no server, account, key or deployment command, and it is general business analysis, not personalised advice.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.1795, 0.8655

locks/jobpolicydeadlockedrate
2free order7180.1795
2global order00.0000
3free order3,4620.8655
3global order00.0000
Show the full program
# Chapter 4. p41: deadlock rate with and without a global lock order.
# Model: 6 agents share 5 named resources. Each agent needs 2 or 3 of
# them for one job, starts at a random tick 0 to 12, takes them one at
# a time, works 1 to 4 ticks, then releases all. "free order": locks
# are taken in the order the job lists them; "global order": always in
# the fixed order of RES (Havender
# 1968). Wait-for graph cycles = deadlock (Coffman, Elphick and
# Shoshani 1971). 4,000 seeded trials per policy and per job size.
import random

RES = ["bib", "index", "ledger", "shelf", "spec"]


def trial(rng, ordered, k):
    agents = []
    for _ in range(6):
        need = rng.sample(RES, k)
        if ordered:
            need.sort(key=RES.index)
        agents.append({"need": need, "held": [], "work": rng.randint(1, 4),
                       "done": False, "start": rng.randint(0, 12)})
    owner = {}
    for tick in range(200):
        if all(a["done"] for a in agents):
            return False
        for i in rng.sample(range(6), 6):
            a = agents[i]
            if a["done"] or tick < a["start"]:
                continue
            if len(a["held"]) < len(a["need"]):
                r = a["need"][len(a["held"])]
                if r not in owner:
                    owner[r] = i
                    a["held"].append(r)
            else:
                a["work"] -= 1
                if a["work"] == 0:
                    for r in a["held"]:
                        del owner[r]
                    a["done"] = True
        if has_cycle(agents, owner):
            return True
    return False


def has_cycle(agents, owner):
    wait = {}
    for i, a in enumerate(agents):
        if not a["done"] and len(a["held"]) < len(a["need"]):
            r = a["need"][len(a["held"])]
            if r in owner and owner[r] != i:
                wait[i] = owner[r]
    for s in wait:
        seen, x = set(), s
        while x in wait and x not in seen:
            seen.add(x)
            x = wait[x]
        if x == s:
            return True
    return False


if __name__ == "__main__":
    print("locks/job  policy         deadlocked  rate")
    for k in (2, 3):
        for name, ordered in (("free order", False),
                              ("global order", True)):
            rng = random.Random(40741)
            n = 0
            for _ in range(4000):
                n += trial(rng, ordered, k)
            print("{:>9}  {:<14} {:>10,}  {:.4f}".format(
                k, name, n, n / 4000))

Single source and citation

Fan, Y. (2026). Commander Intent Compilation, Automated DAG Task Decomposition and Zero-Courier Multi-Agent Dispatch (Version 1.0.0), Chapter 4: Resource Locks: a Global Order against Deadlock, Leases for Orphaned Locks and Fencing Tokens. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-407 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026407,
  author    = {Fan, Yafu},
  title     = {Commander Intent Compilation, Automated DAG Task Decomposition and Zero-Courier Multi-Agent Dispatch},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book