Skip to content

§2.3 Behavioral Models: What May Happen?

A behavioral model represents how a system acts or changes over time. It may describe the messages exchanged by components, the order of steps in a workflow, or how a quantity changes continuously. Where a structural model like a dependency graph answers what is connected to what?, a behavioral model asks what may happen, and in what order? The representation should preserve the distinctions needed to answer the engineering question while leaving out implementation details that do not affect it.

2.3.1 Modeling Behavior with States and Transitions

For lifecycle and recovery questions, a state-transition model makes explicit which states matter and how the system can move between them. This is the form of behavioral modeling developed here. A finite-state machine names a finite set of states and the transitions between them. A labeled transition system associates transitions with actions or events. Statecharts add hierarchy and concurrency to organize more complex behavior 1.1. David Harel, “Statecharts: A Visual Formalism for Complex Systems,” Science of Computer Programming 8, no. 3 (1987): 231–74, https://doi.org/10.1016/0167-6423(87)90035-9. Temporal specifications let us state properties over executions, such as whether every started job eventually finishes. These representations support reasoning about order, reachability, and progress without retaining the code that implements each operation.

That reduction is what makes behavior checkable. A job-processing service described only through its handlers, database writes, and retries hides the very question an engineer most needs to ask — can the system reach a state it should never occupy? The same service, reduced to a handful of states and the transitions between them, turns that question into one a person or a tool can actually answer (Figure 2.3-1).

Figure 2.10: Job Execution with Retries Editable vector recreation of the author-supplied reference. A state model for a remediation job, including retries. A state model for a remediation job, including retries.PendingRunningSucceededRetrying(attempt = n)FailedA worker executes thenext computation for the job.Job completeswith a correcteddocument.On a repairable failure,retry (up to a limit,If retries are exhaustedor the error is not repairable,the job fails.e.g., n ≤ 3).Key properties (examples)• At most N retry attempts (e.g., N = 3).• A job eventually reaches Succeeded or Failed.• Only one worker actively executes the job at a time.
Figure 2.3-1. The behavioral move: states and transitions. This example specifies an allowed job lifecycle: a job passes through Running before Succeeded, with retry and failure transitions describing other possible paths. The legend lists example properties to investigate.

Nodes represent states, and directed edges represent transitions. A path from an initial state describes an execution admitted by the model. The model’s purpose tells us how to interpret that execution. A specification declares allowed behavior, as Figure 2.3-1 does: omitting a direct Pending → Succeeded transition forbids that step. A model of an implementation can instead represent behavior we intend to investigate, including states or transitions that may violate a requirement. Representing a state therefore does not, by itself, declare it acceptable.

The required property tells us what to check over those executions. “A job never reaches Succeeded before Running” is a safety property: any violation has a finite execution prefix that demonstrates it. “Every started job eventually finishes or fails” is a liveness property: observing a finite period of waiting does not establish that the wait will last forever. Reachability asks whether a state can occur; it serves a safety check when the state being sought violates a required invariant. The choice among transition validation, reachability search, invariant checking, and temporal model checking follows from the property we want to establish 2.2. Christel Baier and Joost-Pieter Katoen, Principles of Model Checking (MIT Press, 2008).

A simple job lifecycle also shows the limit of an ordering property. Requiring every path into Succeeded to pass through Running excludes premature completion, but a job could remain in Running indefinitely. These are different questions about the same behavioral model. A transition check asks whether a particular state change is permitted; reachability analysis asks whether some sequence of transitions can lead to an undesirable state; and a temporal property can require that every started job eventually finishes or fails. Investigating that last property requires representing the ways processing can wait or retry, together with assumptions under which progress is expected. The model may therefore need to change as the engineering question changes.

2.3.2 Ownership Under Contention

When several workers can process the same job, who owns this job? depends on their claims. A worker may stop responding, its claim may expire, and another worker may acquire the job. The original worker can later return and attempt to act using its old claim. An ownership model must retain enough information to distinguish the current right to act from a claim that is no longer valid.

Table 2.3-1 distinguishes four familiar constructs used to represent access and ownership.

Table 2.3-1. Constructs for access and ownership. Locks, leases, capabilities, and claims express different aspects of a worker's right to act.
ConstructWhat it expresses
LockCoordinates access to a resource. An exclusive lock admits one holder at a time.
LeaseGrants a right for a limited period; expiry can make that right available for reassignment 3.3. Cary G. Gray and David R. Cheriton, “Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency,” Proceedings of the Twelfth ACM Symposium on Operating Systems Principles (New York), 1989, 202–10, https://doi.org/10.1145/74850.74870.
CapabilityCarries authority to perform specified operations on a resource; that authority need not be exclusive.
ClaimRecords a worker’s assignment to a job and the conditions under which that assignment is valid.

