Introduction
The term “STATE” is used in a number of ways in the world of programming, computing, and modeling the world in general. “State” means a wide variety of things depending on the kinds of things one is talking about. From a technologist viewpoint, I realize that getting all these notions of state lined up properly is essential. Furthermore, getting the appropriate interpretation right is quite important to model a problem. Furthermore, usually, there are multiple connotations of state applicable to a problem. This is well-illustrated by the article in the ACM Queue magazine on modeling “state” in web applications. This essay attempts to provide a conceptual overview of the notion of state in its various forms to re-enforce some essential concepts and highlight some key issues that any software/hardware systems designer should keep in mind.
State – A techie’s common sense understanding
Before delving into the nuanced “computational” notion of “state”, it would be
relevant to baseline ourselves with the generic notion of “state” in common lingo. The term “state” has become part of common language in a number of idioms such as “state of being”, “state of mind”, “state of a system”, “state of the union” etc. All these notions imply an “assessment of things as they are at a particular point in time”, i.e. a snapshot. The deeper notion of state extends this basic idea further to describe and understand how “systems” in general change over time, how things over time can be modified and
controlled. This may be conceptualized as establishing relationships between a sequence of snapshots over time. Two potential interpretations are possible of a snapshot – a) The current snapshot “embeds” all the history from the past, and b) The current snapshot
does not embed all history. Different kinds of systems (when they are built) may use (or exhibit) either of these interpretations of state. Systems transition from state to state via actions or events that may be activated internally (in a well-defined way or may happen randomly) or by external actors. For example, some financial wizards on Wall Street assume that the price of a stock reflects its history and expectation about its future performance whereas others suggest the price is a completely random phenomena!
So given this context, the key issues in modeling state are:
- What makes up the “description” of a state? What are the parameters used to describe a state? Are they logical, categorical, data, continuous, numeric parameters? For example, in financial markets – the complete state of a company is captured in one number – its stock price. Additional parameters include earnings and other financial indicators.
- What is the internal structure of a state? Are there nested states – aka sub-states? How are they described? How is the relationship between the parent and child states? Do these states occur in a single place or are they distributed (physically occurring in different places)
- How many states are there in a dynamic system? if it is finite. Or are there infinite states? How are the “transitions” between states described? Actions or events? Do actions take parameters? Is time captured explicitly in the description? Or is the action assumed to happen instantaneously? How is the duration of time modeled ? Is the action “triggered” by events inside the system or external to the system or both?
- Are the transitions from a state deterministic? are they “non-deterministic”? Are they “stochastic” (with a probability) ? Non-determinism means that an action can cause a transition from one state to a set of states( we do not know which one apriori) instead of a deterministic transition.
The different notions of state in computing (and systems development in general) arise from different assumptions made in response to the above questions. Furthermore, many issues in modern systems arise because they are “composed” of different technologies and subsystems that operate under different models of “state” leading to inevitable blind spots wherein the system behavior is completely unknown (or not cataloged because attention was not paid to tracking such behaviors). The rest of the essay discusses the use of “state” in two classes of systems – analog and digital. In each context, brief examples are provided and the acute reader is advised to further followup if his/her interest is piqued.
Modeling “State” in the Analog world
Analog systems are described by “parameters” that are modeled with “continuous” measures i.e. they can take values from an infinite continuum. Usually one’s first introduction to state is in middle-school or high-school physics and chemistry. The following is a brief list of topics/areas where the notion of state is fundamental:
- Phase space of a particle while understanding the laws of motion. One can plot position and velocity, or momentum and energy etc. and get insights into the motion of a particle. For example, one can plot the phase space for a simple pendulum in single harmonic motion.
- The notion of state is fundamental in our understanding of statistical mechanics and the basic gas laws. Temperature and its relationship to the energy of a system
captures the notions of state. Thermodynamics is fundamentally a study of state of “systems”: solid, liquid, gases and plasma etc. - Atomic structure and quantum mechanics – The motion and energy of particles is described by a variety of state parameters, primarily -momentum and energy. Models include the probabilistic and deterministic versions for phenomena such as modeling photon interactions, radioactive decays (where particles are “emitted”), spin effects etc.
- Other areas include: metallurgy and material science for understanding crystal formation and structure of semiconductors and the like, biological phenomena including protein-protein interactions, electron transfer phenomena (in things like the photo-cycle), signal transduction pathways, systems biology, all fields of engineering – control models of a variety of phenomena, economic systems such as inventory systems, stock markets, modeling the brain -state models of “neurons”, disease, optimization models such as Bellman’s Dynamic Programming and its variations, Monte-Carlo simulation and path analysis etc.
A complete list is beyond the scope of this brief essay, but hopefully the curious reader may follow up. Before the discussion on discrete state modeling, I’d like to note that during WWII and a bit after, (before digital systems were reliable), there were a class of computers called “Analog computers”, which were used to compute and control a large number of phenomena. Computers were built with analog components such as Inductors, Operational amplifiers (opamps in short) and the like to “solve” differential equations and also generate control signals to manage systems. In mechanical systems, there were components used for counting, derivatives of “cams” and cam-like systems to compute functions and perform operations such as differentiation/integration.
Modeling “State” in the Digital World
The early analog computers dominated systems till the advent of semi-conductor based digital systems in the mid 20th century. Given the reliability, miniaturization and scalability of semiconductor devices, the last 50 years have seen a phenomenal growth in the applicability of “digital computers – microprocessors to multi-core systems” in
a wide variety of contexts. Their wide-spread use has gone hand-in-hand with the growth in the variety of “computational models” of real-world phenomena. These computational models have enabled the development of modern software systems. The following is a list of “state models” ranging from abstract (for computational analysis) to the concrete for analyzing different phenomena to highlight the “various” connotations of “state” in a digital context :
1. State models are fundamental to automata theory and a variety of basic concepts in computer science (including Turing machine models), abstract models of computing etc. These models include Finite State Models (machines) – including Mealy and Moore machines (they differ on the “nature” of the transitions”), Finite State transducers and other nuanced variants. Markov models, Hidden Markov Models and other related probabilistic models are used to model systems with embedded stochastic processes. State models are fundamental in the world of hardware to understand the relationship between combinatorial and sequential circuits. State is modelled/captured via flip-flops and forms the basis of modeling “memory” which then are building blocks for sequential circuits. State models also form the basis of a variety of automated proof techniques and verification tools. Further, embedded systems in a variety of devices (consumer and others) rely on an underlying state model to coordinate interaction with the outside world and react appropriately to a variety of stimulii.
2. State models in Programming and Software tools in different subfields of computer science:
a) Parsers/Programming languages/Compilers – Grammars are modelled as finite state machines, compilers rely on state models to perform optimizations, recursion depends on maintaining state with a stack management rule.
b) Networking/Protocols/TCP-IP stack, queuing networks, routing protocols – Networking protocols are based on state models to manage interactions across each layer of the networking stack. Lower level abstractions support higher level protocols. Basically two state models operate on either end of the physical connection managing the communication.
c)Databases – transactions, software transactional memory – Transactions in databases are a way of ensuring that the state of data in the DB correponds to things in the realworld. ACID properties ensure this correspondence. The recent development of STM (software transactional memory) extends this notion to managing memory access at the CPU level to coordinate multicore processing.
d) Workflow systems– Process models, sequencing and scheduling of distributed workflow tasks depends on the ability to capture and reason with state at different levels of abstraction – the workflow case level and at the systems level. The state may be modelled explicitly as in XML-based frameworks or as objects or other intermediary data models.
e) AI -The notion of “state” is fundamental to search and planning algorithms. State in planning is modelled in terms of logical first/second order predicates. Truth maintenance systems maintain world dynamics in terms of logical predicates. Rule-based systems use the notion of state to control different types of rule-chaining and detecting changes in the RETE network. Probabilistic planning and Markov decision processes use statistical models of state along with dynamic programming techniques to drive inferences. Bayesian networks and other graph based models also use state models to reason about conditional dependencies.
f) Speech modeling – Speech models depend on “sequential state” models at different levels of abstraction to transform low-level signals to phonemes to words. The state sequences and transitions may be modelled explicitly or learnt from data with
g) NLP – Natural language processing uses a variety of state models for understanding character/token/work sequences, information extraction and also for discourse modeling. Additionally state models (via n-grams and the like) form the basis of statistical computational linguistics.
h) Software quality tools – A number of error analysis and code verification tools use state models (with domain dependent or domain independent semantics) to reason about behavior of programs. Deadlock/Livelock detection tools use state models of “processes” to detect interactions and for reachability analysis.
i) Discrete control theory– Control of discrete event systems and their coordination depends on complex state models capturing both coordination and independent process logic.
k) Numerical computing and Graphics modeling – Basic techniques in numerical computing, including FFT and other signal processing computations use state models for accuracy detection and restart techniques, controlling divergence etc. In graphics (especially in games/animation etc), state models form the basis of scene logic and animation/interaction control.
l) Discrete event simulations/Event modeling – Discrete event simulations are used to model interactions in a wide variety of domains especially in design of factory systems, data transfer networks and others.
k) SOA (Service-oriented architectures) – Web services (including HTTP protocols/REST architectures ) and other related internet technologies depend on the decoupling of state. However, the plethora of technologies is oriented towards providing a consistent view of state across an application from different perspectives.
l) UI modeling and UI tools – User interaction and the GUI development frameworks deal with managing user state and application state at different levels of abstraction including application data and the GUI element states.
m) Programming – State models are fundamental to different programming paradigms and the different modeling languages associated with them. OO deals with defining an object and managing its state through time. UML modeling, activty charts, state charts (Harel) and other related variants deal with the issue of modeling state when multiple objects interact and we need to define how the system should behave when each maintains its independent state.
o) Distributed systems – State models are also fundamental to large-scale distributed systems (especially the Web infrastructure). They are used in modeling time via vector clocks, coordinating distributed algorithms, data/file synchronization and merging, distributed debugging, resource optimization and the like.
The above list is by no means comprehensive but is intended to illustrate the utility of this basic notion of state and its widespread applicability. However, this widespread usage lends itself to some key design considerations during systems development which I discuss below.
Discussion – What and why should I care about “state”
Hopefully, the above discussion illustrates the wide variety of notions of state that form the basis of modern computational systems. This situation leads to a number of key issues to consider while developing systems, which I briefly summarize below:
a) There are a number of “notations” for modeling state and dynamics of a system. They have different semantics and different levels of expressivity. Further, the “implementation details” can hide the complexity. For example, to model boolean values in logic gates, different types of “voltage” levels are used in integrated circuits depending on the underlying semiconductor technology. With multiple models in a system, it is important to understand the relationships between all these different models.
b) While modeling complex systems, it is important for the system designer to ensure that states and transitions amongst the different models line up properly with proper
interpretations. States in the different models need to be defined completely with proper semantics.
c) Incomplete modeling may lead to the issue of “missing states” and unknown behavior at different levels of abstraction. When one models a “state” in a system (especially an analog system), one is abstracting a number of analog states into one “discrete state”. This leads to the classic aliasing problem in which one cannot discriminate between states in a single bundle. Alternatively, increasing the granularity may lead to too many states without adding any real value. It is important to manage these two extremes effectively. Another related issue is how do we go between states when an intermediary state is not explicitly captured. Major disasters in modern systems have occurred because of these incompleteness in modeling. This problem is exacerbated when digital and analog systems are closely coupled such as in railway systems, traffic control etc.
d) When a software system is operational, it is important to realize that many state models exist concurrently at different levels of abstraction. As an engineer, one has to visualize/reason about the following: for each state/input combination, will the system stop? where does/or would the system get stuck? Will it reach/not reach a given state? Will the system be transitioned by extraneous stimulii (possibly as a random event)? What can happen and what are the potential failure modes that can destabilize the system? (there are many more issues that need to be resolved)
e) The notion of state and dynamics associated with it is quite simple and every one seems to understand the concepts. However, that is the real danger as we do not pay enough attention to the underlying semantics and the kinds of issues that may be engendered when a system is built.
f) As an alternative to state-based computing per se, functional programming focuses on minimizing the use of state only for modeling “real-world” changes and avoid
the number of “state” based errors in modern systems due to unwanted side-effects. However, this is a topic for a different discussion and users are referred to a programmatic world view in the conceptual underpinnings of Clojure.
g) Modeling “state” is fraught with problems and a key issue is to have captured “enough” of the state information to be able to reason effectively. Missing or implicit information or badly defined transition functions leads to different variations of the classic “AI Frame” problem. Issues include incomplete static, dynamic and temporal relationships between states and actors that cause transitions between states. Ensuring that the required behaviors of your system cope reasonably when you reach these boundaries is an essential part of the design.
What does this mean for “Software Engineering” and building software systems?
Once we realize and appreciate the complexity of “state modeling” for real-world systems, one can appreciate why software engineering in general is messy.
State modeling discussions during the requirements phase with different stakeholders leads to different (potentially inconsistent) state models. This is further compounded by state modeling during system analysis. Different groups with different tools, experts and perspectives lead to different state models, locally consistent and potentialy globally inconsistent. Given that there is no phase wherein all these inconsistencies are resolved or limitations explicitly identified, these propagate into the system design and coding phases. During this phase another group of participants in the cycle add their own nuances to the already complex model based on their previous experiences and training. Finally, the whole thing really shows up during testing where nearly 80% of errors in complex systems are due to different kinds of state modeling errors leading to erroneous behaviors. Unit level testing may not catch global inconsistencies and even integration testing may miss unless all the behaviors are tested (assuming that they were even captured in the first place!). These issues are now compounded with software-as-a-service,where it is unclear what are the “valid states” in a blackbox when accessing an API and how different API calls interact (REST or otherwise). Anyways that is a topic for another essay..
In conclusion, the key takeaway: As an architect/developer (in software or hardware), one needs to understand all these potential issues just related to state and it may help you avoid a whole range of issues from building, managing and operating a complex software system.