Exercise 2 --- ELG 7187C --- Fall 2003
(Oct. 6, 2003, due date October 20)
Exercise 2.1:
We consider the alternating bit protocol as described in [Bochmann 78]
(see copied course notes). Your task is to define a Petri net which represents
the "alternating bit protocol system", that is the sender user, the sender
protocol entity, the communicatin medium, the receiver protocol entity and
the receiving user (all as one Petri net). In order to reduce the number of
Petri net places required, you should use the formalism of coloured Petri
nets with predicates to describe this system. This means that each transition
of your Petri net should deal with the two possible values of the alternating
bit (if the bit is relevant for that transition), similar to the specification
in the form of an extended finite state machine shown
here
(taken from [Bochmann 77]) which means that the Sender entity, for instance,
has only 3 states instead of 6. Please also give a short explanation of your
Petri net design.
To get you inspired how a protocol entity may be described in terms of
a Petri net, the following diagram shows en entity that receives m1 messages
from the place P1, sends the received messages to the user at Place P3 and
at the same time remembers that one message was received (adding a token
to Place P5). Transition T2, then, sends a message m2 to the place P2; this
message includes as parameter the number of messages received (minus one).
This number is stored as a token in Place P4.
Exercise 2.2:
We consider the protocol defined by the following diagram which contains
two state machines for two protocols, respectively. You may think of telephone
call establishment. On the left is the caller and right is the callee. R means
ready, C means connected, Req means call request, Inc means incoming call
notification, and Term means termination of the call.
In this exercise, we propose to interpret these two diagrams in three different
manners:
- As two LTS that communicate by rendezvous for the three interactions
Req, Int and Term (that means, we ignore the + and - signs): Please consider
the composition of these two machines and indicate its behavior (in the form
of a single LTS), that means, do a reachability analysis (do you detect any
design error ? ) .
- As two IOA that communicate by rendezvous for the three interactions
Req, Int and Term (Req and Term are output for the first IOA and input for
the other, and inversely for Inc): Please consider the composition of
these two machines and indicate its behavior (in the form of a single state
machine), that means, do a reachability analysis (do you detect any design
error ? ) .
- As two communicating finite state machines that communicate by
message passing with one another: Please consider the composition of
these two machines and indicate its behavior (in the form of a single transition
diagram), that means, do a reachability analysis (do you detect any design
error ? ) .
Modification (introduced Oct. 16):
Please consider for points 1 and 2 above a slightly modified specification
for the left component. The modified specification has an additional "- Term"
transition from state C back to state C. Note: This modified component is
non-deterministic.