These constructs can be combined. For a leased job, the ownership model records the worker’s claim and how expiry or reassignment changes it. The next distinction is between successive claims on the same job.

A claim binds a holder to a resource and carries the facts that make contention decidable: which holder, which generation of claim, and when it expires. The generation is the fact a bare "A owns X" edge cannot express — it distinguishes a current claim from a superseded one. The difficult failures arise from the interleavings: the orders in which concurrent claims, expiries, and reclaims can occur. So the characteristic analysis is state-space exploration over those sequences, with an invariant checked at each reachable configuration — the behavioral toolkit of this section pointed at a concurrency question.

For example, a worker may hold a job, lose its claim after a timeout, and later return with an old completion request. The current owner alone is insufficient to decide whether that request still applies: the model must distinguish successive claims on the same job. Recording a claim generation supplies that distinction. At this level, a job is leased exactly when it has a current claim; the claim represents ownership directly. DocAble's recovery and ownership models show how such small additions support two concrete crash-safety questions.

WORKED EXAMPLEDEEP DIVE

Worked example — Recovery and ownership of a document job

DocAble distributes document accessibility work across workers. A worker can fail while producing a corrected document, and another worker may have to recover the job. Safe recovery therefore involves two related questions: when is a recovered artifact safe to publish as the result, and which worker currently has the right to complete the job? Separate models preserve the facts each question needs.

Publishing a recovered result

DocAble must preserve the ordering between publishing a recovered artifact and updating the database record that references it: the record may not name an artifact that has not yet been published. Reduced to its states, that concern is a small model.

Recovery-ordering model · Behavioral

  • Engineering question — In what order may recovery publish an artifact and update the record that refers to it?
  • Model — a transition system over the recovery lifecycle; the decisive fact is a transition that does not exist.
  • Property — the database record may refer to the fallback artifact only after that artifact has been uploaded to persistent storage.
  • Quality attribute — data integrity; crash-safety.

A worker recovering a document job may have a corrected artifact available locally before it has been uploaded to persistent storage. These are different conditions: a local artifact may disappear if the worker fails, while a published artifact remains available to the service. The database record must not refer to the recovered artifact until publication succeeds. Figure 2.3-2 reduces this obligation to three states. In FALLBACK_STAGED, the artifact exists locally; in FALLBACK_UPLOADED, it has been published to durable storage; and in DB_UPDATED, the database refers to it. The permitted path passes through all three states. The forbidden shortcut from FALLBACK_STAGED to DB_UPDATED captures the failure the model must exclude: a worker could update the database and then crash before uploading the artifact, leaving the record pointing to a result that other workers cannot retrieve.

The model omits the storage API, retry machinery, and other recovery details because they do not determine this ordering requirement. To check the property, search for a path to DB_UPDATED that does not pass through FALLBACK_UPLOADED. In a larger lifecycle, checking only for the direct forbidden transition would miss an indirect route through other states. The model establishes publication order, not eventual completion: a worker could wait or retry indefinitely without violating the ordering constraint.

Recovery-Ordering ModelAuthor-reference redraw with editable text, explicit states, and permitted and prohibited transitions. A state model for publishing a recovered artifact. FALLBACK_STAGED (artifact exists locally) FALLBACK_UPLOADED (artifact durably stored) DB_UPDATED (database refers to artifact) Forbidden: update DB before upload Permitted transition Prohibited transition The artifact must be published (durably stored) before the database may refer to it.
Figure 2.3-2. Recovery-ordering model. A recovered artifact must be published to durable storage before the database may refer to it. The prohibited transition from FALLBACK_STAGED directly to DB_UPDATED illustrates the ordering violation; the property also excludes indirect paths that bypass FALLBACK_UPLOADED.

The three-state recovery model is a reduction for checking publication order. DocAble’s fuller job lifecycle includes queued, leased, remediating, and completed or failed states. That model can address broader workflow questions when it includes the relevant transitions; the smaller recovery model keeps only what the ordering question needs.

Distinguishing a current owner from a returning one

DocAble leases each in-flight job to one worker. A lease carries an owner, a monotonically increasing generation, and a lifetime; when a lease looks abandoned it can be reclaimed and the job re-leased to another worker at the next generation.

In-flight lease · Ownership

  • Engineering question — Who currently owns this in-flight work, and can a returning stale owner disturb the current claim?
  • Model — a claim relating a worker to a job, stamped with a generation and a lifetime; reclaim advances the generation.
  • Property — a stale claim cannot clear or supersede the current one.
  • Quality attribute — correctness under concurrency; crash-safety.

