dwrr-elixir

Deficit weighted round robin (DWRR) scheduler for Elixir. The core is a set of pure functions over immutable values. Dwrr.Server is an optional, caller-owned wrapper that keeps one scheduler in one process.

Intended release: 0.1.0, unpublished according to local release records. The Hex package and application are dwrr.

Other languages

These libraries share fixed-quantum scheduling semantics, with language-specific APIs and additional features. See each library's README for its supported contract.

Shared specification

dwrr-spec defines the shared fixed-quantum contract, conformance corpus and driver protocol / conformance tools. They let implementations with different APIs check the same service order, errors and numeric limits rather than rely on similar-looking algorithms. This is a development/conformance resource, not a runtime dependency. Pinned revisions and vendored snapshots make checks reproducible; they do not automatically track current spec source or establish all-sequences conformance.

This implementation targets the fixed-quantum core through immutable values; Dwrr.Server and Elixir-domain validation are local API choices, not shared requirements. Fixtures and the main CI retain historical revision 8a0e3cf9ae860ba207213590c00feeb822bdd8f2, rather than automatically following upstream. Separate current-source checks must identify their revision and results; see TESTING.md. The standalone example CI does not change that historical conformance-tool pin.

The need

When several queues share one resource, such as a link, a packet path or a job pool, each queue should get a share in proportion to its quantum. DWRR does this with small integer bookkeeping, and it measures work by the cost callers declare, not by elapsed time. This library gives you that scheduler as plain values you can store, branch and test.

At a glance

Quick start

The intended dependency for release 0.1.0 is:

{:dwrr, "~> 0.1.0"}

Local release records mark the package as not yet on Hex; this is an intended install, not a verified public fetch. Until release, use a local checkout, for example:

{:dwrr, path: "../dwrr-elixir"}

Adjust the path for your application. The core has no dependencies to fetch; this repository's own tests additionally require StreamData.

Examples

Each example is an independent history. Each one binds result to what the operations actually returned.

Byte sharing

Queue 0 has quantum 2 and queue 1 has quantum 3. Queue 0 serves packet_a, then blocks on packet_b. Queue 1 cannot yet afford packet_x (cost 4), so it keeps its 3 credit. Queue 0 then serves packet_b, and queue 1 serves packet_x and packet_y.

s = Dwrr.new(2)
{:ok, s} = Dwrr.set_quantum(s, 0, 2)
{:ok, s} = Dwrr.set_quantum(s, 1, 3)

{:ok, s} =
  Dwrr.enqueue(s, 0, [
    %Dwrr.Item{value: :packet_a, cost: 2},
    %Dwrr.Item{value: :packet_b, cost: 2}
  ])

{:ok, s} =
  Dwrr.enqueue(s, 1, [
    %Dwrr.Item{value: :packet_x, cost: 4},
    %Dwrr.Item{value: :packet_y, cost: 1}
  ])

{:ok, served, _s} = Dwrr.take(s, 10)
result = Enum.map(served, &{&1.queue, &1.value, &1.cost})

Expected result:

[{0, :packet_a, 2}, {0, :packet_b, 2}, {1, :packet_x, 4}, {1, :packet_y, 1}]

Fair file-transfer simulation

The standalone example uses Basic/Team/Business byte quanta of 1024/2048/4096 and repeated take(s, 1) calls. Its twelve pretend records, selection order and cumulative totals match the Python example; the Go README uses a different backlogged dataset. Final totals are Basic=5120, Team=6656 and Business=12288 bytes: finite offered demand, not a promised 1:2:4 split. There is no real transfer I/O, timing, bandwidth pacing or preemption. Use bounded chunks as items in a real sender for finer interleaving.

Caller-owned worker orchestration

The Server only decides the order of jobs. It does not run them. The caller receives the jobs and runs them itself. This example stops the server it started, even if an operation fails.

{:ok, server} = Dwrr.Server.start_link(1)

result =
  try do
    {:ok, _scheduler} =
      Dwrr.Server.enqueue(server, 0, [
        %Dwrr.Item{value: :job_a, cost: 1},
        %Dwrr.Item{value: :job_b, cost: 1}
      ])

    {:ok, served, _scheduler} = Dwrr.Server.take(server, 2)
    Enum.map(served, & &1.value)
  after
    GenServer.stop(server)
  end

Pure withdrawal

remove_head/2 withdraws the first item without spending credit. drain_queue/2 then withdraws the rest in FIFO order.

s = Dwrr.new(1)

{:ok, s} =
  Dwrr.enqueue(s, 0, [
    %Dwrr.Item{value: :cancelled, cost: 5},
    %Dwrr.Item{value: :kept, cost: 1}
  ])

{:ok, cancelled, s} = Dwrr.remove_head(s, 0)
{:ok, kept, _s} = Dwrr.drain_queue(s, 0)
result = {[cancelled.value], Enum.map(kept, & &1.value)}

Atomic error

Enqueue checks every item before it adds any. The valid item is not kept when the zero-cost item fails. A later take on the original scheduler returns nothing.

s = Dwrr.new(1)

result =
  Dwrr.enqueue(s, 0, [
    %Dwrr.Item{value: :valid, cost: 1},
    %Dwrr.Item{value: :invalid, cost: 0}
  ])

{:ok, [], _s} = Dwrr.take(s, 10)

Public API

Dwrr.new(count) creates count empty queues (zero is valid), each with quantum 1 and credit 0. %Dwrr.Item{value: value, cost: cost} is the enqueue record; take/2 returns %Dwrr.Scheduled{queue: index, value: value, cost: cost} records.

