Please enable JavaScript.

Coggle requires JavaScript to display documents.

Week 7 Distributed (Synchronisation (Clock Synchronization (Cristian's…

- - - - A drift of 1% (1/100) means that a clock adds or loses a second every 100 seconds
    - - Sync all machines to one time server
      - Time server responds ASAP to requests for time value
      - Requestor sets clock to
        recieved_time + (T1 - T0 - I)/2
        
        T1 is time requestor recieved
        
        T0 is time requestor sent
        
        I is interrupt handling time
      - Needs to be constantly adjusted
      - SImilar to ping
      - Centeralized & therefore a single point of failure
    - - Time server (master) polls slave processes
      - Steps
        
        Master chosen with ring based election (Chang & Roberts)
        
        Master polls slave who reply with their time
        
        Master measures RTT and estimates slave time & its own
        
        Average times ignoring outliers
        
        Sends offsets to each slave to adjust their time to the average. Avoids uncertainty due to RTT
      - Centralized & therefore a single point of failure
    - - Decentralized
      - Everyone broadcasts their current time at time intervals of length R
      - Machine will average all the broadcasts it gets
    - - Logical Clocks
        The order of events have to be in the right order, not nessicarily having the correct real times accross different machines
      - Physical Clocks
        A clock that agrees on the correct time within an error bound
    - - Only determines event order
      - A->B is saying A happens before B
      - Happens-before relation is transitive
        If A->B->C then A->C
      - If two processes don't exchange messages then
        X -> Y & Y -> X is not true
        These events are concurrent
      - A function C exists where if A->B then C(A) < C(B)
      - Clock forward, never backward
  - - - Ensures mutual exclusion
      - Steps
        
        Process A sends request to access a resource
        
        Coordinator checks if someone is already using that resource
        
        If someone is not, then process A is let through. Otherwise they are queued until that process notifies the coordinator they are done
      - Advantages
        
        FCFS therefore it's fair
        
        Simple & easy to implement
        
        Only 3 msgs: request, grant and release
      - Disadvantage
        
        Central point of failure
        
        Cannot distinguish between dead coordinator or permission denied
        
        Performance bottleneck if only one coordinator
      - Central manager to resources.
    - - Steps
        
        Broadcast request to enter critical section
        
        Recipients follow condition branch
        
        Enter critical section when all processes say OK
        
        When done, send OK to all requests in the queue
      - Conditions
        
        Has sent request & waiting for response?
        
        Yes
        
        Is timestamp recieved > timestamp sent?
        
        Yes
        
        Queue
        
        No
        
        Send OK
        
        No
        
        In critical section?
        
        Yes
        
        Queue
        
        No
        
        Send OK
    - - No. Messages exchanged
        Centralized: 3
        Distributed: 2*(n-1)
        Ring: 2
      - Reliability problems
        Centralized: Coordinator crash
        Distributed: Any process crashes
        Ring: Lost token, process crash
- - - - Lax
    - - Strict, all or nothing