How to recover from finite-state-machine breakdown?

Question

My question may seems very scientific but I think it's a common problem and seasoned developers and programmers hopefully will have some advice to avoid the problem I mention in title. Btw., what I describe bellow is a real problem I am trying to proactively solve in my iOS project, I want to avoid it at all cost.

By finite state machine I mean this > I have a UI with a few buttons, several session states relevant to that UI and what this UI represents, I have some data which values are partly displayed in the UI, I receive and handle some external triggers (represented by callbacks from sensors). I made state diagrams to better map the relevant scenarios that are desirable and alowable in that UI and application. As I slowly implement the code, the app starts to behave more and more like it should. However, I am not very confident that it is robust enough. My doubts come from watching my own thinking and implementation process as it goes. I was confident that I had everything covered, but it was enough to make a few brute tests in the UI and I quickly realized that there are still gaps in the behavior ..I patched them. However, as each component depends and behaves based on input from some other component, a certain input from user or some external source trigers a chain of events, state changes..etc. I have several components and each behave like this Trigger received on input -> trigger and its sender analyzed -> output something (a message, a state change) based on analysis

The problem is, this is not completely selfcontained, and my components (a database item, a session state, some button's state)...COULD be changed, influenced, deleted, or otherwise modified, outside the scope of the event-chain or desirable scenario. (phone crashes, battery is empty phone turn of suddenly) This will introduce a nonvalid situation into the system, from which the system potentially COULD NOT BE ABLE to recover. I see this (althought people do not realize this is the problem) in many of my competitors apps that are on apple store, customers write things like this> "I added three documents, and after going there and there, i cannot open them, even if a see them." or "I recorded videos everyday, but after recording a too log video, I cannot turn of captions on them.., and the button for captions doesn't work"..

These are just shortened examples, customers often describe it in more detail..from the descriptions and behavior described in them, I assume that the particular app has a FSM breakdown.

So the ultimate question is how can I avoid this, and how to protect the system from blocking itself?

EDIT> I am talking in the context of one viewcontroller's view on the phone, I mean one part of the application. I Understand the MVC pattern, I have separate modules for distinct functionality..everything I describe is relevant to one canvas on the UI.

Answer 1

I am sure you already know this but just in case:

1. Make sure every node in the state diagram has an outgoing arc for EVERY legal kind of input (or divide the inputs into classes, with one outbound arc for each class of input).

   Every example I have seen of a state machine uses only one outbound arc for ANY erroneous input.

   If there is no definite answer as to what an input will do every time, it is either an error condition, or there is another input that is missing (that should consistently result an arc for the inputs going to a new node).

   If a node doesn't have an arc for one type of input, then that is an assumption the input will never occur in real life (this is a potential error condition that would not be handled by the state machine).

2. Make sure the state machine can only take or follow only ONE arc in response to the input received (not more than one arc).

   If there are different kinds of error scenarios, or kinds of inputs that cannot be identified at state machine design time, the error scenarios and unknown inputs should arc to a state with a completely separate path separate from the "normal arcs".

   I.E. if an error or unknown is received in any "known" state, then the arcs followed as a result of the error-handling/unknown input should Not go back into any states the machine would be in if it only received known inputs.

3. Once you reach a terminal (end) state you shouldn't be able to return to a non-terminal only to the one starting (initial) state.

4. For one state machine there should not be more than one starting or initial state (based on the examples I've seen).

5. Based on what I have seen one state machine can only represent the state of one problem or scenario.
   There should never be multiple possible states at one time in one state diagram.
   If I see the potential for multiple concurrent states this tells me I need to split the state diagram up into 2 or more separate state machines that have the potential each state to be independently modified.

Answer 2

The point of a finite state machine is that it has explicit rules for everything that can happen in a state. That's why it is finite.

For instance:

if a:
  print a
elif b:
  print b

Is not finite, because we could get input c. This:

if a:
  print a
elif b:
  print b
else:
  print error

is finite, because all possible input is accounted for. This accounts for the possible inputs to a state, which may be separate from error checking. Imagine a state machine with the following states:

No money state. 
Not enough money state.
Pick soda state.

Within the defined states, all possible inputs are handled for money inserted and soda selected. Power failure is outside the state machine, and "does not exist". A state machine can only handle inputs for states that it has, so you have two choices.

1. Guarantee that everything action is atomic. The machine can have total power loss and still leave everything in a stable, correct state.
2. Extend your states to include unknown problem, and have errors kick you to this state, where issues are handled.

For reference, the wiki article on state machines is thorough. I also suggest Code Complete, for the chapters on building stable, dependable software.

Answer 3

Regular expressions are implemented as finite state machines. The transition table generated by the library code will have a failure state built in, to handle what happens if input does not match the pattern. There's at least an implicit transition to the failure state from almost every other state.

Programming language grammars are not FSMs, but the parser generators (like Yacc or bison) generally have a way to put in one or more error states, so that unexpected inputs can cause the generated code to end up in an error state.

Sounds like your FSM needs an error state or a failure state or the moral equivalent, along with both explicit (for cases you anticipate) and implicit (for cases you don't anticipate) transitions to one of the failure or error states.

Answer 4

The best way to avoid this is Automated Testing.

The only way to have real confidence about what your code does based on certain inputs is to test them. You can click around in your application and try to do things incorrectly, but that does not scale well to ensure you don't have any regressions. Instead, you can create a test that passes bad input into a component of your code and ensures that it handles it in a sane way.

This will not be able prove that the state machine can never be broken, but it will tell you that many of the common cases are handled correctly and don't break other things.

Answer 5

what you are looking for is exception handling. A design philosophy to avoid staying in an inconsistant state is documented as the way of the samurai: return victorious or do not return. In other words: a component should check all its inputs and make sure that it will be able to process them normally. It it is not the case, it should raise an exception containing useful information.

Once an exception is raised, it bubbles up the stack. You should define an error handling layer which will know what to do. If a user file is corrupted, explain to your client that the data is lost, and recreate a clean empty file.

The important part here is to get back to a working state, and avoid error propagation. When you are done with this, you can work on individual components to make them more robust.

I am not an objective-c expert, but this page should be a good starting point:

http://developer.apple.com/library/ios/#documentation/cocoa/conceptual/objectivec/Chapters/ocExceptionHandling.html

Answer 6

Forget your finite-state-machine. What you have here is a serious multi-threading situation. Any button can be pressed at any time and your external triggers could go off at any time. The buttons are probably all on one thread, but a trigger could litterally go off at the same instant as one of the buttons or one, many, or all of the other triggers.

What you must do is determine your state at the moment you decide to act. Get all the buttons and trigger states. Save them in local variables. The original values may change every time you look at them. Then act on the situation as you have it. It is a snapshot of how the system looked at one point. A millisecond later it could look very different, but with multi-threading there is no real current "now" that you can hang on to, only a picture you have saved in local variables.

Then you have to respond to your saved--historical--state. Everything is fixed and you ought to have an action for all possible states. It will not take into account changes made between the time you took the snapshot and the time you display your results, but that's life in the multi-threading world. And you may need to use synchronization to keep your snapshot from being too blurred. (You cannot be up-to-date, but you can come close to getting your entire state from one particular instant in time.)

Read up on multi-threading. You have a lot to learn. And because of those triggers, I don't think you can use a lot of the tricks often provided to make parallel processing easy ("Worker Threads" and such). You are not doing "parallel processing"; you are not trying to use 75% of 8 cores. You're using 1% of the entire CPU, but you have highly independent, highly interacting threads, and it will need a lot of thought to synchronize them and keep the synchronizing from locking up the system.

Test on both single core and multi-core machines; I've found they behave rather differently with multi-threading. The single-core machines turn up fewer multi-threading bugs, but those bugs are far more weird. (Though the multi-core machines will boggle your mind till you get used to them.)

One last unpleasant thought: this is not easy stuff to test. You'll need to generate random triggers and button presses and let the system run flat out for a while to see what turns up. Multi-threaded code is not deterministic. Something can fail once in a billion runs, just because the timing was off for a nanosecond. Put in debug statements (with careful if-statements to avoid 999,999,999 unneeded messages) and you need to make a billion runs just to get one useful message. Fortunately, machines are real fast these days.

Sorry to dump all this on you this early in your career. Hopefully someone will come up with another answer with a way around all this (I think there's stuff out there that might tame the triggers, but you've still got the trigger/button conflict). If so, this answer will at least let you know what you're missing. Good luck.