boundsort

Boundsort

Boundsort is a Go framework for budget-governed ordering: you can run an ordering algorithm under a deterministic, explicit Budget, stop early when the budget is exhausted, and still return a safe partial result plus an auditable Receipt.

It's designed for systems where "sorting" isn't free:

• comparisons can be expensive (risk engines, compliance checks, remote calls, cache misses)
• strict SLAs require graceful degradation instead of timeouts
• operators/auditors need to know what work was done and why it stopped

Key guarantees

• Guarantee A (framework-level): Safe partial result
  Every engine returns a permutation of the input (no loss/duplication), even on budget exhaustion or errors.

• Guarantee B (engine-specific): Monotonic improvement in inversion count
  For the adjacent-swap engine with a strict weak ordering comparator: each swap reduces the inversion count by at least 1, so the inversion count is non-increasing over time and strictly decreases with each swap. This provides a minimal "progress" property: more budget never makes the result worse in the sense of inversions.

• Guarantee C (engine-specific): Sorted suffix after a completed pass
  For the adjacent-swap engine, after completing a full pass over indices 0..m-1: the maximum element (under the comparator) among indices 0..m is placed at position m (equivalently, at least one element is established in its final position). With the last-swap index optimization, all positions strictly beyond lastSwap form a fixed suffix that never changes again. Important caveat: if the budget is exhausted mid-pass, this guarantee does not apply; you only have the monotonic inversion property (Guarantee B) and whatever domain-specific evidence your receipt provides.

• Guarantee D (engine-specific): Stability under strict swap condition
  For the adjacent-swap engine: if the comparator is based on a key and the engine swaps only when key[i] > key[i+1] (not >=), then the engine is stable with respect to equal keys, preserving the relative order of items with equal keys.

Docs

• Concept note (why Boundsort exists, guarantees, and framing): docs/boundsort_idea.md
• Codebase architecture diagram (Mermaid): docs/boundsort_architecture.md
• Application hypothesis: docs/boundsort_application.md
• What we think on Non-guarantees: docs/boundsort_non_guarantees.md

The application hypothesis is exercised on Kubernetes scheduling, Ethereum client (Go), and MEV-Boost (builder/relay).

Concepts

• Comparator / Before function: your domain-specific ordering logic, returning both an ordering decision and a cost to charge.
• Budget: tracks remaining spend and decides when to stop.
• Receipt: records what happened (cost + events) and can be tamper-evident (hash chain + optional signature).

In this repo the canonical comparator shape used by engines is:

• BeforeFunc[T]: func(a, b T) (aBeforeB bool, cost float64, err error)

And budgets implement:

• Budget: Charge(cost float64) bool and Remaining() float64

Quick start

package main

import (
	"fmt"

	"github.com/bogwi/boundsort"
)

func main() {
	items := []int{5, 1, 4, 2, 3}

	// A simple comparator: ascending order.
	// Here we model "each comparison costs 1".
	before := func(a, b int) (bool, float64, error) {
		return a < b, 1.0, nil
	}

	b := boundsort.NewSimpleBudget(6) // allow ~6 comparisons total

	cfg := boundsort.EngineConfig{
		Kind: boundsort.EngineAdjacentSwap,
		AdjacentSwap: boundsort.AdjacentSwapConfig{
			ReceiptMode: boundsort.ReceiptModeFull,
			SwapCost:    0, // optional: charge extra cost per swap
		},
	}

	out, receipt, completed, err := boundsort.Boundsort(cfg, items, before, b)
	if err != nil {
		panic(err)
	}

	fmt.Println("completed:", completed)
	fmt.Println("out:", out)
	fmt.Println("stop:", receipt.Stop)
	fmt.Println("totalCost:", receipt.TotalCost)
	fmt.Println("tamperEvident:", receipt.Sealed && receipt.Verify())
}

Advanced boundsort example (policy + preflight + caching + signed receipts)

Full runnable program: examples/advanced_contracts/main.go

Run it:

go run ./examples/advanced_contracts

This example demonstrates:

• Policy-driven budgets (Policy → BudgetParameters → Budget)
• Preflight to avoid known-unaffordable expensive comparisons (CompareUpperBound + WithPreflightBefore)
• Comparator memoization (NewCachedComparator)
• Engine selection via the uniform dispatcher (EngineAdaptive)
• Receipt integrity + signing (Verify(), Sign(), VerifySignature())

Guarantees demo (AdjacentSwap engine)

Full runnable program: examples/guarantees_abcd/main.go

Run it:

go run ./examples/guarantees_abcd

This example demonstrates:

• A (safe partial result): every tick returns a permutation even when budget is exhausted
• B (monotonic progress): inversion count is non-increasing across ticks as more budget is spent
• C (pass-level guarantees): once a full pass completes, the worst element is at the end and a suffix becomes fixed (via last-swap optimization)
• D (stability): equal-priority items preserve FIFO order (stable adjacent swaps)
• Receipt integrity: uses ReceiptModeFull and checks receipt.Sealed && receipt.Verify()

Engines

