State Machines

Oct 30, 2020

This and the next post are the longest posts of our Distributed Systems series. The first one about Computation and Mathematics was the shortest. We plan to stabilize somewhere in between as we progress. This post also touches almost all the other topics we will yet properly explain in future posts.

State Machines and especially the notion of state is the central and most important concept in all of computing. Maybe even in the universe. Without state and changes in state, there is no past, present or future. Nothing ever happens. The present is encoded in "the current state of the world". The world 🌐 can mean either our entire planet or anything else that can be understood as a well defined, mathematically observable (sub)system. We don't understand our planet as a computing system because emergence and complex systems theory prevent us from ever really understanding each detail of the system in realtime as it is happening. We can understand simpler, isolated parts of state though, individual parts of our (computing) universe. Please read the post about Computation and Mathematics to see what is meant by computation (as opposed to calculation).

Read this post slowly, with careful thought if you never had the chance to learn how computers are able to be interesting and useful to us while only doing simple operations on bits.


Finite State Machines

Machine in this context means an abstract computing concept, not an actual physical machine.

Finite State Machines are the simplest possible model of computation.

Please note that "abstract" is written as opposed to concrete or physical and not as opposed to fuzzy or undefined. Abstract in this case means mathematical and very exact.

State Machines are usually represented as diagrams:

This is a door represented with a state machine model. Circles are states and arrows are transitions between states when certain actions are executed.

State Machines model the behaviour of the system.

A door can only be in one of the states (Locked, Unlocked or Opened) at any given time. Direct transition between some states (for example between Locked and Opened) are impossible. We have a finite number of states β€” 3.

Each state transition takes some time. We can never open the door in 0.0 seconds.


Our exploration plan:

  • 1st half: philosophical but still realistic, present a few non-everyday viewpoints that should stimulate thinking.
  • 2nd half: exact mathematical theory and definition of Finite State Machines. No room for poetic interpretation here. We will leave this to verified others though. We will curate all links and make sure they contain only information of the highest quality possible on this important subject. You can then invest a few days, a few months or a few years into further exploration down this road πŸ›£οΈ. I certainly will 🐰.

Let's now start with the first half and take a bit of a curious look at the concept of state at the lowest possible level we can.

John Bardeen, Walter Brattain and William Shockley won the 1956 Nobel Prize for physics for their work on the transistor.

What is state? πŸ€”

What could be the shortest possible definition to cover all kinds of states no matter from which perspective we are looking? We go with this definition:

State is the proto-basic unit of information.

For example each bit has 2 states. State is thus a lower-level concept than bit. Β 

From 1948 paper by Claude Shannon:

If the base 2 is used the resulting units may be called binary digits, or more briefly bits, a word suggested by J. W. Tukey. A device with two stable positions, such as a relay or a flip-flop circuit, can store one bit of information.
Claude Shannon, the Father of the Information Age

Notice the concept of two stable positions (≑ states). Also notice the term flip-flop circuit. Flip-flop circuit is a digital circuit that traps (saves) state. We give it electronic input (set or reset) and it remembers it. It does so by circulating the current and staying in perpetuum in that metastable state until we manually change it by giving it the opposite input. This is the hardest diagram in this post but it is still possible to exactly understand it with some effort. It is not crucial that you do though, what follows can also be understand in entirety even if basic mechanics of this very interesting little device at the center of computing is not entirely understood. You will understand the outside behaviour of a flip-flop device after continuing the read for sure.

Bistable multivibrator circuit - we choose the output (H or L) with set and reset buttons
Bistable multivibrator, in which the circuit is stable in either state. It can be flipped from one state to the other by an external trigger pulse. This circuit is also known as a flip-flop. It can store one bit of information, and is widely used in digital logic and computer memory.

Interactive animation where you can try switching between two states is here. The important elements are two transistors. Transistor is a miniature component that conducts current between its two contacts β€” collector and emitter if there is a small current present at a third input contact called base.

Transistor, the basic building block of classical computers

⚠️ We usually mark the electrical current (I) as flowing from [+] to [-] (red arrow). This is actually wrong because electrons flow in the reverse direction (blue arrow).

