Definition 3 — σ-paths and σ-approximate q-counting
DefinitionPulseSyncLowerBound_Pulse_Supplement_ApproxCountingWork in the synchronous crash-fault model of the base mission: processes with permanent identities, finite nonempty local state sets, a deterministic time-independent transition, every initial configuration allowed, and -resilience counted as the number of processes that ever crash in the infinite execution. A process is non-faulty if it never crashes. Let the outputs be .
For , a set is a -path if
that is, an arc of consecutive residues of the -cycle read in the increasing direction.
Let be the set of outputs of the non-faulty processes in round . A protocol is an -resilient -approximate -counting protocol that stabilises in rounds if every execution with at most crashes satisfies, for all :
- (A1) -agreement: is contained in some -path of ;
- (A2) progress: for every non-faulty process .
For this is exact synchronous counting; for it is a self-stabilising analogue of cycle agreement. It is the task solved by the upper bound of Section 7 (Theorem 20).
Formalization Note The source states the definition for ; this range is a parameter assumption of the theorems that use the predicate, not a clause of the predicate, so it cannot make the predicate vacuous. Outputs are Fin q; the output of process in round is the protocol's output map applied to its state e.config t i. The model (Protocol, Execution, Nonfaulty, AtMostCrashes) is the published base definition PulseSyncLowerBound_Pulse_Model, imported unchanged.
import Definitions.Def_PulseSyncLowerBound_Pulse_Model
noncomputable section
namespace PulseSyncLowerBound.Pulse.Supplement
open PulseSyncLowerBound.Pulse
variable {n : ℕ}
/-- §2.2.1, PDF 6 / printed 4: `I ⊆ Z_q` is a σ-path if
`I = {c + k mod q : 0 ≤ k ≤ σ}` for some `c ∈ Z_q`, a clockwise arc of σ + 1 residues. -/
def SigmaPath (q σ : ℕ) (c : Fin q) : Set (Fin q) :=
{x | ∃ k : ℕ, k ≤ σ ∧ (x : ℕ) = ((c : ℕ) + k) % q}
/-- Φ(t): the outputs of the non-faulty (never-crashing) processes in round t. -/
def NonfaultyOutputs {q : ℕ} {P : Protocol n (Fin q)} (e : Execution P) (t : ℕ) :
Set (Fin q) :=
{x | ∃ i, Nonfaulty e i ∧ ∃ s, e.config t i = some s ∧ P.output i s = x}
/-- Definition 3, PDF 6 / printed 4, for one execution: for all t ≥ T,
(A1) Φ(t) is contained in some σ-path of Z_q, and
(A2) every non-faulty process advances its output by one modulo q.
The source's side condition q > max{2σ, 1} is a parameter range, not part of the predicate. -/
def ApproxCountingExecution {q : ℕ} {P : Protocol n (Fin q)} (e : Execution P)
(σ T : ℕ) : Prop :=
∀ t, T ≤ t →
(∃ c : Fin q, NonfaultyOutputs e t ⊆ SigmaPath q σ c) ∧
(∀ i, Nonfaulty e i → ∀ s s', e.config t i = some s → e.config (t + 1) i = some s' →
(P.output i s' : ℕ) = ((P.output i s : ℕ) + 1) % q)
/-- Definition 3: `P` is an f-resilient σ-approximate q-counting protocol that stabilises
in T rounds: every execution with at most f crashes satisfies A1 and A2 from round T on. -/
def ApproxCountingResilient {q : ℕ} (P : Protocol n (Fin q)) (f σ T : ℕ) : Prop :=
∀ e : Execution P, AtMostCrashes e f → ApproxCountingExecution e σ T
end PulseSyncLowerBound.Pulse.Supplement