Clocks and ordering

Question 1

Modelling assumptions

Answer 1

Distributed processes communicate via messages
Events of a process form an event sequence where a->b
Sending or receiving messages is an event

Question 2

Definitions of the happened before relation (->)

Answer 2

1) if a and b are events in the same process and a occurs before b then; a->b
2) if a is the sending of a message and b is the receipt of that message then a->b
3) if a->b, b->c then a->c
4) Two distinct events a and b are said to be concurrent if a->b and b-> a are not true. It would be denoted as (a||b)

Question 3

Correctness condition for logical clocks and its requirements.

Answer 3

for any events; a,b, if a->b, then C(a)<C(b)

CL1: If a and b are events in Process x and a->b, then Cx(a)<Cx(b)
CL2: If a is the sending of a message and b is the receiving of a message during process x, then Cx(a)<Cx(b)

Question 4

Implementing logical clocks rules

Answer 4

IR1: Each process x increments Cx immediately after an event
IR2: i) If a is an event representing the sending of a message m by process x to y, then m contains the timestamp: Tm = Cx(a)
ii) Receiving m by event b by process y, peeks at m; then increments Cy if necessary to ensure that the timestamp is greater than that of the message.

Question 5

Total order definition

Answer 5

This is a solution for concurrence control, so we are able to order events totally. This is done to break ties in concurrent events.

Question 6

Total order observations

Answer 6

1) if a->b then a=>b. If a=>b then a->b or a||b. This means that b->a is definitely not possible
2) while -> is unique for a given set of results, there could be several => orderings depending on the rule used to break this
3) The total ordering of logical clocks cannot be guaranteed to respect ordering of evens in the passage of real time

Question 7

Anomalous behaviour

Answer 7

A system S using logical clocks for total ordering can permit anomalous behaviour, where events are observed to happen in the order that is not consistent with the ordering indicated by the clock numbers.
This causes AB to arise in a system due to non traditional communication between 2 entities such as verbal or no communication.

Question 8

Strong clock condition

Answer 8

for events a,b in S: if a➔ b, then C(a) < C(b)

This is used to prevent anomalous behaviour

Question 9

Why can’t the strong clock condition be met by logical clocks

Answer 9

As logical clocks only tick for events in S, not the whole supersystem, and the inter-tick duration does not respect the passage of real time

Question 10

Physical clocks

Answer 10

These are used for timestamping messages so clocks must reference the ticks respecting the real passage of time

Question 11

Physical clock requirements

determining faster and slower clocks

Answer 11

Ri: the rate at which Ci runs relative to ref time/ real time
* (Ci(t2) - Ci(t1))/(t2 – t1)
Ideally, Ri must be equal to 1; if so,
* (Ci(t2) - Ci(t1)) = (t2 – t1) and Ci is called a perfect clock
Perfect clocks hardly exist due to impurities in crystal
A given physical clock runs either
* faster: (Ci(t2) - Ci(t1)) > (t2 – t1) or Ri > 1, or
* slower: (Ci(t2) - Ci(t1)) < (t2 – t1) or Ri < 1

Question 12

Physical clock conditions

Answer 12

1) There is a known constant k (k«1) such that for all values of t: 1-k<= (Ci(t2) - Ci(t1))/(t2 – t1) <=1+k

2) for all i and j, and for all t :
Either 0 ≤ Ci(t) - Cj(t) ≤ e (assuming Ci is faster than Cj),
or 0 ≤ Cj(t) - Ci(t) ≤ e (assuming Cj is faster than Ci)

Question 13

Hardware approach for synching physical clocks

Answer 13

Use special hardware circuits to
(i) timestamp the clock-synch messages just before they get transmitted to a physical medium

(ii) note the arrival time and copy the timestamp of an incoming clock- synch message soon after it is received from the medium

Question 14

centralised approach for synching physical clocks

Answer 14

a reference clocks periodically transmits its value, and upon A and B receiving the timestamped message, it updates its value.

mmx is the maximum time elapsed between timestamping and receiving so, the initial error can be (mmx - m) which is the maximum variabilities in delays for message processing, queueing and transmission; E > (Umx -U)

Question 15

Use of total order to construct algorithms

Answer 15

Example of a exclusive use of a single resource:
(i) a process that has been granted the resource must release it before it can be granted to another process;
(ii) different requests for the resource must be granted in the → order in which they were made;
(iii) if every process that is granted the resource eventually releases it, then every request is eventually granted

Question 16

Assumptions before implementing the algorithm

Answer 16

(i) Events can be ordered according to the total order relation =>
(ii) For any two processes x and y, messages sent by x to y are received in the sent order
(iii) A process can send a message directly to every other process.
(iv) Each process maintains a queue for its own use
(v) P0 has the resource and all the request queues have a single message; ‘T0: P0 requests resource’ and T0 is less than the current clock value of all processes.

Question 17

The algorithm

Answer 17

(i) To request a resource, Pi sends the message ‘Tm: Pi requests resource’ to every other process and also puts this message in its own request queue.

(ii) When a process Pj receives ‘Tm: Pi requests resource’, it places it on its request queue and sends a timestamped acknowledgement message to Pi.

(iii) To release the resource, the process using the resource (say P0) removes any ‘T0: P0 requests resource’ message from its request queue and sends ‘T: P0 releases resource’ message to every other process.

(iv)When a process Pj receives a ‘T: P0 releases resource’ message, it removes any ‘T0: P0 requests resource’ message from its request queue.

(v) A process (say Pi) is granted the resource when the following two conditions are satisfied:
(a) there is a ‘Tm: Pi requests resource’ message in its
request queue which is ordered before any other
request in its queue; and
(b) Pi has received a message with timestamp
greater than Tm from every other process.