Stochastic modelling: DTMC, CTMC and stochastic Petri Nets

1. From nondeterminism to quantitative modelling

This chapter adds weights to the transition systems of chapter 9. Deck 07, "Stochastic modelling: uncertainty, probability and frequencies", opens by recalling the two sources of uncertainty identified at the end of the previous lecture — openness (new users/services/devices keep arriving; heterogeneity; human behaviour not pre-coded) and unpredictability (failures become the norm; delays and losses; only statistical characterisation; effects only estimated) — and then delivers the diagnosis of the day:

"On the non-determinism modelling mechanism: captures variability of 'outcomes' · does not 'weight' them · does not distinguish what is normal and what exceptional, and neglects performance."

A transition system knows which outcomes are possible; it cannot answer the two questions that matter at scale:

• How probable is a given event? — not "is a bad path possible?" or "is a situation inevitable?", but the probability of the event;
• What is the approximate next time the event will happen? — not just ordering, but actual timing.

The deck's motivations for quantitative modelling are worth reading as a list of exam-project ideas: specifying that some (even unlikely) events may occur, such as a node failing, but this is an exception case; that among the nodes sending messages one is faster, hence it is more probable that a given message comes from it; a timing model for the events captured/produced by a sensor; a nature-inspired approach for solving some computational problem — "in physics, chemistry, cellular biology, ant-colonies (in nature every mechanism is noisy, hence probabilistic, and this is key)"; the probabilistic "performance" of a system ("99% of times it completes its job in 1 hour"); reactiveness/resiliency expressed as the average time needed to recover at least 90% from a fault; a plan guaranteeing achievement of a goal with 60% probability.

The method, per the deck: "Use 'labels' to represent probability, frequency, decisions" — derive enhanced models such as stochastic Petri Nets. The roadmap of the chapter is the evolution of the meta-meta-model:

