Lectures 10 and 11: 5th November 2019

Question 1

What is a TS?

Answer 1

!

Question 2

What is a PG?

Answer 2

!

Question 3

What is an arbtier?

Answer 3

!

Question 4

How can you implement mutual exclusion with an arbiter?

Answer 4

!

Question 5

What is a semaphore?

Answer 5

!

Question 6

How can you implement mutual exclusion with a semaphore?

Answer 6

!

Question 7

How do you compose multiple PGs together?

Answer 7

!

Question 8

How do you interleave multiple PGs together?

Answer 8

!

Question 9

How do you find the reachable part of a TS?

Answer 9

!

Question 10

When does a state satisfy a property?

Answer 10

!

Question 11

When does a TS satisfy a property?

Answer 11

!

Question 12

What is the difference between unconditional, strong, and weak fairness?

Answer 12

Unconditional = Every process gets its turn infinitely often.”

Strong = “Every process that is enabled infinitely often gets its turn infinitely often.”

Weak = “Every process that is continuously enabled from a certain time instant onwards gets its turn infinitely often.”

Question 13

How can you formulate unconditional, strong, and weak fairness in LTL?

Answer 13

Unconditional = ufair = ☐◇criti

Strong = sfair = ☐◇waiti → ☐◇criti

Weak = wfair = ◇☐waiti → ☐◇criti

Question 14

How can you formulate strong fairness in a TS of two composed PGs implementing mutual exclusion?

Answer 14

!

Question 15

What is a linear logic?

Answer 15

!

Question 16

What are the implications of LTL being a linear logic?

Answer 16

!

Question 17

What types of formulae are easy, hard, and impossible to express in LTL?

Answer 17

!

Question 18

What are branching logics?

Answer 18

!

Question 19

What are branching time logics?

Answer 19

!

Question 20

What are the unfoldings of a model?

Answer 20

!

Question 21

What is CTL?

Answer 21

!

Question 22

What are the two types of CTL formulae?

Answer 22

!

Question 23

What are CTL state formulae?

Answer 23

!

Question 24

What are CTL path formulae?

Answer 24

!

Question 25

What is the format of CTL state formulae?

Answer 25

!

Question 26

What is the format of CTL path formulae?

Answer 26

!

Question 27

How can you convert between state and path formulae/

Answer 27

!

Question 28

How must temporal operators be formatted to be legal in a state formula?

Answer 28

!

Question 29

What do ∃ and ∀ mean in state formulae?

Answer 29

!

Question 30

How do you formulate a mutual exclusion property in CTL?

Answer 30

!

Question 31

What are the equivalence laws of CTL?

Answer 31

!

Question 32

When does a state satisfy a CTL state formula?

Answer 32

!

Question 33

When does a path satisfy a CTL path formula?

Answer 33

!

Question 34

What is the satisfaction set of a CTL state formula?

Answer 34

!

Question 35

When are two CTL formulae equivalent?

Answer 35

!

Question 36

Give the basic model checking algorithm for CTL formulae.

Answer 36

!

Question 37

What are synchronous and asynchronous communications?

Answer 37

!

Question 38

What are channel systems?

Answer 38

!

Question 39

How do channel systems work in PROMELA?

Answer 39

!

Question 40

What are communication actions in PROMELA?

Answer 40

!

Question 41

How are communiation actions formatted in PROMELA?

Answer 41

!

Question 42

What is the capacity of a channel?

Answer 42

!

Question 43

How does handshaking work in PROMELA?

Answer 43

!

Question 44

How do you find the capacity of a channel in PROMELA?

Answer 44

!

Question 45

When can processes send and get messages into or from a channel?

Answer 45

!

Question 46

What are channel systems?

Answer 46

!

Question 47

What are channel systems used for in PROMELA?

Answer 47

!

Question 48

What is alternating bit protocol?

Answer 48

!

Question 49

How does ABP implement reliable comms over unreliable channels?

Answer 49

!

Question 50

How does ABP work?

Answer 50

!

Question 51

What are concurrent systems?

Answer 51

!

Question 52

What are the differences between different concurrent systems?

Answer 52

!

Question 53

What are timed automata?

Answer 53

!

Question 54

How do timed automata work?

Answer 54

!

Question 55

What is UPPAAL?

Answer 55

!

Question 56

How does UPPAAL work?

Answer 56

!

Question 57

What is TCTL?

Answer 57

!

Question 58

How does TCTL work?

Answer 58

!

Question 59

What are untimed models?

Answer 59

!

Question 60

What are untimed actions?

Answer 60

!

Question 61

How do untimed models work?

Answer 61

!

Question 62

What are real-time constraints?

Answer 62

!

Question 63

How can you implement timed models with and without using timed automata?

Answer 63

!

Question 64

Is it easier to implement timed models with or without timed automata? Why?

Answer 64

!

Question 65

Why is using a set of clocks acting as stopwatches a poor solution for implementing timed automata?

Answer 65

!

Question 66

How do timed automata work, in detail?

Answer 66

!

Question 67

What are clock constraints?

Answer 67

!

Question 68

How do you mathematically define a timed automaton?

Answer 68

!

Question 69

How are transitions in timed automata formatted?

Answer 69

!

Question 70

What are location invariants in timed automata?

Answer 70

!

Question 71

How do you implement location invariants in timed automata?

Answer 71

!

Question 72

What is the difference between guards and location invariants in timed automata?

Answer 72

!

Question 73

How do clocks work in timed automata?

Answer 73

!

Question 74

How are clocks implemented in timed automata?

Answer 74

!