Question

14. Circle the correct answer: In a distributed memory architecture the interconnection network determines the speed of data accesses, thus this is a

UMA (Uniform Memory Access)            NUMA (Non-uniform Memory Access)

15. A transition system consists of
A set ? of configurations
A binary transition relation ⟶ on ?
A set I ⊆ ? of initial configurations.

1. Define what a terminal configuration is.

2. Define what an execution is.

16. Describe what a race condition is.

17. Lamport’s logical clock LC assigns to an event a the length k of a longest causality chain
?_1≺⋯≺?_?=? in the computation. To calculate the LC values for an event:
Let a be some event and k be the clock value of the event just before a at some process.
If a is the first event and it is an internal or send event, the LC(a) = 1
If a is an internal or send event, then LC(a) = k+1
If a is a receive event and b the send event corresponding to a, then LC(a) = max{ k, LC(b) } + 1

Consider three processes and the following sequence of events at processes p0, p1, p2:
p0 : a s1 s2 b
p1 : c r2 s3
p2 : r1 d r3 e

What are the Lamport’s logical clock values?

Answer 1

• 1st answer is  NUMA(Non-uniform Memory Access)

The NUMA architecture defines the node as the Processing Element, with cache lines and a part of the main memory. Then, each node is connected to each other by the network. So, in the NUMA architecture we could say that the memory and the cache are distributed in the nodes, while in the UMA architecture is only the cache that is distributed.

• A transition system consists of set C of configuration.

(a) A key use of terminals is to define start and end points of subnetwork traces. Terminals are also used to establish paths within a device feature for which a commodity travels through. To establish a terminal configuration.

(b)Execution is the process by which a computer or virtual machine executes the instructions of a computer program.In this case, the "commands" are simply program instructions, whose execution is chained together.

• A race condition is an undesirable situation that occurs when a device or system attempts to perform two or more operations at the same time, but because of the nature of the device or system, the operations must be done in the proper sequence to be done correctly.

• A logical clock is a mechanism for capturing chronological and causal relationships in a distributed system. The algorithm of Lamport timestamps is a simple algorithm used to determine the order of events in a distributed computer system.
• According to the rule (4) of Lamport’s Algorithm, every process has a freedom to remove ANY-ONE request in the queue. Because of this randomness in the rules, P0 might end up waiting for the ACK of removed request from P1, whereas, P1 might also wait for the removed ACK from P0. This will make process to starve and leads to Deadlock.

we have defined the events and their order, we need to differentiate between the two events by assigning clock(LC) to every event. LC is nothing but a way of assigning a number to an event which increments between the two events. With the definition of events, if we say that event a happened before b, then a should have happened at an earlier time than b,

i.e . for any events a, b: if a → b, then LC(a) < LC(b)

Catch: is the converse true? It cannot be! Because if LC(a) < LC(b), there is also a possibility that a and b can be concurrent events of same process. To describe this clock to event relation more precisely, lamport designed a two conditions to be held between the two. they are:

C1: If a and b belongs to same process P and a → b, then LC(a) < LC(b).
C2: If a is a sending event of process Pi and b is the recipient event of process Pj, then LCi(a) < LCj(b).

Now, even though we can successfully log the events indexing with respective LC, we need a mechanism on how to increment LC. To do so, lamport discussed two implementation rules to be followed by every process in designing LC:

(IR1) Each process Pi increments LCi between any two successive events.
(IR2) (*) If event a is sending a message m by the process Pi with the timestamp Tm = LCi(a) . (*) On receiving a message m, Process Pj sets Cj greater than or equal to Cj and greater than Tm. i.e.

Initially, LC = 0; Send: LC++, Tm=LC; Receive: LC = max (LC, Tm)+1

IR1 and IR2 ensures that clock conditions are satisfied. So, they guarantee a correct system of logical clocks.

IR2 is ensured because receive LC will be set before the event message Tm is received. But, what if we set the receive LC after event message Tm is received? All you have to do is, Receive: LC = max(LC, Tm+1)

With the timestamp we can order the events they appear. But, what if two events amongst the process happen at a same time (LC)?To break such tie, Lamport defined a relation, “==>” as: if a is an event in process Pi and b is an event in process Pj , then a==> b if and only if either (i) LCi(a) < LCj(b) (ii) LCi(a) == LCj(b) and Pi < Pj. i.e. We break a tie using the process ids of the communicating process. This relation constitute for a total ordering of events using lamport’s logical clock.