Distributed System Notes PDF

Preview

Summary

dwsxsadcds sdfvaedfqwedc dvadvade ewfefqadsc wdcqdsc wecqdsdv vqefvqervfv dfvqefdv dfvqaerg3v werft34rfgf frgdfhhr gqergwtrtgh fsfghstrhstrhv v bgbefwrg...

Description

Logical Clock Logical Clocks refer to implementing a protocol on all machines within your distributed system, so that the machines are able to maintain consistent ordering of events within some virtual timespan. A logical clock is a mechanism for capturing chronological and causal relationships in a distributed system.

Algorithm: 

Happened before relation (->): a -> b, means ‘a’ happened before ‘b’.



Logical Clock: The criteria for the logical clocks are: 

[C1]: Ci (a) < Ci(b), [ Ci -> Logical Clock, If ‘a’ happened before ‘b’, then time of ‘a’ will be less than ‘b’ in a particular process. ]



[C2]: Ci(a) < Cj(b), [ Clock value of Ci(a) is less than Cj(b) ]

Reference: 

Process: Pi



Event: Eij, where i is the process in number and j: jth event in the ith process.



tm: vector time span for message m.



Ci vector clock associated with process Pi, the jth element is Ci[j] and contains Pi‘s latest value for the current time in process Pj.



d: drift time, generally d is 1.

Implementation Rules [IR]: 

[IR1]: If a -> b [‘a’ happened before ‘b’ within the same process] then, Ci(b) =Ci(a) + d



[IR2]: Cj = max(Cj, tm + d) [If there’s more number of processes, then t m = value of Ci(a), Cj = max value between Cj and tm + d]

Vector Clock Vector Clock is an algorithm that generates partial ordering of events and detects causality violations in a distributed system. These clocks expand on Scalar time to facilitate a causally consistent view of the distributed system, they detect whether a contributed event has caused another event in the distributed system. It essentially captures all the causal relationships. This algorithm helps us label every process with a vector (a list of integers) with an integer for each local clock of every process within the system. So, for N given processes, there will be vector/ array of size N.

Limitations of Distributed System 1. Absence of a Global Clock: In a distributed system there are a lot of systems and each system has its own clock. Each clock on each system is running at a different rate or granularity leading to them asynchronous. In starting the clocks are regulated to keep them consistent, but only after one local clock cycle they are out of the synchronization and no clock has the exact time. Time is known for a certain precision because it is used for the following in distributed system:



Temporal ordering of events



Collecting up-to-date information on the state of the integrated system



Scheduling of processes

There are restrictions on the precision of time by which processes in a distributed system can synchronize their clocks due to asynchronous message passing. Every clock in distributed system is synchronize with a more reliable clock, but due to transmission and execution time lapses the clocks becomes different. Absence of global clock make more difficult the algorithm for designing and debugging of distributed system. 2. Absence of Shared Memory: Distributed systems have not any physically shared memory, all computers in the distributed system have their own specific physical memory. As computer in the distributed system do not share the common memory, it is impossible for any one system to know the global state of the full distributed system. Process in the distributed system obtains coherent view of the system but in actual that view is partial view of the system. As in distributed system there is an absence of a global state, it is challenging to recognize any global property of the system. The global state in distributed system is divided by many number of computers into smaller entities....