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:



Qualitative Research: Sampling

Purposive and Theoretical Sampling:

When identifying means for recording data, one must be wary in qualitative research to how they collect data as well, it can be via unstructured or semi-structured observations and interviews, documents, and visual materials (Creswell, 2014).  Purposeful sampling is to help select the (1) actors, (2) events, (3) setting, and (4) process that will best allow the researcher to get a firm grasp at understanding and addressing their central questions and sub-questions in their study.  Also, consider how many sites and participants there should be in the study (identifying your sample size).  The sample size can vary from 1-2 in narrative research, 3-10 in grounded theory, 20-30 for ethnographic studies, and 4-5 cases in case studies (Creswell, 2014).

However, you can reach data saturation (when the research stops the data collection because there exists no more new information that would reveal any other insights or properties addressing the question of the research) before any of these aforementioned numbers (Creswell, 2014). Theoretical sampling is theoretically bound around a concept, but this type of sampling touches more on this concept of data saturation.  Thus, when the researcher is trying to understand the data in order to help them define or understand their theory to the point of data saturation, rather than reaching a defined number.


An example of this could come from studying the effects of business decisions affecting the family through analyzing relocation decisions on non-military families. (PROCESS)  Purposefully I would like to sample in this example are three groups of families, ACTORS: those with no children, those with children that are no older than 12 years of age, and those with one or more children over the age of 13.  I want to see if there is a difference between the reactions based on having kids and having kids that are older versus younger, over the past decade (EVENT) at Boeing (SETTING).  I could aim for 20-30 families per group to a total of 60-90 sample size, or I could aim for data saturation between each of these groups (Theoretically sampling).  If I want to stick with 60-90 as a total sample size, I could aim for an open answer survey or conduct interviews (which is more costly on my end).  If I wish to aim for data saturation, it can be more easily done with interviews.


Parallel Programming: Logical Clocks

In a distributed system nodes can talk (cooperate) to each other and coordinate their systems.  However, the different nodes can execute concurrently, there is no global clock in which all nodes function on, and some of these nodes can fail independently (Sandén, 2011).  Since nodes talk to each other, we must study them as they interact with each other.  Thus, a need to use logical clocks (because we don’t have global clocks) which show that distances in time are lost (Sandén, 2011). In logical clocks: all nodes agree on an order of events, partially (where something can happen before another event).  They only describe the order of events, not with respect to time.  If nodes are completely disjoint in a logical clock, then a node can fail independently. This is one way to visualize the complex nature of nodes.

The following is an example of a logical clock: