Documentation

PolyFun.Interaction.Concurrent.Observation

Observation equivalence for concurrent processes #

This file packages the notion of "what a party can tell apart" from concrete executions of a concurrent process.

The process semantics keeps the exact dependent type of each local observation, which is ideal when reasoning inside one fixed execution. But comparison across different executions, processes, or refinement layers needs a uniform carrier. The solution adopted here is to pack each local observation together with its type and then compare executions through these packed observations.

The resulting API provides:

This is the comparison layer later used by refinement and equivalence results.

PackedObs is a locally observed value packaged together with its observation type.

This is the simplest uniform carrier for local observations whose precise type may vary from one visited node to the next.

  • α : Type w

    The type of the locally observed value.

  • val : self.α

    The locally observed value itself.

Instances For
    def Interaction.Concurrent.Observation.Step.Observed.toList {Party : Type u} [DecidableEq Party] {me : Party} {spec : TypeTree} {semantics : PFunctor.FreeM.Displayed.Decoration (StepContext Party) spec} {tr : PFunctor.FreeM.Path spec} :
    Step.Observed me semantics tr → List PackedObs

    Forget the dependent indices of an observed sequential path and keep only the concrete packed sequence of observations that was exposed locally.

    This is the uniform, comparison-friendly summary of what one party learned from one complete sequential step path.

    Equations
    Instances For
      def Interaction.Concurrent.Observation.Step.obsList {Party : Type u} [DecidableEq Party] (me : Party) {P : Type v} (step : Step Party P) (tr : PFunctor.FreeM.Path step.tree) :

      obsList me step tr is the packed sequence of local observations available to the fixed party me while the sequential process step step executes along the path tr.

      This forgets the exact dependent observation types but keeps their concrete values in order, which makes it the basic comparison object for one process step.

      Equations
      Instances For
        def Interaction.Concurrent.Observation.Process.Trace.observations {Party : Type u} [DecidableEq Party] {P : Type v} {process : Process P Party} (me : Party) {p : ProcessOver.Proc process} :
        process.Trace p → List (List PackedObs)

        The per-step packed local observations exposed along a finite complete process trace.

        Each list element corresponds to one executed process step and stores the local observations that me obtained during that step.

        Equations
        Instances For
          def Interaction.Concurrent.Observation.Process.Prefix.observations {Party : Type u} [DecidableEq Party] {P : Type v} {process : Process P Party} (me : Party) {p : ProcessOver.Proc process} {n : ℕ} :
          process.Prefix p n → List (List PackedObs)

          The per-step packed local observations exposed along a finite process prefix.

          This is the prefix-level analogue of Trace.observations.

          Equations
          Instances For
            def Interaction.Concurrent.Observation.Process.Prefix.Rel {Party : Type u} {P₁ P₂ : Type v} {left : Process P₁ Party} {right : Process P₂ Party} (rel : left.StepRel right) {pL : ProcessOver.Proc left} {pR : ProcessOver.Proc right} {n : ℕ} :
            left.Prefix pL n → right.Prefix pR n → Prop

            Rel rel left right states that the two finite prefixes left and right match step-by-step according to the path relation rel.

            The length index forces the two prefixes to have the same number of executed steps.

            So Prefix.Rel is the generic finite-horizon comparison interface: the caller chooses what it means for one process step of left to match one process step of right, and Rel lifts that choice to whole finite prefixes.

            Equations
            Instances For
              theorem Interaction.Concurrent.Observation.Process.Prefix.rel_cast {Party : Type u} {P₁ P₂ : Type v} {left : Process P₁ Party} {right : Process P₂ Party} (rel : left.StepRel right) {pL pL' : ProcessOver.Proc left} {pR pR' : ProcessOver.Proc right} {n : ℕ} (hL : pL = pL') (hR : pR = pR') (leftPrefix : left.Prefix pL n) (rightPrefix : right.Prefix pR n) :
              Rel rel (hL ▸ leftPrefix) (hR ▸ rightPrefix) ↔ Rel rel leftPrefix rightPrefix

              Transporting both prefixes along equal start states does not change their matching relation.

              @[reducible, inline]
              abbrev Interaction.Concurrent.Observation.Process.StepRel {Party : Type u} {P₁ P₂ : Type v} (left : Process P₁ Party) (right : Process P₂ Party) :
              Type (max u_1 v)

              Concurrent.Process.StepRel left right is a cross-process relation on concrete process steps. Each step pairs its source process state with the complete path selected there.

              This is the basic matching interface used later by refinement, equivalence, and observation-preservation theorems. The permissive relation and conjunction are the lattice operations ⊤ and ⊓ on relations.

              Equations
              Instances For
                def Interaction.Concurrent.Observation.Process.StepRel.byController {Party : Type u} {P₁ P₂ : Type v} {left : Process P₁ Party} {right : Process P₂ Party} :
                StepRel left right

                Match two paths by equality of their current controlling parties.

                Equations
                • One or more equations did not get rendered due to their size.
                Instances For
                  def Interaction.Concurrent.Observation.Process.StepRel.byPath {Party : Type u} {P₁ P₂ : Type v} {left : Process P₁ Party} {right : Process P₂ Party} :
                  StepRel left right

                  Match two paths by equality of their full controller paths.

                  Equations
                  • One or more equations did not get rendered due to their size.
                  Instances For
                    def Interaction.Concurrent.Observation.Process.StepRel.byEvent {Party : Type u} {P₁ P₂ : Type v} {left : Process P₁ Party} {right : Process P₂ Party} {Event : Type w} (eventL : left.EventMap Event) (eventR : right.EventMap Event) :
                    StepRel left right

                    Match two paths by equality of stable external event labels.

                    Equations
                    Instances For
                      def Interaction.Concurrent.Observation.Process.StepRel.byTicket {Party : Type u} {P₁ P₂ : Type v} {left : Process P₁ Party} {right : Process P₂ Party} {Ticket : Type w} (ticketL : left.TicketMap Ticket) (ticketR : right.TicketMap Ticket) :
                      StepRel left right

                      Match two paths by equality of stable tickets.

                      Equations
                      Instances For
                        def Interaction.Concurrent.Observation.Process.StepRel.byObservation {Party : Type u} [DecidableEq Party] {P₁ P₂ : Type v} {left : Process P₁ Party} {right : Process P₂ Party} (me : Party) :
                        StepRel left right

                        Match two paths by equality of the packed local observations exposed to one fixed party.

                        This is the relation that identifies executions that are observationally indistinguishable to me at the step level.

                        Equations
                        • One or more equations did not get rendered due to their size.
                        Instances For
                          theorem Interaction.Concurrent.Observation.Process.Prefix.currentControllers_eq_of_relByController {Party : Type u} {P₁ P₂ : Type v} {left : Process P₁ Party} {right : Process P₂ Party} {pL : ProcessOver.Proc left} {pR : ProcessOver.Proc right} {n : ℕ} {leftPrefix : left.Prefix pL n} {rightPrefix : right.Prefix pR n} (hrel : Rel StepRel.byController leftPrefix rightPrefix) :
                          leftPrefix.currentControllers = rightPrefix.currentControllers

                          Matching by current controller equality preserves the extracted controller sequence of finite prefixes.

                          theorem Interaction.Concurrent.Observation.Process.Prefix.controllerPaths_eq_of_relByPath {Party : Type u} {P₁ P₂ : Type v} {left : Process P₁ Party} {right : Process P₂ Party} {pL : ProcessOver.Proc left} {pR : ProcessOver.Proc right} {n : ℕ} {leftPrefix : left.Prefix pL n} {rightPrefix : right.Prefix pR n} (hrel : Rel StepRel.byPath leftPrefix rightPrefix) :
                          leftPrefix.controllerPaths = rightPrefix.controllerPaths

                          Matching by controller-path equality preserves the extracted controller path sequence of finite prefixes.

                          theorem Interaction.Concurrent.Observation.Process.Prefix.events_eq_of_relByEvent {Party : Type u} {P₁ P₂ : Type v} {left : Process P₁ Party} {right : Process P₂ Party} {Event : Type w} (eventL : left.EventMap Event) (eventR : right.EventMap Event) {pL : ProcessOver.Proc left} {pR : ProcessOver.Proc right} {n : ℕ} {leftPrefix : left.Prefix pL n} {rightPrefix : right.Prefix pR n} (hrel : Rel (StepRel.byEvent eventL eventR) leftPrefix rightPrefix) :
                          Process.Prefix.events eventL leftPrefix = Process.Prefix.events eventR rightPrefix

                          Matching by stable event equality preserves the extracted event sequence of finite prefixes.

                          theorem Interaction.Concurrent.Observation.Process.Prefix.tickets_eq_of_relByTicket {Party : Type u} {P₁ P₂ : Type v} {left : Process P₁ Party} {right : Process P₂ Party} {Ticket : Type w} (ticketL : left.TicketMap Ticket) (ticketR : right.TicketMap Ticket) {pL : ProcessOver.Proc left} {pR : ProcessOver.Proc right} {n : ℕ} {leftPrefix : left.Prefix pL n} {rightPrefix : right.Prefix pR n} (hrel : Rel (StepRel.byTicket ticketL ticketR) leftPrefix rightPrefix) :
                          Process.Prefix.tickets ticketL leftPrefix = Process.Prefix.tickets ticketR rightPrefix

                          Matching by stable ticket equality preserves the extracted ticket sequence of finite prefixes.

                          theorem Interaction.Concurrent.Observation.Process.Prefix.observations_eq_of_relByObservation {Party : Type u} [DecidableEq Party] (me : Party) {P₁ P₂ : Type v} {left : Process P₁ Party} {right : Process P₂ Party} {pL : ProcessOver.Proc left} {pR : ProcessOver.Proc right} {n : ℕ} {leftPrefix : left.Prefix pL n} {rightPrefix : right.Prefix pR n} (hrel : Rel (StepRel.byObservation me) leftPrefix rightPrefix) :
                          observations me leftPrefix = observations me rightPrefix

                          Matching by local observation equality preserves the packed observation sequence of finite prefixes for the chosen party.

                          def Interaction.Concurrent.Observation.Process.Run.observationsUpTo {Party : Type u} [DecidableEq Party] {P : Type v} {process : Process P Party} (me : Party) (run : process.Run) :

                          The per-step packed local observations exposed along the first n steps of the run run.

                          This is the infinite-run analogue of Prefix.observations, truncated to the first n steps.

                          Equations
                          Instances For
                            def Interaction.Concurrent.Observation.Process.Run.RelUpTo {Party : Type u} {P₁ P₂ : Type v} {left : Process P₁ Party} {right : Process P₂ Party} (rel : StepRel left right) (leftRun : left.Run) (rightRun : right.Run) :
                            ℕ → Prop

                            RelUpTo rel left right n states that the first n executed steps of the runs left and right match step-by-step according to rel.

                            This is the finite-prefix comparison predicate for runs.

                            Equations
                            Instances For
                              def Interaction.Concurrent.Observation.Process.Run.Rel {Party : Type u} {P₁ P₂ : Type v} {left : Process P₁ Party} {right : Process P₂ Party} (rel : StepRel left right) (leftRun : left.Run) (rightRun : right.Run) :

                              Rel rel left right states that every finite prefix of the runs left and right matches according to rel.

                              So two runs are related when they remain indistinguishable at every finite horizon under the chosen step-matching criterion.

                              Equations
                              Instances For
                                theorem Interaction.Concurrent.Observation.Process.Run.relUpTo_of_pointwise {Party : Type u} {P₁ P₂ : Type v} {left : Process P₁ Party} {right : Process P₂ Party} (rel : StepRel left right) (leftRun : left.Run) (rightRun : right.Run) (hrel : ∀ (n : ℕ), rel ⟨leftRun.state n, ProcessOver.Run.path leftRun n⟩ ⟨rightRun.state n, ProcessOver.Run.path rightRun n⟩) (n : ℕ) :
                                RelUpTo rel leftRun rightRun n

                                Pointwise path matching implies prefix matching of the first n steps.

                                theorem Interaction.Concurrent.Observation.Process.Run.rel_of_pointwise {Party : Type u} {P₁ P₂ : Type v} {left : Process P₁ Party} {right : Process P₂ Party} (rel : StepRel left right) (leftRun : left.Run) (rightRun : right.Run) (hrel : ∀ (n : ℕ), rel ⟨leftRun.state n, ProcessOver.Run.path leftRun n⟩ ⟨rightRun.state n, ProcessOver.Run.path rightRun n⟩) :
                                Rel rel leftRun rightRun

                                Pointwise path matching implies full run matching.

                                theorem Interaction.Concurrent.Observation.Process.Run.currentControllersUpTo_eq_of_relUpTo_byController {Party : Type u} {P₁ P₂ : Type v} {left : Process P₁ Party} {right : Process P₂ Party} (leftRun : left.Run) (rightRun : right.Run) {n : ℕ} (hrel : RelUpTo StepRel.byController leftRun rightRun n) :

                                Matching by current controller equality preserves the extracted controller sequence of the first n run steps.

                                theorem Interaction.Concurrent.Observation.Process.Run.controllerPathsUpTo_eq_of_relUpTo_byPath {Party : Type u} {P₁ P₂ : Type v} {left : Process P₁ Party} {right : Process P₂ Party} (leftRun : left.Run) (rightRun : right.Run) {n : ℕ} (hrel : RelUpTo StepRel.byPath leftRun rightRun n) :

                                Matching by controller-path equality preserves the extracted controller-path sequence of the first n run steps.

                                theorem Interaction.Concurrent.Observation.Process.Run.eventsUpTo_eq_of_relUpTo_byEvent {Party : Type u} {P₁ P₂ : Type v} {left : Process P₁ Party} {right : Process P₂ Party} {Event : Type w} (eventL : left.EventMap Event) (eventR : right.EventMap Event) (leftRun : left.Run) (rightRun : right.Run) {n : ℕ} (hrel : RelUpTo (StepRel.byEvent eventL eventR) leftRun rightRun n) :
                                Process.Run.eventsUpTo eventL leftRun n = Process.Run.eventsUpTo eventR rightRun n

                                Matching by stable event equality preserves the extracted event sequence of the first n run steps.

                                theorem Interaction.Concurrent.Observation.Process.Run.ticketsUpTo_eq_of_relUpTo_byTicket {Party : Type u} {P₁ P₂ : Type v} {left : Process P₁ Party} {right : Process P₂ Party} {Ticket : Type w} (ticketL : left.TicketMap Ticket) (ticketR : right.TicketMap Ticket) (leftRun : left.Run) (rightRun : right.Run) {n : ℕ} (hrel : RelUpTo (StepRel.byTicket ticketL ticketR) leftRun rightRun n) :
                                Process.Run.ticketsUpTo ticketL leftRun n = Process.Run.ticketsUpTo ticketR rightRun n

                                Matching by stable ticket equality preserves the extracted ticket sequence of the first n run steps.

                                theorem Interaction.Concurrent.Observation.Process.Run.observationsUpTo_eq_of_relUpTo_byObservation {Party : Type u} [DecidableEq Party] (me : Party) {P₁ P₂ : Type v} {left : Process P₁ Party} {right : Process P₂ Party} (leftRun : left.Run) (rightRun : right.Run) {n : ℕ} (hrel : RelUpTo (StepRel.byObservation me) leftRun rightRun n) :
                                observationsUpTo me leftRun n = observationsUpTo me rightRun n

                                Matching by local observation equality preserves the packed observation sequence of the first n run steps for the chosen party.