Tag: state diagram

Parallel Programming: State Diagram Example

Capture

  • Enter into state S0 into the superstate S1 through event 1 and yields action a1.
  • When entering into superstate S1, we must go through state S12, with action a7 to enter and action a3 to exit.
    • If action a3 yields an event e9, which yielded action a9, we enter into state S13, causing action a6 and action a12 to exit.
      • If action a12 yields an event e5, we will get action a5 and we hit the superstate S1 and begin again to state S2.
      • If action a12 yields an event e9, we will use action a1 an enter state S112 (under the S11 superstate) with an entry of an action a11.
        • Event e2 acts on S112, to get action 2 which enters the superstate S11.
          • Entering into the superstate through state S112 we get an exit criterion of action a14 and we end.
          • If exiting state S112 we do event e1 and action a1 we are sent back to state S12 to start again.
          • If we exit state S112 we do event e3 and action a3 which is used to enter into state S1 follow 1.a.
    • If action a3 in state S12 yields event e4 and action a4, we enter the superstate S11. Entering super state S11 this way we enter into state S111 with an entry action of a8.
      • We then carry out event e9 and action a1 to get to state S112. If this happens follow 1.a.i.2.

Parallel Programming: State diagram of Maekawa’s voting algorithm

Sandén (2011) defines state diagrams as a way to show the possible states an object could be on.  He also defines, that events are action verbs that occur on an arrow between two events (if an action doesn’t change the state it can be listed in the state).  Whereas an action can have conditions on them.

Thus, a state diagram shows the transition from state to state as events occur.  An event usually has many occurrences, and they are instantaneous.  Finally, a super-state can encompass multiple states (Sandén, 2011).  An activity is an operation that takes time, and it has the keyword “do /”

The goal of this post was to make a state diagram of Maekawa’s voting algorithm on the “Maekawa’s algorithm” within the “Distributed mutual exclusion” set. This can be done in various ways. One option is the following 5 states:

  • Released and not voted
  • Released and voted
  • Wanted and not voted
  • Wanted and voted
  • Held and voted (for self)

Events are:

  • request_received, etc., for messages arriving from other nodes
  • acquire for when the local node wants the lock
  • release for when the local node gives up the lock.

A possible solution is shown below:

statediagram

Reference