Boundsort provides multiple engines. You can call them directly, or use the uniform dispatcher Boundsort(cfg, ...).

Adjacent-swap (anytime baseline)

• Function: AdjacentSwapBounded(...) (full receipts, backward-compatible)
• Function: AdjacentSwapBoundedWithReceiptMode(...) (choose receipt detail level)
• Strengths: strong anytime behavior; engine-specific guarantees B/C/D
• Notes:
  • Optional swapCost can model swaps as real spend.
  • Budget exhaustion mid-pass is expected: the algorithm stops and returns the current permutation.

Bounded quicksort

• Function: BoundedQuickSort(...)
• Strengths: average-case (O(n \log n)) work under sufficient budget
• Notes: preserves Guarantee A; does not provide adjacent-swap-specific guarantees

Bounded heapsort (full sort or top-k)

• Function: BoundedHeapSort(items, k, ...)
• Strengths: worst-case (O(n \log n)); good for top‑k use cases
• Important output detail (top‑k):
  • if k > 0, the engine extracts the k largest elements and places them at the end of the slice (positions [n-k:n]), in sorted order under your comparator.

Adaptive selection

• Kind: EngineAdaptive (via Boundsort dispatcher)
• What it does: deterministically chooses an engine from input size + remaining budget + objective hints in EngineConfig.Adaptive.
• What it does NOT do: it does not "probe" by executing unaccounted comparisons.

Receipts, tamper-evidence, and signing

Receipt modes (adjacent-swap family)

• ReceiptModeFull: full event log + incremental hash chain; engine calls Seal() before returning
  • Tamper-evident: receipt.Verify() detects mutation of events; when sealed it also binds the terminal Stop.
• ReceiptModeSummary: totals + stop only (no per-event log)
  • Not tamper-evident (intentional trade-off).
• ReceiptModeNone: minimal receipt with Stop only
  • No audit trail (intentional trade-off).

Hash-chain semantics

Receipts maintain a stateful, incremental event hash chain:

• while unsealed, Verify() checks event integrity only (the Stop field is not bound)
• after Seal(), the final digest binds the event-chain head and Stop

Most engines in this repo call Seal() before returning; if you build receipts manually, call Seal() once the terminal fields (like Stop) are final.

Signatures

Receipt supports optional signing and verification:

• receipt.Sign(privateKey) supports RSA / ECDSA / Ed25519
• receipt.VerifySignature(publicKey) verifies both the receipt hash chain and the signature

For meaningful signatures, sign sealed receipts (i.e., call Seal() first, or use engines/modes that seal).

Budgeting details (edge cases)

To keep the cost model robust under adversarial or buggy comparators, engines and budgets treat costs conservatively:

• negative cost → treated as 0
• NaN → treated as 0
• +Inf → treated as immediate budget exhaustion (the operation is not charged)

Preflight (skip unaffordable expensive comparisons)

Some workloads have a cheap way to compute a conservative upper bound on comparison cost (e.g., "this will require a remote call"). Boundsort provides additive wrappers that can avoid executing a known-unaffordable expensive comparison:

• WithPreflightBefore(b, before, upperBound)
• WithPreflightComparator(b, cmp, upperBound)

If the upper bound is known and b.Remaining() < bound, the wrapper returns cost = +Inf and err = nil. Existing engines interpret +Inf cost as immediate budget exhaustion and stop without charging.

Helpers exist to scale bounds by policy:

• ScaleCompareUpperBound(base, multiplier)
• PolicyCompareUpperBound(p, ctx, base)

Policy (deterministic budget selection)

Boundsort includes a simple, deterministic Policy abstraction for mapping system context → BudgetParameters, plus a reproducible input log for auditability:

• Policy.DetermineBudget(ctx) BudgetParameters
• Policy.LogInput(ctx) string

This is intentionally kept separate from engine APIs: you compose policy → budget at the call site.

Where Boundsort fits

Boundsort is a pattern for systems that must choose "best effort ordering under a cost cap," for example:

• scheduling / dispatch: ordering candidate nodes/jobs under per-cycle budgets (think Kubernetes-style scheduling loops)
• crypto / sequencing / block building: ordering transactions/bids under strict time and verification budgets (e.g., Ethereum clients, builder/relay selection)
• financial services: ranking portfolios/orders under expensive risk/compliance comparisons with regulatory auditability

Testing and benchmarks for development

Run the test suite:

go test

There is also a benchmark harness under benchmarks/ (see benchmarks/README.md). This is used for tracking regressions when extending boundsort with new features or making general improvements an optimizations.

boundsort has a great optimization potential especially if implemented in languages like C/C++, Rust, Zig, or Odin.

go run ./benchmarks/cmd/run

Project status and scope

This repo is a research-to-production implementation of:

• budget-governed ordering engines
• deterministic budgeting primitives
• receipts with verifiable, incremental integrity (and optional signatures)

Non-goals (by design):

• claiming a single "best" ordering algorithm for all domains
• silently spending work beyond budget
• weakening receipt integrity without making it explicit (use ReceiptModeSummary/None only when you accept reduced auditability)