gregyoung

Untitled

Nov 14th, 2026
562
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.94 KB | None | 0 0
  1. Compile-Time Bounded Process Managers: A Join-Calculus DSL for Event-Sourced Messaging Finite State Machines
  2. Abstract
  3. Distributed workflow coordination typically forces a trade-off between ergonomic imperative orchestration (where Turing-complete host languages make termination, worst-case lifetime, and state-space bounds undecidable) and formal process calculi (which offer strong verification guarantees at the cost of developer ergonomics and tight coupling to raw state tables). This dissertation presents a non-Turing-complete embedded Domain-Specific Language (DSL) for authoring event-sourced process managers. By restricting pauses exclusively to finite, timeout-bounded join patterns (Join(...).WithTimeout(...)) and lowering linear workflow definitions into pure, single-stream Mealy finite state machines (evolve / decide), the compiler statically guarantees outcome totality, race confluence under at-least-once delivery, and an exact upper bound \(T_{\max }\) on process lifetime—reducing versioning, retention, and SLA governance to compile-time proofs and living documentation.
  4. Chapter 1: Introduction & Problem Statement
  5. 1.1 The Distributed Coordination Dilemma
  6. Why single-stream atomicity is mandatory for horizontal partitionability in event-sourced systems (and why multi-stream transactions / 2PC / cross-stream write queries destroy scale).
  7. The role of the Process Manager (Saga) as an asynchronous, single-stream coordinator mediating across independent aggregate boundaries.
  8. 1.2 The Authoring vs. Verification Gap
  9. Imperative Durable Execution (Temporal, Durable Functions): Easy to read, impossible to bound statically; prone to zombie instances, non-deterministic replay hazards, and multi-year version migration debt.
  10. Hand-Coded Messaging FSMs: Formally clean and replayable, but suffers from combinatorial state explosion on concurrent joins and poor developer adoption.
  11. 1.3 Thesis Statement & Core Contributions
  12. Contribution 1 (Language Design): An embedded, non-Turing-complete linear DSL based on algebraic join patterns with mandatory timeout bounds.
  13. Contribution 2 (Compilation & Verification): A lowering pipeline from linear DSL ASTs to Join-Calculus IR and deterministic evolve/decide Mealy FSMs, with O(V + E) compile-time worst-case execution time (WCET) verification.
  14. Contribution 3 (Operational Lifecycle Reduction): Demonstrating how compile-time bounded lifetime \(T_{\max }\) eliminates mid-flight state migration, bounds stream retention, and enables automated behavioral specification generation.
  15. Chapter 2: Background & Related Work
  16. 2.1 Event Sourcing as Pure Functional State Transitions
  17. Formalizing streams, deterministic GUIDs (UUIDv5), upcasting pipelines (flatMap), and left-fold state hydration (events.reduce(evolve, initialState)).
  18. Separation of domain invariants (decide : (State, Command) -> Result<Event[], Error>) from workflow coordination (react : (State, Event) -> (State', Command[])).
  19. 2.2 Process Calculi & Concurrency Models
  20. From Milner’s π-calculus to Fournet & Gonthier’s Join-Calculus: why localized join patterns map 1-to-1 onto isolated correlation_id streams.
  21. Comparison with Erlang/OTP process isolation, mailbox semantics, and explicit exit signals (Killed).
  22. 2.3 Timed Automata & Workflow Verification
  23. Alur & Dill Timed Automata, Uppaal model checking, Petri Nets, and Session Types.
  24. Why restricting the DSL grammar to a finite weighted DAG avoids general model-checking state explosion while preserving exact WCET guarantees.
  25. Chapter 3: The Restricted Process DSL & Type-State Grammar
  26. 3.1 Design Philosophy: Intentional Expressiveness Restriction
  27. Eliminating unbounded loops, arbitrary recursion, and unguarded waits from the syntax.
  28. Type-state builder enforcement (UnboundedJoin<T> \(\xrightarrow{\text{WithTimeout}}\) BoundedJoin<T>) making unbounded waits syntactically unrepresentable.
  29. 3.2 Abstract Syntax & Typing Rules
  30. Primitives: Publish(Command), Join(Pattern).WithTimeout(Duration), Branch(Predicate, Step, Step), Retry(ConstantN, Step), and terminal outcomes (Complete(Outcome), Fail(Reason)).
  31. Join Algebra: Conjunctive (A & B), disjunctive (A | B), and mixed boolean event patterns over a single correlation_id.
  32. Outcome Totality Typing: Proving that every well-typed ProcessDefinition<TResult> terminates at a typed outcome leaf on every control-flow path.
  33. 3.3 First-Class Control Operations
  34. Self-scheduled timer messages published onto correlation_id as the sole external time dependency.
  35. Universal Kill / Abort transitions and explicit Killed stream events for deterministic teardown and compensation.
  36. Chapter 4: Compilation Pipeline — Linear AST to Event-Sourced FSM
  37. 4.1 Lowering to Join-Calculus Intermediate Representation (IR)
  38. Translating linear continuations into localized internal channel tokens and atomic join rules.
  39. Expanding Join(A & B) into partial-order sub-states (WaitingAB, GotA, GotB) sharing a single bounded timer horizon.
  40. 4.2 Determinization into Pure Mealy State Machines
  41. Compiling the Join-Calculus IR into a frozen transition table: (StateId, EventType) -> (NextStateId, CallbackDelegate[]).
  42. Ensuring pure, zero-thread runtime execution via event-stream folding.
  43. 4.3 Static Verification & WCET Calculation
  44. Constructing the weighted DAG where Join edges carry timeout weights and instant transitions carry weight 0.
  45. Algorithm 1: O(V + E) topological longest-path calculation accounting for shared partial-join countdowns and bounded loop unrolling.
  46. Compile-time SLA budget enforcement (MaxProcessDuration <= DeclaredBudget).
  47. Chapter 5: Formal Properties & Proofs
  48. 5.1 Theorem 1 — Outcome Totality & Termination
  49. Proof: By structural induction on well-typed DSL terms, every execution path reaches a terminal state (Completed, TimedOut, or Killed) in finitely many steps.
  50. 5.2 Theorem 2 — Bounded-Time Liveness under Bounded Timer Skew
  51. Proof: Given a durable timer service with maximum delivery delay Δ, any instance with compiled DAG weight \(T_{\text{DAG}}\) reaches a terminal state within \(T_{\text{DAG}} + k \cdot \Delta\), where k is the maximum join depth.
  52. 5.3 Theorem 3 — Race Confluence & Idempotency under At-Least-Once Delivery
  53. Proof: Linear token consumption in join patterns combined with deterministic UUIDv5 event IDs ensures duplicate deliveries, late-arriving domain replies, and post-termination timer wake-ups act as pure identity transitions ([]).
  54. 5.4 Theorem 4 — Soundness of Compilation (Bisimulation)
  55. Proof: Weak bisimulation between the big-step operational semantics of the Join-Calculus IR and the step-by-step execution of the compiled Mealy FSM.
  56. Chapter 6: Operational & Governance Consequences
  57. 6.1 Versioning Without State Migration
  58. Pinning process_version at instance creation and deriving exact drain horizons (deploy_time + T_max) from the compile-time bound.
  59. Handling the 1% urgent cutover case via Kill + compensation + versioned re-trigger.
  60. 6.2 Living Documentation & Automated Governance
  61. Extracting Given (Events) / When (Command/Event) / Then (Emitted/Error) specifications and weighted state graphs directly from the verified AST.
  62. Enforcing business sign-off gates (CODEOWNERS + CI spec drift checks) only when behavioral specifications change.
  63. 6.3 Property-Based Fuzzing & Mutation Verification
  64. Generating adversarial, out-of-order, and duplicate event streams against the lowered transition metadata to validate runtime invariants (0 <= active_time <= T_max).
  65. Chapter 7: Implementation & Empirical Evaluation
  66. 7.1 Reference Implementation Architecture
  67. Embedded C# type-state builder, Roslyn source generator / compile-time analyzer, and event-store runtime adapter.
  68. 7.2 Experimental Setup & Benchmarks
  69. Compile-Time Analysis Overhead: Measuring AST lowering, cycle detection, and O(V + E) WCET calculation times across workflows scaling from 5 to 500 states and multi-way joins (2-way to 8-way).
  70. Runtime Throughput & Memory Footprint: Comparing event-sourced FSM replay latency and memory overhead against traditional imperative durable workflow engines.
  71. Fault Injection & Chaos Testing: Verifying 100% termination within \(T_{\max} + k\Delta\) under simulated message drops, duplicate deliveries, node crashes, and concurrent Kill commands.
  72. Chapter 8: Limitations, Extensions & Future Work
  73. 8.1 Expressiveness Trade-Offs
  74. Identifying workflows that genuinely require unbounded lifespans (e.g., perpetual entity monitors) and how to decompose them into chained, bounded process instances.
  75. 8.2 Multi-Process Supervision (Erlang/OTP Links & Monitors)
  76. Extending single-stream isolation with asynchronous Monitor / ProcessExited subscriptions across parent/child correlation streams without recursive teardown locks.
  77. 8.3 Formal Mechanization
  78. Porting the operational semantics and bisimulation proofs into Lean 4 or Coq/Rocq for machine-checked verification.
  79. Appendices
  80. Appendix A: Complete Formal Grammar & Typing Judgments of the Process DSL
  81. Appendix B: Reference Implementation of the evolve / decide Runtime & UUIDv5 Idempotency Layer
  82. Appendix C: Auto-Generated Specification & Mermaid State Graph Output Samples
Advertisement
Add Comment
Please, Sign In to add comment