CPNs, LLMs, and Distributed Applications
A big theme in LLM-enabled software dev is that verifiable correctness makes it much easier to take bigger leaps with LLMs. E.g. tests, compilers, state machines, etc. While researching for databuild, I recently came across colored petri nets, and instantly saw opportunity.
Colored petri nets (CPNs) are an extension of petri nets. Petri nets are essentially directed bipartite graphs where places can contain tokens, and places are connected by transitions (where the side effects happen). In petri nets, a single token contains no data, and represents an identity-less tokens location in the net. Importantly, petri nets with transitions that have only one input and output and one token globally are equivalent to finite state machines. Colored petri nets extend this model, allowing individual tokens to have data associated with them. This allows CPNs to match closely to the Rust typestate pattern, and suggests Rust may be able to implement CPN semantics easily.
CPNs are of particular interest because a) it is still hard to write concurrent applications and b) provide the potential for formally verifying concurrent programs at build time. Also, if we can implement a high performance datastore underneath, a CPN framework might be able to handle the hard parts of concurrent applications: state synchronization, conflict detection, deadlock avoidance, and coordinating access to shared resources. These are enabled via two other features of CPNs: guards and multi-token consumption/production.
A guard is a list of boolean conditions that may apply to a transition: things that must be true for a token to take that transition. For instance, there need to be more than 0 connections available in the connection pool to claim one. Multi-token consumption/production is just what it sounds like: a fork in the network via a transition, where P1 -> T1 -> (P2, P3), so T1 consuming a token from P1 produces a token in each of P2 and P3 simultaneously. Conversely, a join in the network via a transition, where (P1, P2) -> T1 -> P3, would require that both P1 and P2 to have tokens present that are able to transition via T1 into P3, which will also be simultaneous.
One application that has light concurrency involved is web scraping with leased proxies and scrape targets. You have a limited number of proxies to use to proxy your requests, and need to rate limit your usage of all of them to ensure they don't over-request a given target. Also, you both want to avoid requesting the same target multiple times concurrently, and also avoid making requests to the domain too frequently, to be a responsible user. Traditionally, this is solved with leasing of resources via a central database, implemented via select for update style semantics in the database. We can imagine implementing this with CPN semantics as having the scrape_target transition being the join of the available_proxies and prioritized_targets places, with a scrape only starting when a proxy is available and a prioritized target is available. You can also imagine implementing other complex distributed scraper features with CPN semantics:
Scrape target cooldowns : after being scraped, a target token transitions to a cool_down state, where using a timed petri net allows us to delay transitioning back to prioritized_targets after the delay period.
: after being scraped, a target token transitions to a state, where using a timed petri net allows us to delay transitioning back to after the delay period. Domain-level rate limiting : add a separate domains token, so that the scrape_target transition is a 3-way join domains x available_proxies x prioritized_targets .
: add a separate token, so that the transition is a 3-way join . Retry with backoff : Failed scrapes fork: one token to failed_log, one back to prioritized_targets with incremented retry count and a longer cooldown. Guard prevents retries beyond max attempts.
: Failed scrapes fork: one token to failed_log, one back to prioritized_targets with incremented retry count and a longer cooldown. Guard prevents retries beyond max attempts. Result pipeline — Post-scrape, tokens flow through raw_html → parsed → validated → stored, each with its own concurrency limits, which naturally implements back pressure.
... continue reading