• DTMC — using probabilities (discrete time);
• CTMC — using rates, i.e. negative-exponential probabilities (continuous time);
• the concept of simulation (Gillespie's algorithm);
• some stochastic model (stochastic Petri Nets);
• to come later: MDP and Q-learning (the bridge to chapter 13).

In the vocabulary of the modelling stack of chapter 9, section 8: the meta-meta-model evolves from RS to CTMC, and the meta-model evolves from Petri Nets to Stochastic Petri Nets. Everything built in chapter 9 — System, MSet, toSystem — survives the upgrade almost unchanged.

2. DTMC: transition systems with probabilities

A Discrete-Time Markov Chain is "an extension of RS": the same couple ⟨S, →⟩, but the relation now carries a probability:

It is a couple ⟨S, →⟩ where → ⊆ S × [0, 1] × S — that is, a directed graph where edges are labelled with probabilities; write S -p→ S′ when ⟨S, p, S′⟩ ∈ →.

Sanity condition 1: ∀S ∈ S, either S is a deadlock (S ↛), or the outgoing arcs have total probability 1.

Sanity condition 2: there is at most one arc from S to S′.

The two sanity conditions say: from every non-deadlock state, the outgoing probabilities are a genuine distribution (they sum to 1), and the graph is simple (no duplicate edges). The deck immediately relaxes the first condition with likelihood factors (LF):

• same couple, but → ⊆ S × ℝ⁺ × S, and the label is any positive real — "informal meaning: double that factor, the likelihood of the event doubles";
• the actual probability is obtained by normalising each factor with respect to the sum of the outgoing LFs;
• outgoing arcs with LF 10, 10, 30 are equivalent to probabilities 0.2, 0.2, 0.6;
• "in this way it is easier to compose specifications".

Finally, a pure DTMC is a finite set S and a transition probability function T : S × S ↦ [0, 1] — "namely, a square matrix of non-negative reals; probability 0 means there can't be any transition". The matrix view is the one PRISM uses in chapter 11.

3. The probabilistic abstraction and fair sampling

Two questions accompany every probabilistic model: where do the numbers come from, and how do we draw from them when we animate or simulate?

Where do probabilities come from? "Typically, probabilities are obtained by information on the past, as the ratio between how many times a transition occurred, over the times it could have occurred." This makes probability "a (powerful) abstraction tool to deal with uncertainty": the label hides the unknown detail behind a frequency. And because it is a refinement of non-determinism, "it tells us how frequently a certain 'event' is expected to happen in the future".

How do we draw results fairly? The standard technique is inverse transform sampling: build the cumulative distribution function (CDF) of the distribution — for a positive-real-valued random variable X, FX(x) = Pr(X ≤ x), with FX : ℝ⁺₀ ↦ [0, 1], f(0) = 0, f(∞) = 1 — then compute FX⁻¹(n) where n is a uniform random number in [0, 1]. For a finite set of weighted outcomes, the CDF is the cumulative list of weights, and the draw is the first outcome whose cumulative weight exceeds the random number — exactly the algorithm the next section implements.

4. Interpreting DTMCs: the Stochastics toolkit

The deck gives the essential algorithm for interpreting a DTMC — yielding a path and its overall probability:

1. start with current state s equal to the initial state s0, and current probability p = 1;
2. compute the next steps along with their probabilities: [(p1, s1), ..., (pn, sn)];
3. draw a random number n in [0, 1];
4. compute i = min{j : Σ_{k=1..j} pₖ ≥ n};
5. select the next state s = sᵢ with probability p = pᵢ;
6. go back to step 3.

The sample trace printed in the deck alternates between states s1, s2, s3 with probabilities like 0.6, 0.2 and 1.0 — a run of exactly this interpreter. The toolkit that implements it is Stochastics, a small object with three operations: cumulative (turn weighted choices into the cumulative list), draw (select one outcome fairly), and statistics (repeat the draw many times and tally):

object Stochastics:

  given Random = new Random()

  // (p1, a1),...,(pn, an) --> (p1, a1), (p1+p2, a2), ..., (p1+..+pn, an)
  def cumulative[A](l: List[(Double, A)]): List[(Double, A)] =
    l.tail.scanLeft(l.head):
      case ((r, _), (r2, a2)) => (r + r2, a2)

  // (p1, a1),...,(pn, an) --> ai, selected randomly and fairly
  def draw[A](cumulativeList: List[(Double, A)])(using rnd: Random): A =
    val rndVal = rnd.nextDouble() * cumulativeList.last._1
    cumulativeList.collectFirst:
      case (r, a) if r >= rndVal => a
    .get

  // (p1, a1),...,(pn, an) --> { a1 -> P1%, ..., an -> Pn% }
  def statistics[A](choices: Set[(Double, A)], size: Int)
                          (using rnd: Random): Map[A, Int] =
    (1 to size).map(_ => draw(cumulative(choices.toList)))
                      .groupBy(identity).view.mapValues(_.size).toMap

The unit test in the deck pins the behaviour with a tolerance — and carries an honest editorial note: "to be improved, e.g. with random monad!" (the monad machinery of chapter 7 reappears here as a testing concern). With choices 1.0 → "a", 2.0 → "b", 3.0 → "c", the cumulative list is List((1.0, "a"), (3.0, "b"), (6.0, "c")), and over 10 000 draws the counts must land within ±500 of the expected 1666 / 3333 / 5000:

import org.scalatest.funsuite.AnyFunSuite
import org.scalatest.matchers.should.Matchers.*
import org.scalactic.Tolerance.convertNumericToPlusOrMinusWrapper

class StochasticsSpec extends AnyFunSuite:
  import Stochastics.given

  val choices = Set(1.0 -> "a", 2.0 -> "b", 3.0 -> "c")

  test("Choices should correctly give cumulative list"):
    Stochastics.cumulative(choices.toList) shouldBe
      List((1.0, "a"), (3.0, "b"), (6.0, "c"))

  test("Choices should correctly draw"):
    val map = Stochastics.statistics(choices, 10000)
    map("a") shouldBe 1666 +- 500
    map("b") shouldBe 3333 +- 500
    map("c") shouldBe 5000 +- 500

5. CTMC: time, rates and the exponential law

Probabilities answer "how likely"; the next question is "when". The deck starts from the observation that "many natural/computational phenomena are timed": it is key to consider when something happens, continuously — "time is hence a mechanism to consider when our design has to be validated against timing aspects, and when we are generally concerned about the actual reactivity of a system in providing a certain service".

Which model of time?

• Discrete time — by time ticks, already covered by DTMC;
• Continuous time — a real number, resembling physical time-passing.

And which timing model for transitions? One extreme: label a transition with a positive real number saying exactly how much time the transition takes — "example incarnations based on this idea include Timed Petri Nets", but "this model is considered too synchronous for real distributed systems". The middle ground is a semi-synchronous timing model: the positive real attached to a transition is its average expected time — "which can actually be lower or higher in each case, depending on probability" — and "sometimes, average frequency is instead used, also called rate". The model is captured by a cumulative distribution function describing the probability that a transition fires after a given amount of time elapsed; several such functions could be used:

• synchronous model — a threshold function;
• semi-synchronous model — a piecewise linear function;
• asynchronous model — a more gradually increasing function;
• "markovian" model — a negative exponential function.

CTMC: transition systems with rates

CTMC (Continuous-Time Markov Chains) — as an extension of TS. It is a couple ⟨S, →⟩ where → ⊆ S × ℝ⁺ × S: a directed graph where each edge is labelled with a (Markovian) rate r; transitions are probabilistic and timed, using as cumulative distribution function the exponential one 1 − e^(−t·r).

The exponential distribution is the deck's choice, and the reasons are given in full. First, empirical: many natural/artificial systems follow it — "radioactive particle decays, arrival of the next email (in a small period), mutations on a DNA strand, roadkill on a given street" — and "it is often used when not much information is known about variability". Second, and deeper: it is the distribution of memoryless processes:

Formally, let X be the time at which an event occurs: memoryless means P(X > s + t | X > t) = P(X > s).

Then P(X > s + t) = P(X > s) · P(X > t), and P(X > t) decreases in t. The only continuous function satisfying this is P(X > t) = e^(−r·t), where 1/r is the average value — or vice versa P(X ≤ t) = 1 − e^(−r·t). "In fact, note that this is a 'self-similar' function..."

If the event has not happened yet, nothing new is known about when it will happen in the future — the process has no memory, and the exponential is the only continuous distribution with that property. The rate r is the average frequency, so the average waiting time is 1/r.

6. Competing transitions and the Gillespie algorithm

In a CTMC several transitions are usually allowed from the same state. How do we draw the choice, and how do we state how much time passed? "Some simple math" answers both:

Assume in a state S several transitions are allowed: S -r1→ S1, S -r2→ S2, ..., S -rn→ Sn.

1. the probability of transiting to Si is ri/R, where R = r1 + r2 + ... + rn;

2. S will transit to a new state at Markovian rate R.

⇒ see "Distribution of the minimum of exponential random variables": P(X > min(t1, ..., tn)) = 1 − P(X < min(t1, ..., tn)) = 1 − e^(−r1·t) · ... · e^(−rn·t) = 1 − e^(−(r1+...+rn)·t).

The intuition: each competing transition has its own exponential clock; the one that rings first wins. The minimum of independent exponentials with rates r1..rn is exponential with rate R = Σri, and the probability that clock i is the first is ri/R — proportional to its rate. Two consequences worth stating: "the probability part of CTMC is the same as a DTMC (with normalisation)" — the CTMC's embedded chain is a DTMC — and "DTMC equates a CTMC if we forget about its duration aspects".

The Gillespie algorithm (1977)

Simulation of a CTMC is done by Gillespie's algorithm. One simulation step:

1. take the next states and rates from the current state: (S1, r1), ..., (Sn, rn);
2. let R be the sum of rates Σ ri;
3. choose the next state Si by probability ri/R, using a random number τ1;
4. draw a Δt by exponential distribution with rate R, using a random number τ2: Δt = (1/R) · log(1/τ2).

Simulation results have the form [S0s, t0s], [S1s, t1s], ..., [Sns, tns] — a trace of states with their cumulative times. The deck notes: "as expected, the same as DTMC when duration is not considered", and "drawing duration is essentially computing the inverse of CDF on a random number".

The Scala implementation: CTMC and CTMCSimulation

The meta-meta-model is a trait with one operation, mirroring System of chapter 9, section 4:

trait CTMC[S]:
  import CTMC.Action
  def transitions(a: S): Set[Action[S]]   // rate + state

object CTMC:

  case class Action[S](rate: Double, state: S)
  extension [S](rate: Double)
    def -->(state: S) = Action(rate, state)

  case class Transition[S](state: S, action: Action[S])

  def ofFunction[S](f: PartialFunction[S, Set[Action[S]]]): CTMC[S] =
    s => f.applyOrElse(s, x => Set[Action[S]]())

  def ofRelation[S](rel: Set[Transition[S]]): CTMC[S] =
    ofFunction(s => rel.filter(_.state == s).map(_.action))

  def ofTransitions[S](rel: Transition[S]*): CTMC[S] = ofRelation(rel.toSet)

The stochastic channel of section 5 is one expression — note the rates: IDLE → SEND is slow (rate 1), everything inside SEND is fast, and DONE → DONE at rate 1 makes success sticky:

object StochasticChannel:
  enum State:
    case IDLE, SEND, DONE, FAIL;

  export State.*
  export u07.modelling.CTMCSimulation.*

  def stocChannel: CTMC[State] = CTMC.ofTransitions(
    Transition(IDLE, 1.0 --> SEND),
    Transition(SEND, 100000.0 --> SEND),
    Transition(SEND, 200000.0 --> DONE),
    Transition(SEND, 100000.0 --> FAIL),
    Transition(FAIL, 100000.0 --> IDLE),
    Transition(DONE, 1.0 --> DONE)
  )

Simulation is a lazy stream of events — Trace = LazyList[Event] — built with LazyList.iterate. A deadlock state repeats itself at the same time; otherwise the next state is drawn from the normalised rates and the time advances by the exponential draw:

import java.util.Random
import u07.utils.Stochastics

object CTMCSimulation:

  case class Event[A](time: Double, state: A)
  type Trace[A] = LazyList[Event[A]]

  export CTMC.*

  extension [S](self: CTMC[S])
    def newSimulationTrace(s0: S, rnd: Random): Trace[S] =
      LazyList.iterate(Event(0.0, s0)):
        case Event(t, s) =>
          if self.transitions(s).isEmpty
          then Event(t, s)
          else
            val choices = self.transitions(s) map (t => (t.rate, t.state))
            val next = Stochastics.cumulative(choices.toList)
            val sumR = next.last._1
            val choice = Stochastics.draw(next)(using rnd)
            Event(t + Math.log(1 / rnd.nextDouble()) / sumR, choice)

The deck prints a sample run of the DTMC interpreter of section 4 as successive [probability, state] pairs — lines such as [5.9999999999999998e-1, s1] (probability 0.6 towards s1), [2.0000000000000001e-1, s2] (0.2 towards s2), and occasional [1.0e+1, s1] / [1.0, s3] — the drawing of a model whose labels mix probabilities and likelihood factors. The exact model is the slide's example; what matters is the shape: each line is one draw of the next state weighted by its label. For the stochastic channel, the widget below lets you draw such steps yourself, with the actual rates of the lecture.

7. Stochastic Petri Nets: Petri Nets plus rates

The meta-model upgrade is the promised one: PN + CTMC. "Each Petri transition is associated with a rate — such a rate could be a formula of the number of tokens in each incoming place. When the transition can fire it competes with all other pending ones. Probabilistically, the fastest one wins, and a duration is applied."

The structural change to Trn is minimal: cond, eff and inh stay, and a rate function is added — MSet[P] => Double, so the rate may depend on the current marking. The compilation step is the CTMC analogue of toSystem:

object SPN:

  // pre-conditions, rate, effects, inhibition
  case class Trn[P](
    cond: MSet[P],
    rate: MSet[P] => Double,
    eff: MSet[P],
    inh: MSet[P])

  type SPN[P] = Set[Trn[P]]

  def toCTMC[P](spn: SPN[P]): CTMC[MSet[P]] =
    m =>
      for
        Trn(cond, rate, eff, inh) <- spn
        if m disjoined inh
        r = rate(m)
        out <- m extract cond
      yield Action(r, out union eff)

  def apply[P](transitions: Trn[P]*): SPN[P] = transitions.toSet

Compare with PetriNet.toSystem of chapter 9, section 7: the only differences are the rate function (computed on the current marking) and the target type (CTMC[MSet[P]] instead of System[MSet[P]]). The enablement machinery — inhibition check, extract, union eff — is identical. The meta-modelling promise of chapter 9 pays off: the DSL changed by three lines.

The deck's canonical application is producers and consumers: two producers send data items at rates rp1 and rp2, one consumer processes items at rate rc:

        rp1                    rp2                  rc
M ────────→ d | M        M ────────→ d | M        M | d ─────→ M

And the stochastic version of mutual exclusion shows rates as marking-dependent formulas: the first transition has fixed rate 1.0, the second has rate m(T) — "the more processes are trying, the faster one of them gets in" — and the third has fixed rate 2.0:

object StochasticMutualExclusion extends App:
  // Specification of my data-type for states
  enum Place:
    case N, T, C

  export Place.*
  export u07.modelling.CTMCSimulation.*
  export u07.modelling.SPN.*

  val spn = SPN[Place](
    Trn(MSet(N), m => 1.0,     MSet(T), MSet()),
    Trn(MSet(T), m => m(T),    MSet(C), MSet(C)),
    Trn(MSet(C), m => 2.0,     MSet(),  MSet()))

  println:
    toCTMC(spn).newSimulationTrace(MSet(N, N, N, N), new Random)
      .take(20)
      .toList.mkString("\n")

The stochastic readers/writers of the deck give the full rate table (to be reused in PRISM in chapter 11, section 6): t1: 1.0 (a fixed rate of actual arrival of requests), t2: 200000 (almost immediate, 66% of readers), t3: 100000 (almost immediate, 33% of writers), t4: 100000 and t5: 100000 (immediate), t6: 0.1·p6 (average "rate" of reading is 0.1, scaled by the number of readers), t7: 0.2 (average "rate" of writing is 0.2).

8. Chemistry as a stochastic model

The deck makes a striking observation: "This is precisely the chemical settings!!!" The stochastic mutual exclusion of section 7 is structurally the sodium-chloride reaction:

Ionization law:    Na + Cl  ──rio──→  Na+ + Cl−
Deionization law:  Na+ + Cl− ──rdeio─→  Na + Cl

"Chemical system dynamics is precisely the same as in Stochastic Petri Nets!" — with the rates computed from the current amounts:

• Ionization rate = #Na · #Cl · rio — the more sodium and chloride molecules are around, the more frequently a pair ionises;
• Deionization rate = #Na⁺ · #Cl⁻ · rdeio.

This is the law of mass action: reaction rates proportional to the product of reactant concentrations — exactly a marking-dependent rate function of an SPN. The simulation of such a system "is done by Gillespie algorithm", and the deck shows a chart of the counts of Na, Cl, Na⁺ evolving over time: the system oscillates around the equilibrium while the total number of particles stays constant — no particle is created or destroyed, only ionised and deionised.

9. Towards large-scale models: gossip and spatial networks

The last move of the lecture extends Petri Nets towards the systems that motivate the course — networks of hundreds or thousands of devices. The deck's recipe is an ad-hoc extension:

• think of a network of devices as a graph;
• each device is modelled by the same Petri Net;
• a special outgoing arc — the "firing arc" — models broadcasting the token to all neighbours;
• transitions have markovian rates (à la CTMC).

The example is a gossip algorithm on such a net, with three rules (note the rate 100000 — "quickly" — on the first):

       100000
a | a ──────→ a          the first transition makes sure a node holds only one copy of a
       1
a | b ──────→ b          the second erases tokens a where a b occurs
       1
a ──────→ a | a          the third spreads tokens a into neighbours

"Overall: a is gossiped in the whole network, blocked where b occurs." The a | a → a rule deduplicates (a node never keeps two copies), a | b → b makes b absorb nearby a tokens, and a → a | a is the broadcast: one token produces one copy per neighbour. In a grid, the a wavefront propagates until it meets a b region.

The full machinery — called DAP (Distributed Asynchronous Processes) in the next deck — is the meta-model behind this. A rule is pre −rateExp→ eff | ^msg: preconditions, a rate expression, effects, and an outgoing message; a token is localised in a node and characterised by an ID; the network state is tokens plus pending messages plus the neighbourhood map; and the operational semantics is a CTMC whose actions either apply a rule in a node or deliver a message with infinite rate (messages are instantaneous):

object DAP:
  // Rule of the net: pre -- rateExp --> eff | ^ msg
  case class Rule[P](pre: MSet[P], rateExp: MSet[P] => Double, eff: MSet[P], msg: MSet[P])

  // Whole net's type
  type DAP[P] = Set[Rule[P]]

  // A Token, localised in a given node, characterised by an ID
  case class Token[ID, P](id: ID, p: P)

  // state of the network at a given time, with neighbouring as a map
  case class State[ID, P](
    tokens: MSet[Token[ID, P]],
    messages: MSet[Token[ID, P]],
    neighbours: Map[ID, Set[ID]])

  // Local facility to extract the marking of a node
  def localTokens[ID, P](tokens: MSet[Token[ID, P]], id: ID): MSet[P] =
    tokens.collect:
      case Token(`id`, t) => t    // quotes are needed to match an existing variable

Its operational semantics, as a CTMC, first tries to apply every rule in every node (with the rate computed from the local marking — the neighbours' tokens stay out of reach, so the rate is local), and then delivers pending messages: each message token spreads a copy to all neighbours of its node and disappears — Action(Double.PositiveInfinity, ...), "note rate is infinity":

def toPartialFunction[ID, P](spn: DAP[P]): PartialFunction[State[ID, P], Set[Action[State[ID, P]]]] =
  case State(tokens, messages, neighbours) =>
    // we first try to apply rules
    (for
      Rule(pre, rateExp, eff, msg) <- spn            // get any rule
      nodeId <- neighbours.keySet                    // get any node
      out <- tokens extract pre.map(Token(nodeId, _)) // checks if that node matches pre
      newtokens = out union eff.map(Token(nodeId, _)) // generate new tokens
      newmessages = messages union msg.map(Token(nodeId, _)) // generate new messages
      rate = rateExp(localTokens(tokens, nodeId))    // compute rate
    yield Action(rate, State(newtokens, newmessages, neighbours)))
    ++
    (for
      Token(id: ID, p: P) <- messages.asList.toSet   // get any pending message
      newtokens = tokens union MSet.ofList(neighbours(id).toList.map(Token(_, p))) // compute spread tokens
      newmessages <- messages extract MSet(Token(id, p)) // drop the message
    yield Action(Double.PositiveInfinity, State(newtokens, newmessages, neighbours))) // note rate is infinity

def toCTMC[ID, P](spn: DAP[P]): CTMC[State[ID, P]] = CTMC.ofFunction(toPartialFunction(spn))

And the gossip example from the next lecture, run on a 5×5 rectangular grid with one a token on the top-left corner — the trace prints, at each step, the time and a grid rendering of where the a tokens are:

object DAPGossip:
  enum Place:
    case A, B, C
  type ID = (Int, Int)
  export Place.*
  export u08.modelling.DAP.*
  export u08.modelling.DAPGrid.*
  export u08.modelling.CTMCSimulation.*

  val gossipRules = DAP[Place](
    Rule(MSet(A, A), m => 1000, MSet(A), MSet()),   // a | a -1000-> a
    Rule(MSet(A),    m => 1,    MSet(A), MSet(A)))  // a -1-> a |^ a

  val gossipCTMC = DAP.toCTMC[ID, Place](gossipRules)
  val net = Grids.createRectangularGrid(5, 5)
  // an 'a' initial on top LEFT
  val state = State[ID, Place](MSet(Token((0, 0), A)), MSet(), net)

@main def mainDAPGossip =
  import DAPGossip.*
  gossipCTMC.newSimulationTrace(state, new Random).take(50).toList.foreach: step =>
    println(step._1)                                  // print time
    println(DAPGrid.simpleGridStateToString[Place](step._2, A)) // print state, i.e. A's

10. Lab: operational steps and R&D directions

The lab repository is the same https://github.com/mviroli/asmd-public-models, folder u07 (from Virtuale), imported in IntelliJ as an SBT project.

Operational steps

• Step 1 — download and check. Get acquainted with all parts: utils (the MSet abstraction "and also others"), modelling (the API/DSL: CTMC, CTMCSimulation as meta-meta-model, then SPN and DAP as meta-model), examples (extensional StochasticChannel; intensional by Petri Nets StochasticMutualExclusion and by DAP DAPGossip), and test. Check that all tests and checks pass and understand why.
• Step 2 — implement the stochastic readers & writers of the slides, and run it: "is it enough to give evidence of correctness of expected behaviour?" — note the difference between evidence from runs and verification; the next chapter closes that gap.
• Step 3 — play with DAPGossip. Implement and simulate a system where gossip-like broadcasts send a message and get a reply from a node: "the reply is eventually received only if a target is ever reached".

R&D tasks

Test your knowledge