AFTD Auto-Formalizing Theoretical Domains

Cslib.FLP.Algorithm

structureimported Lean

The specification of a distributed algorithm for solving the consensus problem. Note that each field below can depend on a process's identifier (recall that each Message contains its destination's identifier), so the algorithm is not required to be uniform across processes.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Set Sum Multiset in
variable {P M S : Type*} [DecidableEq P] [DecidableEq M] in
structure Cslib.FLP.Algorithm (P M S : Type*)
Defined in
CSLib, `Cslib.FLP.Algorithm`
Lean proof
By Ching-Tsun Chou, from github.com/leanprover/cslib at 3951377e5a3f (Copyright (c) 2026 Ching-Tsun Chou. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.
Verified
08 Oct 2026
Axioms
none listed
Built on 2
Used by 1

Lean source view module on GitHub

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Set Sum Multiset in
variable {P M S : Type*} [DecidableEq P] [DecidableEq M] in
/-- The specification of a distributed algorithm for solving the consensus problem. Note that each field below can depend on a process's identifier (recall that each `Message` contains its destination's identifier), so the algorithm is not required to be uniform across processes. -/
structure Cslib.FLP.Algorithm (P M S : Type*) where
  /-- A map specifying the initial state of each process. -/
  init : P → S
  /-- A map specifying how a process changes its internal state upon receiving a message. -/
  next : Message P M → ProcState S → S
  /-- A map specifying what messages a process sends out upon receiving a message. -/
  send : Message P M → ProcState S → Multiset (Message P M)
  /-- A map specifying the boolean decision a process makes upon receiving a message,
      where `none` means that no decision is made. -/
  out : Message P M → ProcState S → Option Bool
See it in the graphDiscuss this resultChallenge it