Solution to F2001 hw2

 

Exercise 1. Reachability Analysis

Given the following network of two CFSMs.

Questions:

  1. Perform the reachability analysis on the Network (M, N).
    Ans: Figure 1 shows the reachability graph generated by the reachability analysis on the Network (M,N). It contains 19 global states. Gs15 indicates there is an unspecified reception state.
  2. What sizes of buffers are needed for the two FIFO channels?
    Ans: From gs17, a buffer size of 2 is needed for channel  from Machine M to Machine N. From gs18, a buffer size of 2 is needed for channel from Machine N to Machine M.
  3. Are there non-executable states or transitions?
    Ans: For Machine M, state 7 is a non-executable state and transitions (4, 7, +A) and (7,1,-D) are non-executable transitions.
    For Machine N, there is no non-executable state and transition (7,1,+D) is a non-executable transition.

Exercise 2. Understand the protocol behavior of Alternating Bit Protocol.

Given the alternating bit protocol,

Describe the event sequence, starting from initial states, of the alternating bit protocol, if channel C2 loses the even messages, i.e., it loses the 2nd, 4th, 6th,... messages. Each event can be identified as starting global state--machine:transition->ending global state. For example, (1,1,E,E)--S:NewData-->(2,1,E,E) is the first event.  Include events up to the one that successfully delivers A1 to the Sender.

Ans:         The event sequence is as follows:

            (1, 1, E, E)—S :NewDataà(2, 1, E, E)

(2, 1, E, E)—S :-D0à(3, 1, D0, E)

            (3, 1, D0, E)—R :+D0à(3, 2, E, E)

            (3, 2, E, E)—R :Deliver Dataà(3, 3, E, E)

            (3, 3, E, E)—R: -A0à(3, 4, E, A0)

            (3, 4, E, A0)—S :+A0à(4, 4, E, E)

            (4, 4, E, E)—S :New Dataà(5, 4, E, E)

            (5, 4, E, E)—S :-D1à(6, 4, D1, E)

            (6, 4, D1, E)—R :+D1à(6, 5, E, E)

            (6, 5, E, E)—R :Deliver Dataà(6, 6, E, E)

            (6, 6, E, E)—R :-A1à(6, 1, E, A1)

            (6, 1, E, A1)—C2 :Lose 2nd msg A1à(6, 1, E, E)

            (6, 1, E, E)—S :Toà(8, 1, E, E)

            (8, 1, E, E)—S :-D1à(6, 1, D1, E)

            (6, 1, D1, E)—R :+D1à(6, 8, E, E)

            (6, 8, E, E)—R :-A1à(6, 1, E, A1)

            (6, 1, E, A1)—S :+A1à(1, 1, E, E)