Distributed OS Basics

Question 1

What is a distributed system?

Answer 1

a system that consists of several computers that do not share a memory or clock and communicate with each other by exchanging messages over a communication network

Question 2

5 motivations for developing and using a distributed system

Answer 2

Improved price/performance

resource sharing

enhanced performance

improved reliability and availability

modular expandability

Question 3

Benefit of improved price/performance

Answer 3

equivalent computing power may be obtained by a network of workstations at a much lower cost than a traditional time-sharing system

Question 4

Benefit of resource sharing

Answer 4

requests for services may be satisfied using hardware/software resources on other computers on the communication network

Question 5

Benefit of enhanced performance

Answer 5

concurrent execution of tasks and load distributing can lead to improved response time

Question 6

Benefit of improved reliability and availability

Answer 6

fault tolerance can be achieved through the replication of data and services

Question 7

Benefit of modular expandability

Answer 7

new hardware and software resources can be added without replacing the existing resources

Question 8

5 design issues with distributed systems

Answer 8

global knowledge

naming

scalability

compatibility

process synchronization

Question 9

Issues with global knowledge

Answer 9

the global state of the system is hard to acquire due to the unavailability of a global memory and a global clock along with the unpredictability of message delays

aka its impossible to know the state of the entire system at a given point and thus nothing can assume or be based on an up to date global state being available

Question 10

Issues with Naming

Answer 10

the directory of all the named objects (services, files, printers, etc) in the system must be maintained to allow proper access.

How is one node in the system supposed to know the name of an object on another node?

does one node hold the records for all named objects?

does every node maintain their own record of all objects in the system?

are the naming records for the system partitioned in some way across all the nodes such that a single node could logically determine where to find an object based on some properties of that object?

Question 11

Issues with Scalability

Answer 11

any mechanisms or approaches adopted in a system must result in badly degraded performance when the system grows

Question 12

Issues with compatibility

Answer 12

the interoperability among the resources in a system must be an integral part of the design of a distributed system

Question 13

Issues with process synchronization

Answer 13

especially difficult in distributed systems due to the lack of shared memory and a global clock

none of the previously discussed methods work for distributed systems

Question 14

2 inherent limitations of a distributed system

Answer 14

lack of common memory

lack of system-wide clock

Question 15

Limitations caused by lacking system-wide clock

Answer 15

without global time it is difficult to talk about a temporal ordering of events

Question 16

Limitations caused by a lack of shared memory

Answer 16

up-to-date information about the state of the system is not available to every process by a simple memory lookup. The state information must be collected through communication

Question 17

Happened Before Relation

Answer 17

a (arrow) b means that event a happened before the event b

Question 18

properties of Happened before relation

Answer 18

if a and b are events in the same process then a happened before b

if a is the sending of a message to node i and b is the event receiving the message then a happened before b

if a arrow b and b arrow c then a arrow c is also true

Question 19

Causal dependency of events

Answer 19

if a arrow b or b arrow a then a and b are causally related.

a arrow b means a casually affects b

if neither are true the events are said to concurrent

Question 20

Lamport’s logical clocks - timestamp

Answer 20

a number Ci(a) associated with an event ‘a’ in process i

The timestamp of an event will be of the form enk. Where n is the node and k is the value of logical clock at that node

Question 21

How do Lamport’s logical clocks relate to happened before relationship

Answer 21

‘a’ arrow ‘b’ is true if either of the following is true:

• for ‘a’ and ‘b’ in process i, if Ci(a) < Ci(b)
• if ‘a’ in process i is the sending of a message to ‘b’ in process j and Ci(a) < Cj(b)

Question 22

Rules of implementing Lamport’s logical clocks

Answer 22

The clock Ci is incremented after each successive event in Pi by a value of d (typically we increment by 1)

If ‘a’ in process i is the sending of a message ‘m’ to process j then ‘m’ is assigned a timestamp called tm = Ci(a).
When process j receives the message it assigns the value Cj according to the first rule described above. Then the final value of Cj = max(current Cj value, tm + d).

Question 23

Limitation of Lamport’s logical clocks

Answer 23

for any two arbitrary events in ‘a’ in process i and b in process j

Ci(a) < Cj(b) DOES NOT necessarily imply ‘a’ arrow ‘b’

we have no way of knowing the ordering of those events

Question 24

Vector Clocks

Answer 24

essentially a vector of integer values, ‘C’, maintained by each node. The ith node has its own logical time at Ci[i].
All other elements of vector Ci represent the ith node’s best guess as to the logical time of other nodes.

With that, the following must hold Ci[j] less than or equal to Cj[j]

Question 25

2 rules of implementing vector clocks

Answer 25

Clock Ci is incremented after successive events in process Pi by a value of d (typically 1)

This second rule is implemented just like lamport’s logical clock but extended for an entire array.
Let ‘a’ in process i, be the sending of a message ‘m’ to process j. When process j receives the message its increments Cj[j] according to the rule above.
Then for each entry Cj[k] (k from 1 to n), Cj[k] = max (Cj[k], Ci[k]) (find the max value at each entry and update Cj as needed)

Question 26

Definition of causal order of messaging

Answer 26

Send(m1) arrow Send(m2) implies Receive(m1) arrow Receive(m2)

Question 27

Cut event

Answer 27

is the recording of a single node’s local state at a given time

Question 28

Definition cut

Answer 28

The set C of cut events ci for all nodes in the distributed system

A cut represents the global state of the system

Question 29

Consistent cut

Answer 29

A cut C is inconsistent iff for every pair of events ei and ej where the following expression is TRUE

(ei arrow ej) AND (ej arrow cj) AND NOT(ei arrow ci)

AKA every message received before the cut event at Site J was sent from Site i before the cut event at Site i