Inverting Finite State Machines (FSM)

Summary

This page focus on

a very simple form of specify transitions for an FSM
the ability to Invert a (server) FSM to get a (client) FSM interacting with each other
elaborate examples (poor Bob and his rich aunt Alice, DHCP server, rebuffering and your own? FSM in a set of interactive Usecases

Introduction to FSM and inverting

The FSM is a very established form of specification and implementation of technical solutions for hardware and software especially in the state full environments.

This page will focus on a new aspect: How to generate FSM peers. Or partners. Or complements. Or mirrors. Or inverters. Or conjugates. To my knowledge there is not any names for one FSM talking to another which is a formally inherited FSM.

Kass

Background

If a protocol, a speech act, is specified using FSM for the behavior of one part then, of course, the other part could also use an FSM to describe its behavior. And then came the idea up if it was possible to use the formal FSM for the server to create an inverted FSM for the client. You get two talkative FSM's from one FSM specification!

This mechanism how to programmatically create an inverted FSM to "main" FSM is the very issue on this site

Purpose

This page walk you through what's required to invert an FSM and there is also an we page with Usecases Fore more background on FSM look into Wikipedia or similar sources.

Examples of FSM usage

Tullverket
DHCP
TCPIP
zip
Sequence usage
User Interactions

Definitions for the FSM

We need to make some definition. Most of them are classic

FSM: A set of Transitions
Transition: A set of element telling 'In State receiving an Event an proceesing a GuardFunction giving the GuarValue will produce an Ouput and change State to a new state.
Example: STATE14, EVENT23, GUARDVALUE3, OUTPUT9, STATE12
State: Traditional. Public name in order to understand the FSM.
Event: Data sent to FSM. Public name and long living.
GuardFunction: Function to be called when an FSM got an Event in a State. Must return a GuardValue out of a predefined set of values.
GuardValue: Rteurnvalue from a GuardFunction.
Output: Data sent from an FSM. Public name and long living.
PreProcess: Will decode a raw in event to proper a public Event.
PostProcess: Will encode a public Output to raw output
Server: In this context the root specification of an FSM
Client: In the context the result of Inverting a Server FSM
callin: The possibility for functions to feed_Event_ with to an FSM
nooutput: In this context an Output telling that the FSM should not produce any Output
anyevent: In this context an Event telling that the FSM should bypass this event.
Message wait time out
Session service time out

Specifications

One need language to specify a protocol. It must also be possible to verify a solution towards a specification. And that must be declarative as much as possible and contained in one manageable source.

I prefer to use the first normal form like the CSV format. Both early in the process but also as a robust - but not always sufficient documentation

CSV

JSON

SDL

UML

A minimal example could look like as CSV

    State, Event,      NextEvent
    ----------------------------
    Init,  FirstEvent, Wait4
    Wait4, StopEvent,  Final
    Wait4, Work,       Wait4
    Final, anyevent,   Final

Visualizations

There are a lot of ways to visualize an FSM. But why must it bee pleasant for the eye? I think that by emulating a use case towards a running FSM you can decide whether it will conform to the desired function. There are several profession involved in communication and they have different demands during the development and support. It is important to be able to utilize just one source for each visual drawing.

-tty cvs source json?

out matrix of different kind also generic

Implementation

Here we focus on proper and correct specification and behavior but leaving most aspects on implementation in different run time environment like threading, asynch, synch

Extending a bit

Guard

First we extend our specification. We must have the possibility to check events and make some decision like what do answer when a certain resource is fully utilized like the amount of available IP addresses in a DCHP server etc. This mechanism is called guard in UML and many other domains

Here we introduce guard as a function to be called and giving a result back to the machine. Depending on the outcome the machine rolls on

    State Event      GuardResult     NextEvent
    ------------------------------------------
    Init  FirstEvent Full            Final
    Init  FirstEvent NotFull         Wait4
    Wait4 StopEvent  OK              Final
    Wait4 StopEvent  BuffersNotEmpty Wait4
    Wait4 Work       AlWaysOk        Wait4
    Final anyevent   OK              Final

Output

This page is about Speech Acts so the FSM must listen on Event and talk through Output. So we add another (Output) column like following

    State Event      GuardResult     Output    NextEvent
    ----------------------------------------------------
    Init  FirstEvent Full            FULL      Final
    Init  FirstEvent NotFull         OK        Wait4
    Wait4 StopEvent  OK              OK        Final
    Wait4 StopEvent  BuffersNotEmpty NotEmpty  Wait4
    Wait4 Work       AlWaysOk        OK        Wait4
    Final anyevent   OK              nooutput  Final

The Output value can be 'nooutput'. This is required when we have a communication which is not of ping-pong kind but when one peer will send a set of messages before getting an answer from the other peer.

Timers

FSM are often used in communication system where components are sharing external resources. An invocation is often not a single call path in the cpu. Therefore responses might be delayed. However one want's to restrict the delay time. But also limit the usage of certain resources for a certain time

Message timers are short timers typically a few seconds or less. They are started when one event is sent and you await an answer very soon. If the timers bell you must take a proper action. If you got an answer before time out don't forge to shut down the timer
Session timers are long timers like for hours limit allocation time or similar. They are started when you got the allocation of a resource for a limit time. At the time out you are allowed to use the the resource any more
It must be possible to specify such timers in a proper way in the specification Time out event should be treated as e certain type of event. It must obvious in the specification when to start short and long timers. The killing of timers are calculable and no manual operations are required.

Local event injection

In order to get something done then the client FSM has a user or program must invoking it. It is not a closed box. Than it's meaningless. So we must be able to specify external call-in.

Initial State

Final State

Client reduction and Usecase

The inverting process

This function will take an existing (server) FSM and produce a new (client) FSM which will be able to communicate with the (server) FSM. Why specify the server FSM as a base? That is because a server must be able to service all scenarios but a client might use a subset scenarios.

The use of inverted might not be the most obvious. Perhaps complement, mirror, conjugate, peer, opposite, match could be used. It is all about conversation machine-machine following rules.

Steps

Ensure there is one initial state in the FSM. That is one state which will never be reached through a transition. (That state is not in the nextstate column).
Ensure there is one final state in the FSM. That state has no transitions to another state but only to itself. It will probably accept transitions with any events.
Specify the FSM through a set of rows each containing
```
State,Event,GuardResult,Output,NextEvent
```
Paste this specification into XXX and hit the Invert button