13-EFT.WP.Methods.SimStack v1.0 | Chapter 3: Discrete Weaving & Thread Network (Threads Layer)

Home ／ Docs-Technical WhitePaper ／ 13-EFT.WP.Methods.SimStack v1.0

Chapter 3: Discrete Weaving & Thread Network (Threads Layer)

I. Scope & Objectives

• Define the objects, semantics, and metrics of the discrete weaving layer (Threads), establish P61-* concurrency postulates and S62-* minimal equations, and align execution, observation, and publishing with the continuous kernel and the coupler layer.
• Deliver a reusable execution graph G=(V,E), contracts for messaging and retry, backpressure and scheduling strategies, an SLO metric family TS.*, and a manifest convention aligned to T_arr and the tau_mono ↔ ts mapping.

II. Terms & Symbols

1. Execution graph and weights
   • G=(V,E): a directed acyclic or feedback-containing execution graph. V are Thread/Actor nodes, E are dependencies or message channels.
   • w(v): nominal service time or work for node v. c(e): transmission/queueing cost on edge e.
   • crit(G): critical-path length. W(G)=Σ_v w(v): total work. D(G)=crit(G): span.
2. Arrival and service rates
   • lambda(v): arrival rate. mu(v): service rate. rho(v)=lambda(v)/mu(v): utilization.
   • Coefficients of variation: c_a^2(v) (SCV of inter-arrival), c_s^2(v) (SCV of service time).
3. Causality and time bases
   • hb(a,b): event a happens-before b.
   • Time bases: internal tau_mono, published ts, related by a linear mapping.
4. Backpressure and watermarks
   B(v): queue length at node v. bp: backpressure control policy. Thresholds B_hi > B_lo.
5. Metric family
   TS.latency.*, TS.throughput.*, TS.queue.*, TS.hb.violations, TS.sli.success_rate, etc.

III. Postulates & Minimal Equations (P61- / S62-)

• P61-1 (Causality conservation)
  If hb(a,b) holds, any observable output o_b must not influence o_a. Retries or reordering must preserve this invariant via idempotency or compensation.
• P61-2 (Idempotency and retry)
  All externally visible operations must realize exactly-once effects. If at-least-once delivery is used, processors require idempotency keys or deduplication.
• P61-3 (Monotone backpressure)
  When B(v) ≥ B_hi, upstream throttling tightens monotonically until B(v) ≤ B_lo.
• P61-4 (Time-base coherence)
  All timing comparisons and SLO evaluation occur on tau_mono. Publications convert to ts with recorded mapping parameters.
• S62-10 (Lower bound on makespan)
  T_make(G,P) ≥ max( W(G)/P , D(G) ), where P is the parallelism.
• S62-11 (Single-node waiting time, G/G/1 Kingman approximation)
  For node v:
  W_q(v) ≈ ( rho(v) / ( 1 - rho(v) ) ) * ( ( c_a^2(v) + c_s^2(v) ) / 2 ) * ( 1 / mu(v) ).
  Sojourn time: L_v = W_q(v) + ( 1 / mu(v) ).
• S62-12 (Path delay aggregation)
  For path Pi: L(Pi) = Σ_{v∈Pi} L_v + Σ_{e∈Pi} c(e).
  End-to-end tail: P99 ≈ quantile( Σ delays , 0.99 ).
• S62-13 (Stability criterion)
  Necessary stability condition: rho(v) < 1 for all bottleneck nodes v. If violated, scale out or throttle.
• S62-14 (Backpressure differential invariant)
  In a continuous approximation, dB(v)/dt = lambda(v) - mu(v) when B(v) > 0. Backpressure aims to keep B(v) bounded and to minimize queueing delay.

IV. Data & Manifest Conventions

• Graph and time-base fields
  graph.id, V, E, w(v), c(e), crit(G), W(G). Mapping tau_mono ↔ ts with alpha/beta and uncertainty.
• Queueing and throughput fields
  lambda(v), mu(v), rho(v), c_a^2(v), c_s^2(v), B(v), W_q(v), L_v.
• Backpressure and throttling fields
  B_hi/B_lo, bp.policy (e.g., token_bucket/aimd/cubic), bp.action (drop/delay/reject).
• SLO and observability fields
  TS.latency.p50/p90/p99, TS.throughput.rps, TS.queue.backlog, TS.hb.violations, TS.sli.success_rate.
• Publication consistency
  All timestamps are published as ts and durably recorded with tau_mono and the mapping parameters for audit and replay.