Start with what the model means. A job is leased exactly when it has an owner; the two are the same fact seen from two sides, so the model represents ownership as the presence of a current claim rather than as a separate flag that could disagree with it. That is a definition, not a property that could fail. It sets up the invariant that can.

The next invariant concerns ownership under contention. A stale claim must not clear or supersede the current claim. Suppose worker A holds a claim at generation 7, appears to stall, and loses its lease. Worker B then acquires the job at generation 8. When A returns and attempts to release its generation-7 claim, that operation must not clear B's current claim. Figure 2.3-3 models this sequence. The generation number distinguishes successive claims on the same job, making the stale release identifiable and rejectable. Without it, A's delayed release could clear B's valid claim. The model preserves owner, generation, and lifetime while omitting the worker implementation and the machinery that stores the lease.

Ownership Under ContentionAuthor-reference redraw with editable text, explicit states, and permitted and prohibited transitions. A behavioral model for job ownership with generations. Claims identify (worker, generation). Unowned Owned (A, 7) Owned (B, 8) Reclaimable claim(A, 7) expire claim(B, 8) release(A, 7) (rejected: stale generation) release(B, 8) Release clears ownership only when worker and generation match the current claim.
Figure 2.3-3. Ownership under contention. Worker A’s generation-7 claim expires and worker B acquires generation 8. A later release from A cannot clear B’s current claim. Recording the generation makes stale operations distinguishable from operations authorized by the current owner.

The publication model separates a local artifact from a durably stored one. The ownership model separates a current claim from a superseded one. In each case, the useful addition is a distinction that changes whether a state change is acceptable. The models make those distinctions available for analysis; the later Alignment chapter examines the mechanisms that enforce them.

Notice what this model omits: the processing topology. Ownership, generation, lifetime, and reclamation matter to the question of who controls a job; how the job's work is partitioned does not. DocAble's implementation changed over time to improve performance while preserving those ownership semantics. We changed the pointers to the code, but not the model. The ownership properties could therefore remain invariants across those changes. The inset explains what an invariant requires and how a checker evaluates one.

FORMAL METHODS

Inset — What is an invariant?

An invariant is a property required to hold over a declared domain of states, structures, or observations. In a behavioral state machine, the invariant may be a predicate that must hold in every reachable state; in a structural model, it may require every observed dependency to belong to a declared set; in a measurement model, it may require a quantity to remain within a hard capacity bound. State both the property and the domain the checker claims to establish it over.

Take a behavioral illustration. A job carries two fields at once — a status of free, leased, or done, and a lease_owner that names the holding worker or is empty. At the model level, leased-iff-owner was a definition; an implementation that represents the two sides as separately written fields turns it into a property that can fail, which is exactly why you write the invariant down. "A job is leased if and only if it has an owner" is a predicate over the pair: (status == "leased") == (lease_owner is not None). A free status with a lingering lease_owner is a stale lease; a leased status with no owner is a lost lease. Separating the two writes can make either inconsistent state reachable, and both break the predicate. The predicate becomes mechanically meaningful when a checker evaluates it over the declared reachable state space:

STATES = product({"free", "leased", "done"}, {None, "worker-1", "worker-2"}) def invariant(s): # leased iff owned return (s.status == "leased") == (s.lease_owner is not None) assert all(invariant(s) for s in reachable_states()) # check every reachable state

2.3.3 One Representation, Several Questions

A lease illustrates how one representation can answer several classes of question. Its owner identifies who currently controls a job. Its generation and lifetime distinguish current claims from stale ones and support reasoning about expiry and reclamation. Counting the current claims across jobs gives a measurement of how much work is in flight. These questions concern ownership, behavior, and capacity, yet they draw on the same represented facts.

The overlap follows from the distinction introduced at the opening of the chapter: model classes identify engineering questions, not mutually exclusive data structures. One representation can serve several questions when it preserves the facts each requires. §2.5 develops this idea further by connecting models through shared identities.

Ownership introduced permission implicitly: a stale claimant may not clear a current lease. The next section examines decisions directly, including permissions and how to choose what should happen next.

Works Cited

  1. Harel, David. “Statecharts: A Visual Formalism for Complex Systems.” Science of Computer Programming 8, no. 3 (1987): 231–74. https://doi.org/10.1016/0167-6423(87)90035-9.
  2. Baier, Christel, and Joost-Pieter Katoen. Principles of Model Checking. MIT Press, 2008.
  3. Gray, Cary G., and David R. Cheriton. “Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency.” Proceedings of the Twelfth ACM Symposium on Operating Systems Principles (New York), 1989, 202–10. https://doi.org/10.1145/74850.74870.
© James C. Davis, 2026–present