Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Compile-Time Bounded Process Managers: A Join-Calculus DSL for Event-Sourced Messaging Finite State Machines
- Abstract
- 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.
- Chapter 1: Introduction & Problem Statement
- 1.1 The Distributed Coordination Dilemma
- 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).
- The role of the Process Manager (Saga) as an asynchronous, single-stream coordinator mediating across independent aggregate boundaries.
- 1.2 The Authoring vs. Verification Gap
- 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.
- Hand-Coded Messaging FSMs: Formally clean and replayable, but suffers from combinatorial state explosion on concurrent joins and poor developer adoption.
- 1.3 Thesis Statement & Core Contributions
- Contribution 1 (Language Design): An embedded, non-Turing-complete linear DSL based on algebraic join patterns with mandatory timeout bounds.
- 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.
- 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.
- Chapter 2: Background & Related Work
- 2.1 Event Sourcing as Pure Functional State Transitions
- Formalizing streams, deterministic GUIDs (UUIDv5), upcasting pipelines (flatMap), and left-fold state hydration (events.reduce(evolve, initialState)).
- Separation of domain invariants (decide : (State, Command) -> Result<Event[], Error>) from workflow coordination (react : (State, Event) -> (State', Command[])).
- 2.2 Process Calculi & Concurrency Models
- From Milner’s π-calculus to Fournet & Gonthier’s Join-Calculus: why localized join patterns map 1-to-1 onto isolated correlation_id streams.
- Comparison with Erlang/OTP process isolation, mailbox semantics, and explicit exit signals (Killed).
- 2.3 Timed Automata & Workflow Verification
- Alur & Dill Timed Automata, Uppaal model checking, Petri Nets, and Session Types.
- Why restricting the DSL grammar to a finite weighted DAG avoids general model-checking state explosion while preserving exact WCET guarantees.
- Chapter 3: The Restricted Process DSL & Type-State Grammar
- 3.1 Design Philosophy: Intentional Expressiveness Restriction
- Eliminating unbounded loops, arbitrary recursion, and unguarded waits from the syntax.
- Type-state builder enforcement (UnboundedJoin<T> \(\xrightarrow{\text{WithTimeout}}\) BoundedJoin<T>) making unbounded waits syntactically unrepresentable.
- 3.2 Abstract Syntax & Typing Rules
- Primitives: Publish(Command), Join(Pattern).WithTimeout(Duration), Branch(Predicate, Step, Step), Retry(ConstantN, Step), and terminal outcomes (Complete(Outcome), Fail(Reason)).
- Join Algebra: Conjunctive (A & B), disjunctive (A | B), and mixed boolean event patterns over a single correlation_id.
- Outcome Totality Typing: Proving that every well-typed ProcessDefinition<TResult> terminates at a typed outcome leaf on every control-flow path.
- 3.3 First-Class Control Operations
- Self-scheduled timer messages published onto correlation_id as the sole external time dependency.
- Universal Kill / Abort transitions and explicit Killed stream events for deterministic teardown and compensation.
- Chapter 4: Compilation Pipeline — Linear AST to Event-Sourced FSM
- 4.1 Lowering to Join-Calculus Intermediate Representation (IR)
- Translating linear continuations into localized internal channel tokens and atomic join rules.
- Expanding Join(A & B) into partial-order sub-states (WaitingAB, GotA, GotB) sharing a single bounded timer horizon.
- 4.2 Determinization into Pure Mealy State Machines
- Compiling the Join-Calculus IR into a frozen transition table: (StateId, EventType) -> (NextStateId, CallbackDelegate[]).
- Ensuring pure, zero-thread runtime execution via event-stream folding.
- 4.3 Static Verification & WCET Calculation
- Constructing the weighted DAG where Join edges carry timeout weights and instant transitions carry weight 0.
- Algorithm 1: O(V + E) topological longest-path calculation accounting for shared partial-join countdowns and bounded loop unrolling.
- Compile-time SLA budget enforcement (MaxProcessDuration <= DeclaredBudget).
- Chapter 5: Formal Properties & Proofs
- 5.1 Theorem 1 — Outcome Totality & Termination
- Proof: By structural induction on well-typed DSL terms, every execution path reaches a terminal state (Completed, TimedOut, or Killed) in finitely many steps.
- 5.2 Theorem 2 — Bounded-Time Liveness under Bounded Timer Skew
- 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.
- 5.3 Theorem 3 — Race Confluence & Idempotency under At-Least-Once Delivery
- 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 ([]).
- 5.4 Theorem 4 — Soundness of Compilation (Bisimulation)
- 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.
- Chapter 6: Operational & Governance Consequences
- 6.1 Versioning Without State Migration
- Pinning process_version at instance creation and deriving exact drain horizons (deploy_time + T_max) from the compile-time bound.
- Handling the 1% urgent cutover case via Kill + compensation + versioned re-trigger.
- 6.2 Living Documentation & Automated Governance
- Extracting Given (Events) / When (Command/Event) / Then (Emitted/Error) specifications and weighted state graphs directly from the verified AST.
- Enforcing business sign-off gates (CODEOWNERS + CI spec drift checks) only when behavioral specifications change.
- 6.3 Property-Based Fuzzing & Mutation Verification
- Generating adversarial, out-of-order, and duplicate event streams against the lowered transition metadata to validate runtime invariants (0 <= active_time <= T_max).
- Chapter 7: Implementation & Empirical Evaluation
- 7.1 Reference Implementation Architecture
- Embedded C# type-state builder, Roslyn source generator / compile-time analyzer, and event-store runtime adapter.
- 7.2 Experimental Setup & Benchmarks
- 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).
- Runtime Throughput & Memory Footprint: Comparing event-sourced FSM replay latency and memory overhead against traditional imperative durable workflow engines.
- Fault Injection & Chaos Testing: Verifying 100% termination within \(T_{\max} + k\Delta\) under simulated message drops, duplicate deliveries, node crashes, and concurrent Kill commands.
- Chapter 8: Limitations, Extensions & Future Work
- 8.1 Expressiveness Trade-Offs
- Identifying workflows that genuinely require unbounded lifespans (e.g., perpetual entity monitors) and how to decompose them into chained, bounded process instances.
- 8.2 Multi-Process Supervision (Erlang/OTP Links & Monitors)
- Extending single-stream isolation with asynchronous Monitor / ProcessExited subscriptions across parent/child correlation streams without recursive teardown locks.
- 8.3 Formal Mechanization
- Porting the operational semantics and bisimulation proofs into Lean 4 or Coq/Rocq for machine-checked verification.
- Appendices
- Appendix A: Complete Formal Grammar & Typing Judgments of the Process DSL
- Appendix B: Reference Implementation of the evolve / decide Runtime & UUIDv5 Idempotency Layer
- Appendix C: Auto-Generated Specification & Mermaid State Graph Output Samples
Advertisement
Add Comment
Please, Sign In to add comment