Operation Successful result
enqueue(s, index, items) {:ok, scheduler}
set_quantum(s, index, quantum) {:ok, scheduler}
add_queue(s) {index, scheduler}
remove_queue(s) scheduler (unchanged when no queues exist)
remove_head(s, index) {:ok, item_or_nil, scheduler}
drain_queue(s, index) {:ok, items, scheduler} in FIFO order
take(s, n) {:ok, scheduled_items, scheduler}

Dwrr.Server exposes the same operations against a caller-started server and returns the same results, including immutable scheduler snapshots.

Behavior worth knowing

There are no built-in queue capacity limits, admission control or resource-exhaustion recovery guarantees. Large counts, batches and retained immutable snapshots still consume memory. Pure histories need no shared lock; callers coordinate which snapshot to retain. The Server serializes its own history, not caller-owned branches. Neither interface waits for producers when empty; take(s, 0) or an empty scheduler returns {:ok, [], s}. Selection still costs CPU and memory.

How we know it's correct

Historical local verification ran on Elixir 1.20.4 / OTP 29. The minimum Elixir 1.18 / OTP 27 and the full CI matrix (Elixir 1.18.4 / OTP 27.3 and Elixir 1.20.4 / OTP 29.1.2) are configured but not verified by this README. See TESTING.md.

Check it yourself

Run these from the repository root:

MIX_ENV=test mix deps.get --check-locked
mix format --check-formatted
mix compile --warnings-as-errors
MIX_ENV=test mix test --warnings-as-errors --no-color

The conformance replay needs a sibling dwrr-spec checkout at the pinned commit. TESTING.md lists the exact commands.

How it compares

Current implementation and shared-source status

The pure core, driver, optional Server, public docs and package metadata are implemented in this checkout; intended 0.1.0 remains unpublished. The owner-run kit instructions below are historical preparation instructions, not a statement that these files are still stubs or authorization to rerun a loop.

Vendored SPEC/PROTOCOL/corpus and their hash guards deliberately retain the historical 8a0e3cf9ae860ba207213590c00feeb822bdd8f2 snapshot. Sibling working-tree corrections clarify that negative costs/quanta are language-local and wire integers have no signed-32-bit protocol cap, add language mappings, and repair the Go adapter/checker; no scheduler semantics or corpus bytes changed. They do not silently repin these historical fixtures or CI. Historical verification records report that Elixir was also checked against the expanded sibling checker: 41/41, plus all 1,839 cases / 44,728 steps. Python now has a working mutable, internally locked implementation; its public API and language-domain validation differ from Elixir's immutable core. Go's unreleased callbacks/result API and generation-exhaustion restriction are not shared fixed-core requirements. The sibling protocol now permits native count-representation exhaustion as a resource failure, not malformed input: Go detects counts above native int before allocation, emits stderr and exits 1 with no response or later processing; prior responses stand. This adds no shared count cap or Elixir rejection requirement, and guarantees no controlled recovery from actual allocation limits/OOM. Frozen vendored documents and identities above remain unchanged.

Apply and run the stage-2 kit (owner only)

Already applied over audited stage-1 HEAD 7205252 on spec-loop/stage2-preparation. Review SPEC Part 2, tasks.json and verification first. T01–T21 remain unchanged; the old T22 whole-tree gate was replaced by seven new tasks T22–T27 and T29. T28 is deliberately absent: CI is complete and protected, not a coding task. Properties, the naive oracle and CI identity check are protected preparation assets.

Exact judge expectations require installed Elixir 1.20.4 / OTP29. Library minimum 1.18/27 is not proven by that runtime. CI minimum/current jobs are not executed by preparation. Requires Python3, bash, git, jq, timeout (or gtimeout), Pi with owner-authorized access/spending, and approved StreamData test dependency. Do not start with unrelated edits. Only the owner may commit this baseline and then authorize model calls, loop commits and discards of attempt-owned edits.

cd ~/Development/dwrr-elixir
test "$(git -C ../dwrr-spec rev-parse HEAD)" = 8a0e3cf9ae860ba207213590c00feeb822bdd8f2
test "$(git branch --show-current)" = spec-loop/stage2-preparation
MIX_ENV=test mix deps.get --check-locked
git status --short
# Review all tracked AND new files; do not include .loop/ or private source.
git add .
git diff --cached --stat
git commit -m "Add verified stage-2 spec-loop kit"
test -z "$(git status --porcelain)"
mkdir -p .loop
set -o pipefail
JUDGE_TIMEOUT=300 bash scripts/loop.sh 2>&1 | tee .loop/stage2-console.log

Unchanged pinned defaults (inspection only; no kit overrides):

cheap: pi --provider anthropic --model claude-haiku-5-5 --thinking high --print --no-session
strong: pi --provider openai-codex --model gpt-6.1-sol --thinking high --print --no-session
strongest: pi --provider openai-codex --model gpt-6.1-sol --thinking max --print --no-session

Inspect any owner environment overrides yourself. Defaults: 60 iterations, four attempts per task, 1200s coder timeout, 300s per judge command. The loop commits on this branch. .loop/loop.log records exact coder commands, .loop/coder.*.log holds output and .loop/notes.* discarded notes; STOP names an exhausted task. Keep ignored logs for review; do not blindly rerun STOP. Preparation invokes no coder, stages/commits nothing, publishes nothing and changes no installed skill.

Colophon