Skip to main content

14. Distributed Algorithms

28/03/23

MoodlePDF

Interaction Models

Models and Assumptions

Computer clocks and timing events

  • Most computers have an internal clock which local processes can use to get the current time
  • But two processes in a distributed system reading their clocks at the same moment can get different time values
  • Each clock with drift from perfect time
  • Clocks can be correct to some extend by:
    • Using a GPS receiver on each computer where available/cost-effective => ~1 microsecond accuracy
    • Sending messages to other process => accuracy depends on communication latency

Synchronous distributed systems

  • Time to execute each step of a process has known upper and lower bounds
  • Each message transmitted over a channel is received within a known bounded time
  • Each process has a clock whose drift rate from real time has a known bound

Asynchronous distributed systems

Has no bounds on:

  • Process execution speeds
  • Message transmission delays
  • Clock drift rates E.g.
  • Busy web server can take a long time to handle a request
  • An email can take days to arrive
  • A servers clock can differ by any amount from the real time

Synchronous vs Asynchronous

  • Modelling interaction in a synchronous system can be useful, and simpler than the alternative
  • Some problem are impossible to solve in an asynchronous system, but can be solved

Distributed Algorithms

  • Algorithm - Describes a sequence of steps to be taken to perform a particular operation
  • Distributed algorithm - Describes the steps to be taken by each process in the distributed system, including sending/receiving messages
  • Intended to achieve one or more goals/outcomes
  • A correct algorithm will satisfy those goals - hopefully provably - provided its assumptions are met. If the constrains are not met, then most likely to fail
  • One distributed algorithm may provide a basis on which to build another

Logical Time

  • In an asynchronous system
    • Host clocks are not synchronised
    • So cannot provide a definite ordering of events happening at different hosts
  • Want to preserve the logical relationships between events
  • Represented as the happened before relation \to
    • aba\to b means even aa happened before event bb
    • If cc happens before dd in the same process then cdc\to d
    • Sending a message always happens before receiving the message

Lamports logical clock algorithm

  • Each process pip_i maintains a logical clock LiL_i which is used to assign Lamport timestamps to each event
    • Li(e)L_i(e) is the timestamp of event ee at the process ii
    • L(e)L(e) is the timestamp of event ee at the process it occurred at
  • LC1: LiL_i is incremented before each event at pip_i
  • LC2(a): when pip_i sends a message mm it piggybacks the value t=Lit=L_i
  • LC2(b): on receiving (m,t)(m,t) at pjp_j, do Lj=max(Lj,t)L_j = \max(L_j,t) then LC1 then timestamp recieve(m)

Routing in Distributed Hash Tables

In the Pastry DHT

  • Each node has a GUID
  • Each value/file has a GUID
  • Values are stored at the node whose GUID is closest to the values
  • The nodes organise themselves into an overlay network that is a ring sorted in order of GUID

Pastry request routing

  • Routing requests to add/remove/get a specified value GUID
  • So a request can be routed in the overlay network simply by sending it to he neighbour in the direction with the closer GUID
    • Each node knows it neighbours whether it is current to the closest node
    • Each hop will get closer
    • So eventually it will reach the right node