Such convention was established before actual facts were fully known. It is not important for undertanding basic circuits but it is worth knowing. Electrons have negative charge [-] and are attracted to the positive [+] electrode. The basic symbol for transistor in the entire human literature has the arrow pointing in the wrong direction :) Once something is widely used it is very hard to change.

Transistors can do two things:

  • amplify the current (for example when you speak in the microphone and the speaker makes your voice louder)
  • act as little switches as in flip-flop circuit. Main purpose is not to amplify the signal but to use it as a trigger for turning something on and off. This is how we physically transition from continuous currents in physics to our discrete systems with well defined separate states. Another name for this is digital logic.

It is interesting to notice that a flip-flop circuit is itself conceptually a state machine!

Flip-flop circuit represented as a state machine

As we see, 'zero' and 'one' (or 'high' and 'low') are just names for states, computers don't actually operate in 'zeros' or 'ones' as usual natural numbers.

Emergence of symbolic meaning

Information emerges out of the distinction between states and out of the assigned meaning of what these distrinct states represent.

We can represent two states with one bit, 4 states with 2 bits, 8 states with 3 bits etc.

Representing 4 different states with 2 bits.

With 3 bits in each box we could represent these 8 distinct states: 000, 001, 010, 011, 100, 101, 110, 111. For each additional bit we add, we get twice as many possible state as before (jump from 4 to 8 states between 2 and 3 bits)! General formula for this is:

\[ n_{states} = 2^{n_{bits}} \]

This is exponential growth of \( n_{states} \) because \( n_{bits} \) is in the exponent of the equation.

Early computers grouped 8 bits together and this is still called a byte. 1 byte (= 8 bits) can store \( 2^8=256 \) different combinations (states). This was enough for basic symbols like all normal letters A-Z, all digits 0-1 and a few other symbols. This is called an ASCII table and it proved a bit limiting over time. Modern computers now take 32 or even 64 bits as a basic unit for general computation instead of just 8. Modern UTF-8 symbol encoding standard uses up to 4 bytes (32 bits) for each symbol representation.

Symbolic barrier

This is how symbols emerge out of tiny electric gates! These symbols don't have any meaning without a human observer. We show potentially meaningful state representation on a computer screen and this is how symbols (or User Interfaces in general) cross into our 🧠 wetware where they finally mean something. At almost any point in the state processing hiearchy we can have something that we consider state with some kind of symbolic meaning. This is a bit arbitrary and decisions about how to go about it can make or break a potentially good software design.

Performance and stability oriented computer programmers (especially those working with distributed systems) have to be exactly aware of how state is stored and manipulated while end users don't have to know almost anything about it. They usually notice a bad design immediately but they don't realize it is very likely related to state mismanagement at some level of the program computation.

Distributed systems are notoriously hard exactly because making sure various copies of our state are always consistent with each other. We can either get different versions of state and cannot be sure which is right or we can corrupt our state by accident so it doesn't represent reality anymore. With fast systems where messages arrive quickly (sometimes nanoseconds) between each other we have to be sure to apply them in the right order or we can get a wrong final state. It is not always possible to know what order is correct because nature does not keep an absolute and objective clock. Each processing unit is working with its respective relative time ticking. This is a subject more appropriate for next week (a general post about distributed systems).

Let's go back to the main topic of this post now.

Program state

To quote the Turing Award winner Leslie Lamport again:

I believe that the best way to get better programs is to teach programmers how to think better. Thinking is not the ability to manipulate language; it’s the ability to manipulate concepts. Computer science should be about concepts, not languages.

Manipulation of state (eg. DATA STRUCTURES, with or without explicit State Machines) is the fundamental concept of Computer Science and will make you think about programming in a tremendeously more structured way than just thinking about if / else statements and for loops.

Consider this representation of information:

{
  "currentSong": "Van Morrison - Alan Watts Blues",
  "status": "playing"
}

If we save this somewhere, we can consider this json document as our representation of state. It gives us information about the media player and this information is represented exactly by this document which can be easily converted into a string of letters. Computers know exactly how to save strings into memory or hard drive. This is the same as bits which are also saved and represent state. Here we have a document that also represents state and information emerges somewhere between that document inside the computer and our interpretation and confirmation of its effect (song actually playing).