V. Algorithms & Implementation Bindings (I60-*)

1. Interface prototypes (anchored in this volume)
   • I60-6 build_exec_graph(spec:any) -> GraphRef
   • I60-7 plan_schedule(graph:GraphRef, policy:dict, resources:dict) -> SchedPlanRef
   • I60-8 apply_backpressure(graph:GraphRef, strategy:dict) -> bp.Report
   • I60-9 compensate_retry(event:any, idempotency_key:str) -> bool
   • I60-10 eval_slo(trace:any, targets:dict) -> TS.Report
2. Policy highlights
   • Scheduling: priority = criticality * aging / cost. Critical-path first can be combined with work stealing.
   • Backpressure: thresholds B_hi/B_lo with rate control r_out ← min( r_budget , r_target * f(B) ).
   • Retry: deduplicate via idempotency_key. If side effects are non-idempotent, require compensating transactions and record a compensation manifest.
   • Observability: I60-5 emit_metrics(...) periodically produces TS.*, combined with eval_slo for gating.

VI. Metrology Flows & Run Diagrams (Mx-6*)

1. Mx-63 (coupling-run, Threads-side extension)
   Steps:
   • Assemble G and the resource pool.
   • Use plan_schedule to produce a plan.
   • Run advance_dt or an event-driven loop.
   • Periodically emit_metrics and apply_backpressure.
   • Route failures to compensate_retry.
2. Mx-65 (queue-audit)
   Verify rho(v) < 1, B(v) bounded, and error of W_q(v) estimates. If off-target, trigger load shedding and scaling recommendations.
3. Mx-66 (slo-check)
   Gate on TS.latency.p99, TS.sli.success_rate, and TS.hb.violations, and issue a regression report.

VII. Verification & Test Matrix

1. Minimum required
   • Single-node G/G/1: given lambda/mu/c_a^2/c_s^2, verify deviations of W_q and L_v.
   • Two-stage pipeline: verify T_make and P99 aggregation, and identify the critical path.
   • Retry idempotency: craft duplicate deliveries and validate idempotency_key deduplication and compensation.
2. Boundary and extreme cases
   • High-frequency jitter: stability of backpressure when c_a^2 ≫ 1.
   • Bottleneck drift: dynamic reordering and SLO maintenance under time-varying mu(v).
3. Regression and thresholds
   Fix a baseline graph and load. Compare ΔTS.latency.p99, ΔTS.queue.backlog, ΔTS.hb.violations.

VIII. Cross-References & Dependencies

• With the Continuous Kernel (Chapter 2): when exchanging wave-packets or flux across the coupling boundary, maintain unit and measure consistency, and measure on the same tau_mono before publishing as ts.
• With Coupled Advancement (Chapter 4): share scheduling and backpressure signals for time advancement and synchronization. Failures and retries follow the same idempotency/compensation contract.
• With Time Bases (Chapter 5): calibrate end-to-end latency and arrival time on tau_mono, and in parallel report both T_arr formulations when they are part of calibration.

IX. Risks, Limitations & Open Questions

1. Risks
   • Non-idempotent side effects can defeat compensation and violate the hb invariant.
   • Relying on rho < 1 while ignoring large c_a^2/c_s^2 underestimates W_q and P99.
2. Limitations
   Methods and conventions are specified, but no constraint is placed on concrete middleware or threading libraries.
3. Open questions
   • Optimal adaptive backpressure under strong feedback and bursts.
   • Cross-layer co-scheduling and formal stability proofs under strong coupling with the continuous kernel.

X. Deliverables & Versioning

1. Deliverables
   • Reference implementations and contract tests for I60-6..I60-10.
   • Benchmark graph suite and load generators covering stable and overload regimes.
   • Regression report template with TS.* metrics and thresholds.
2. Versioning
   Freeze symbols and manifest fields from v1.0. Add strategies via feature flags with backward-compatible switches, and provide migration guidance.

XI. New Terms & Symbols (to memorize)

• Graph & measures: G=(V,E), w(v), c(e), W(G), D(G), crit(G), T_make(G,P).
• Queueing parameters: lambda(v), mu(v), rho(v), c_a^2(v), c_s^2(v), W_q(v), L_v.
• Causality & time bases: hb(a,b), tau_mono, ts.
• Backpressure & thresholds: B(v), B_hi/B_lo, bp.policy.
• Metric family: TS.latency.*, TS.throughput.*, TS.queue.*, TS.hb.violations, TS.sli.success_rate.