chemart / disperser
View on GitHubChemical disperser (load balancing) — 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 ot…
How it works
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.
- S
- job molecules X_i (one species per node) and catalysts C_i_j (one per directed link, located at node i) · explicit
- R
- C_ij + X_i --k--> C_ij + X_j, for all (i,j) in E · arity 2
- A
- ssa, compartments · none
Parameters
| name | default | meaning |
|---|---|---|
| graph list · spatial |
[[1, 2], [1, 3], [1, 4], [2, 3]] | undirected links [u, v] of the network; every link carries a catalyst in each direction |
| k float · kinetic |
1.0 | rate coefficient, the same for all links; node degree then sets the outflow rate [0, ∞] |
| catalyst_concentration float · population |
1.0 | concentration of every catalyst C_i_j, held constant and equal everywhere [0, ∞] |
| initial_jobs dict · population |
{"4": 1000} | node id (as a string) -> initial number of job molecules; other nodes start empty |
Chemical disperser (load balancing)
One of the artificial chemistries of Banzhaf & Yamamoto, Artificial Chemistries (MIT Press, 2015), §17.3.1; appendix (Disperser.py); first proposed by Meyer & Tschudin, 2009.
Its generator ships with the chemart library, so loading it runs no code from the hub and needs no trust_remote_code.
import chemart
net = chemart.generate_network("chemart/disperser", seed=0) # same as "disperser"
print(net.summary())
What to look for
- 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)
Implementation 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
Banzhaf & Yamamoto, Artificial Chemistries (2015), §17.3.1; appendix (Disperser.py)
Preview at default parameters
12 species · 8 reactions · status complete · seed 1
C1_2 + X1 -> C1_2 + X2 [mass-action k=1.0] C1_3 + X1 -> C1_3 + X3 [mass-action k=1.0] C1_4 + X1 -> C1_4 + X4 [mass-action k=1.0] C2_1 + X2 -> C2_1 + X1 [mass-action k=1.0] C2_3 + X2 -> C2_3 + X3 [mass-action k=1.0] C3_1 + X3 -> C3_1 + X1 [mass-action k=1.0] C3_2 + X3 -> C3_2 + X2 [mass-action k=1.0] C4_1 + X4 -> C4_1 + X1 [mass-action k=1.0]
Generated by the uploader with chemart push; the hub never runs uploaded code.