If state which is saved in the computer is not synchronized with its actual meaning (for example a different song playing), then the entire theory of deterministic state manipulation and interpretation fails and we don't have a working computing system. We have to always take care that our state machines are in check with reality.

Machine has to perfectly and reliably execute its behaviour according to inputs presented, never making a mistake. If mistakes are made because of physical reality, they have to be immediately recognized and mitigated. We also have to know when we are not able to know if a mistake has been made.

Another curious example of state machines

Blockchains are also an example of a computing system that is best thought of as a State Machine albeit with some interesting additional security properties (prevention of undesired state modifications while operating permissionlessly as an open protocol). Distributed security (consensus) protocol is not directly part of state machine so we can forget about it for now (until our installment about Blockchains in a few weeks).

We can think of a blockchain as a repository of various states (for regular account balances as well as for each smart contract). We can name the sum of all these states simply as "Blockchain state".

A high level overview of a blockchain as state machine

At each block (usually every few seconds) blockchain accepts valid pending transactions and bakes them immutably into this particular block. We always get to the end (current) state of the blockchain by applying all state transitions in each block following the genesis (zeroth block) one after the other... All state transitions from beginning give us the end state. Blockchain stores the entire history (state transitions) but we are usually only interested in the end state. We need the history to be sure that our end state is valid and that there were never invalid or fake transitions involved.

What are the blockchain transactions actually? Each transaction can either move some balance between a pair of accounts or it can execute more complex computation inside some smart contract. Both of these are instances of valid state transitions.

[short comment --> some of this will probably be moved into a separate post about Blockchains because it got a bit too long]


Computing appears like magic but it's just fast state transitions

Computers somehow manage to appear 'in touch with us' although all they do is manipulate electric currents to quickly turn billions of little digital switches on and off.

We sometimes manage to continually put computers in correct state to reflect our own thoughts, organize our ideas and make interpersonal communication easier.

They are actually our mirrors and how we behave is reflected and emphasized back to us through our globally interconnected information amplifiers. Before 2000 it was mostly one to one relationship with our digital state manipulators but since then and especially after 2020 we are starting to see a few unified global state machines emerging which will increasingly hold all our important state information and secure our digitall-mirrored real life relationships with one another.

Quantum state

Here things get weird and this is the current edge of research. The goal is to save state not in "giant flip-flop circuits" (in relative terms) but to save state directly in elementary particles! Many orders of magnitude smaller building blocks for this kind of computation. Small size is not the only difference. At this scale we bump into physics laws we are not really familiar with in our every day lives and don't have any intuitive notion about them. Quantum computing is weird but so was our current computing roughly 70 years ago.

Qubit - Wikipedia
Quantum state - Wikipedia

Quantum computers (if possible in practice) will once again change our entire worldview within less than one generation.

Perhaps an 🐠 exploratory learning course in quantum computing is coming this time next year. A promise given to oneself is only good if fulfilled. Promising others makes fulfilment more likely because what we openly promise should hurt us in same way in case of non-delivery. This was a self-made unprovoked promise but it is still a promise :) If not next, then one of the coming years for sure.

Second part

As promised, here are some of the greatest resources on State Machines and Statecharts:

Finite-state machine - Wikipedia
Theory of Computation & Automata Theory
Theory of Computation is one of the most fundamental as well as abstract courses of Computer Science. It is a branch in theoretical Computer Science that dea...

Expansion of the concept of State Machines:

Statecharts: a visual formalism for complex systems
We present a broad extension of the conventional formalism of state machines and state diagrams, that is relevant to the specification and design of c…
Welcome to the world of Statecharts
The world of statecharts describes what statecharts are, their benefits and drawbacks, how they differ from state machines, and practical examples on how to use them.

Library implementing standard compliant State Machines and Statecharts:

https://xstate.js.org

Read the docs! Lots of great resources, video tutorials and other great useful information in there.

For even more resources in this area please consider using the ZetaSeek re/search engine. The engine is powered by Connectome library.

And have a great week! πŸ‘

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.