CSA

Question 1

What does “embarrassingly parallelisable” mean?

Answer 1

A task can be parallelised without any information needing to be exchanged between threads.

Question 2

What is a mutual exclusion?

Answer 2

Only one thread is allowed to access some data at a given time, it must have acquired a lock on the data.

Question 3

How does a channel work in Go?

Answer 3

Shared memory with a mutex protecting it. Sender locks before writing data, and receiver locks before deleting the data.

Question 4

Flow of TCP/IP layers

Answer 4

Question 5

What is the TCP/IP Application layer?

Answer 5

• Used by the applications the user is interacting with.
• Defines protocols for using the network, error handling and recovery
• HTTP/S, FTP, DNS

Question 6

TCP/IP Transport layer

Answer 6

• First layer that breaks down messages into packets
• Common features: reliability, flow control
• TCP/UDP/QUIC

Question 7

TCP/IP Internet layer

Answer 7

• Responsible for routing packets through an internet
• Decide next hop a packet needs to take
• Handle errors in packet transmission
• Reassembles packets at destination
• IPv4/IPv6

Question 8

TCP/IP Link layer

Answer 8

• Concerns the network layer that is physically connected
• Protocols to convert data to signals along wires
• Protocols to handle ethernet/wifi/etc
• E.g. MAC Addresses

Question 9

What is livelock?

Answer 9

When a distributed program descends into an endless sequence of interaction with different components of itself, excluding interaction with the outside world.

Question 10

What is the general idea of CSP?

Answer 10

Reduce the description of a program to only its interactive behaviours.

Question 11

What is a CSP process?

Answer 11

• Independent, sequential entity
• Engage in events (operations visible to the environment)
• May communicate with other processes via common events
• Completely described by their possible event sequences

Question 12

What are primitive processes?

Answer 12

Represent fundamental, predefined behaviours such as:

• STOP (process that communicates nothing e.g. deadlock)
• SKIP (process that terminated succesfully)

Question 13

What are events?

Answer 13

Represent visible behaviours of a process (e.g. communications) which are atomic and instantaneous.

The set of all possible atomic events of a process P is its alphabet (or interface) written as α(P)

Question 14

What is prefixing?

Answer 14

Describing a process as an event followed by another process e.g:

SVM = coin -> STOP
SVM = coin -> (choc -> STOP)

For convenience we sometimes leave out the brackets, but do this ONLY when no strict CSP is asked for.

Question 15

What is a choice?

Answer 15

A choice describes alternate paths a process can take e.g:

Wait = green -> Walk | red -> Wait

Choices can be made amongst any finite number of events.

Choices are either internal (made by the process) or external (made by the environment).

Question 16

How do we describe multiple choices from an alphabet?

Answer 16

P = x: A → P(x) given A = {a1 ,…, an} means P can perform any event x from A

Read as ”x from A then P of x”.

Question 17

How do we sequentially compose processes?

Answer 17

P; Q performs P until P terminates with SKIP and then performs Q

Question 18

What is a trace?

Answer 18

A finite sequence of events, representing a particular behaviour of a process up to a point in time.

Written as comma-separated list of events, enclosed in angle brackets e.g:

<coin, choc, coin, sweet>

The set of all possible traces of a program is called traces e.g. traces(p)

Question 19

What is the trace refinement relation?

Answer 19

P refines to Q (P ⊑T Q) if and only if traces(P) is a superset of traces(Q). That is to say that Q exhibits at most the behaviour exhibited by P, possibly less.

Question 20

How do common events work?

Answer 20

An event common to two processes’ alphabets must be offered by both processes at the same time in order to occur and are then offered as one event.

Question 21

What is the number of states in a combined process P||Q?

Answer 21

If P and Q are independent, there are |P|*|Q| states.

Question 22

What is P/tr?

Answer 22

The process whose behaviour is whatever P could do after the trace tr has been observed.

Question 23

What are refusals?

Answer 23

The refusals of a state are the events which cannot occur at that time without causing a deadlock.

Question 24

What are failures?

Answer 24

Failures are pairings of traces to refusals.

Question 25

How do we represent an external choice?

Answer 25

P☐Q does either P or Q depending on an external choice (usually which process ended up processing the event first).

Permits choices with the same event in multiple branches e.g. (a -> P ☐ a -> Q) which cannot be written as (a -> P | a -> Q).

Question 26

How do we represent an internal choice?

Answer 26

P⊓Q does either P or Q depending on an internal choice to the program that cannot be influenced by the environment. For example P = a -> b -> STOP ⊓ b -> STOP

An example is a mail router which may choose the route to send mail along depending on network traffic where the end-user doesn’t care which route the mail takes.

The trace of an internal choice always does the invisible event 𝜏 first.

Question 27

What does 𝜏 mean?

Answer 27

A silent transition internal to the program that cannot be seen by the environment

Question 28

What is the set initials(P)?

Answer 28

The set of initial events that can be emitted by P

Question 29

What is a divergent process?

Answer 29

A process which may enter an infinite loop of internal decisions, preventing it from ever interacting with the environment again.

We can avoid them by specifying failure traces called divergences which are finite traces during or after which an infinite loop may occur.

Question 30

What are the four conditions of a deadlock?

Answer 30

Mutual Exclusion - Agents claim exclusive control of the resources they require
Wait For - Agents hold resources already allocated to them while waiting for more resources
No Preemption - Resources cannot be forcibly removed from the agent holding them until the resources are used to completion
Circular Wait - A circular chain of agents exist where each agent holds one or more resources that are being requested by the next agent in the chain

Question 31

What is a vector clock?

Answer 31

Each process holds a vector of the current timestamps of each process. It updates its vector whenever it receives a message from another process. It chooses which vector element is correct by which is highest.