CS2310 Quiz 1 (Feb 6, 2020, Thursday, 4pm to 4:45pm, 349 CL)

Name: _______________________

(1) An on-line bookstore has a web site which can interact with other on-line bookstores' web sites. Let us say we have three bookstores' web sites B1, B2 and B3. A customer can browse the web page B1 and select a book. A message is sent to other bookstores B1, B2 and B3, which respond if they carry the book and the price. Notice the message is also sent to B1 itself, so that it can respond. Upon reception of the messages from B1, B2 and B3, or after the expiration of certain time T (because perhaps not all bookstores will respond in time), the least expensive book is selected, and a message is sent to that bookstore to reserve the book. A bookstore, upon reception of a reservation, will put that book on hold for the customer, and send back to the originating bookstore an acknowledgement message. At this time, the resulting book is displayed on the web page of B1 for the customer to purchase. This protocol could go on but we will stop here for simplicity.

(1a) @(1 point) Draw state-transition diagram to define graphically the index cell type associated with the electronic bookstores' web page.

(1b) @(1 point) Specify this index cell type formally using mathematical notations ic = (X, Y, S, so, A, tmax, f, g).

(1c) @(1 point) Draw a diagram showing B1, B2 and B3 enhanced with the index cells to illustrate how these index cells work together to form an active index system.

```ANS: (1)
ANS:   --m1/m2:a4--
ANS:   |          |
ANS:   |<----------
ANS:   |
ANS:   S0--m0/m1:a4-->S1--m2,m3/m4:a1-->S2--m5/:a3--> S4
ANS:   |                                |             ^
ANS:   |                              m4/m5:a2        |
ANS:   |                                |             |
ANS:   |                                V             |
ANS:   ----------m4/m5:a2-------------->S3------a3-----
ANS:
ANS: S0: Initial state
ANS: S1: Query Price State
ANS: S2: Book Reservation State
ANS: S3: Book Reserved State
ANS: S4: Display Reservation State
ANS: m0: A book is selected by a customer
ANS: m1: A query on book price
ANS: m2: Book price query result
ANS: m3: Book query timeout
ANS: m4: A request to reserve a book
ANS: m5: A response to reserve a book
ANS: a1: Find the book with the minimum price
ANS: a2: Reserve a local book
ANS: a3: Display a reserved book
ANS: a4: Query local book price
ANS:
ANS: X = { m0, m1, m2, m3, m4, m5 }
ANS: Y = { m1, m2, m4, m5 }
ANS: S = { S0, S1, S2, S3, S4 }
ANS: S0 = S0
ANS: A = { a1, a2, a3, a4 }
ANS: tmax = T
ANS:
ANS: Only shows the interaction when a customer visits the web site B1.
ANS:                 ------------->B2
ANS:                 |
ANS:                 V
ANS:      User ----> B1
ANS:                 ^
ANS:                 |
ANS:                 ------------->B3
ANS:
```

(2) @(1 point) The Petri net is defined as follows: I(t1) = {p1, p2}, O(t1) = {p2}, I(t2) = {p2, p3} and O(t2) = {p2}, where I(t1) is the set of input place(s) for transition t1, and O(t1) is the set of output place(s) for transition t1. The initial marking, i.e., the initial token distribution, is (1, 1, 1). What is the marking (token distribution) after two firings?

```ANS: (2) The transitions can be (1,1,1)-t1->(0,1,1)-t2->(0,1,0),
ANS: or (1,1,1)-t2->(1,1,0)-t1->(0,1,0).  Therefore, in either
ANS: case, the final marking after two firings is (0,1,0).
```
(3) @(0.5 point) True or False. In a live Petri net there is always some transition that is enabled.
```ANS: (3) True.
```
(4) @(0.5 point) True or False. In an IC Card System, if the current IC can perform the activity by itself, the interaction pattern is colored purple.
```ANS: (4) False.  It should be colored green.
```