14. Distributed Algorithms
28/03/23
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
- means even happened before event
- If happens before in the same process then
- Sending a message always happens before receiving the message
Lamports logical clock algorithm
- Each process maintains a logical clock which is used to assign Lamport timestamps to each event
- is the timestamp of event at the process
- is the timestamp of event at the process it occurred at
- LC1: is incremented before each event at
- LC2(a): when sends a message it piggybacks the value
- LC2(b): on receiving at , do 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