chemart / disperser

hub:
  repo_type: generator
  builtin: disperser
  tags:
  - banzhaf-yamamoto
chemistries:
- id: disperser
  name: Chemical disperser (load balancing)
  intuition: 'A distributed algorithm that happens to be a chemistry. Each network node holds a species
    whose concentration is its workload, and each directed link carries a catalyst that converts a job
    at one end into a job at the other. Run it and the loads provably converge to the network-wide average,
    and return to it after jobs are added or removed. Mass conservation does the safety argument for free:
    the algorithm can never invent or lose work, so it cannot produce a negative load.

    '
  origin: Meyer & Tschudin, 2009
  book: 17.3.1; appendix (Disperser.py)
  refs:
  - '[576]'
  - '[580]'
  - '[941]'
  family: application
  kind: generator
  constructive: false
  S:
    repr: job molecules X_i (one species per node) and catalysts C_i_j (one per directed link, located
      at node i)
    definition: explicit
  R:
    definition: explicit
    arity: 2
    scheme: C_ij + X_i --k--> C_ij + X_j, for all (i,j) in E
  A:
    reactor:
    - ssa
    - compartments
    dilution: none
  params:
  - name: graph
    type: list
    default:
    - - 1
      - 2
    - - 1
      - 3
    - - 1
      - 4
    - - 2
      - 3
    role: spatial
    meaning: undirected links [u, v] of the network; every link carries a catalyst in each direction
  - name: k
    type: float
    default: 1.0
    min: 0
    role: kinetic
    meaning: rate coefficient, the same for all links; node degree then sets the outflow rate
  - name: catalyst_concentration
    type: float
    default: 1.0
    min: 0
    role: population
    meaning: concentration of every catalyst C_i_j, held constant and equal everywhere
  - name: initial_jobs
    type: dict
    default:
      '4': 1000
    role: population
    meaning: node id (as a string) -> initial number of job molecules; other nodes start empty
  provides:
  - topology
  - stoichiometry
  - catalysts
  - rate-constants
  - compartments
  - initial-state
  fidelity: book+decisions
  decisions:
  - 'The book''s 4-node topology (figure 17.3) is only drawn. Edges 1-2, 1-3, 1-4, 2-3 are the graph consistent
    with the text: after injection at node 4, nodes 2 and 3 are the farthest; after injection at node
    2, node 4 is.'
  - Catalyst concentration is not given numerically; default 1. extras.compartments maps each node to
    its X and outgoing C species.
  sources:
  - 'Meyer, T. & Tschudin, C. (2009). Chemical networking protocols. HotNets-VIII (book [576]). Sec. 2.1:
    reaction C_i + X_i -> C_i + X_j, mass-action scheduling by an exact stochastic algorithm; sec. 3.2:
    the Disperser protocol, one catalyst C_ik per link, ODE (5), fixpoint = network average (6-7), Jacobian
    = -Laplacian (8-9); sec. 3.3: comparison with gossip-based Push-Sum. http://conferences.sigcomm.org/hotnets/2009/papers/hotnets2009-final66.pdf'
  - 'Yamamoto, L. (2013/2015). Disperser.py, PyCellChemistry 1.0: topology [[1,2],[1,3],[1,4],[2,3]],
    Gillespie vessel with N_A*V = 1 so c = k = 1, one molecule of each catalyst, 1000 X4 at t = 0, 600
    X2 injected at t = 10, 300 X2 expelled at t = 20, run to t = 30 (the book''s figure 17.3). https://www.cs.mun.ca/~banzhaf/pycellchem-1.0.tgz'
  reference_impl: PyCellChemistry Disperser.py
  phenomena:
  - provable convergence to the network-wide average x_bar = sum_i x_i(0)/n, stable under injection and
    deletion (1000 jobs on 4 nodes -> 250 each)
  notes: 'The cleanest ''chemistry as a provable distributed algorithm'' example: mass conservation means
    the algorithm can never produce a negative load, and the ODE can be checked for convergence and stability
    directly.

    '