Untitled

• Synchronization involves coordinating events across different nodes in a network.
• Events at different nodes in a network use different clocks for recording.
• The timing of events in a distributed system determines the order of writes and data staleness.
• Determining if it is possible to sell stock that does not exist is a synchronization issue.

Clock Synchronization

• Clock synchronization is difficult to achieve in practice.
• Synchronizing clocks on every node in the network is a simple solution, however.

Hardware Clocks

• Crystal oscillators connected to oscillation counter circuitry are hardware clocks in computers.
• This counter is then scaled to provide a physical time approximation.

Problems with Hardware Clocks

• Hardware clocks are not all the same.
• Clock rate is affected by physical differences in the crystal.
• Clock rate is affected by temperature differences.
• Voltage and humidity affect the clock rate.
• Skew is a disagreement in the reading of two clocks.
• Drift is the difference in the rate at which two clocks count time..
• Clock Drift Rate is the difference in precision between a hardware clock and a reference clock.
• Normal clocks have a clock drift rate of approximately 10-6 sec/sec.
• High precision clocks have a clock drift rate up to 10-7 - 10-8 sec/sec.
• Assuming a normal clock drift rate of 10-6 sec/sec, a drift of 1ms occurs in approximately 17 minutes.
• Assuming a normal clock drift rate of 10-6 sec/sec, a drift of 1s occurs in approximately 12 days.

Synchronizing Clocks

• External Synchronization involves using an external authoritative clock to update the clock of nodes in the network.
• With External Synchronization, skew is limited to the delay between the authoritative clock server and the node.
• In Internal Synchronization, Nodes in the network collaborate to limit the skew to a delay bound but has larger delay.
• Software-Based Clock Synchronization methods include Christian's Algorithm, Berkley Algorithm, and Network Time Protocol (Internet).

Christian's Algorithm

• This algorithm assumes LAN networks have a sufficiently small round trip time.
• It requires a clock server synchronized to UTC time.
• A node in the network sends a request to the clock server and records the Round Trip Time (RTT).
• The clock server measures its current time (T) and sends this to the node.
• A node updates its time t to be t = T + RTT/2.

Christian's Algorithm Problems

• The duration of the two parts of the round trip are assumed to be equal.
• It is unsuitable outside a LAN because RTT increases dramatically.
• The clock server being a central point of failure is a problem.

Berkeley Algorithm

• A master server is used to alter the clocks and not a synchronized server.
• A master server periodically polls all nodes in the network.
• It records RTT to estimate a node's clock like in the Christian's algorithm.
• Berkeley Algorithm averages the values obtained from all nodes.
• Instructions are given for nodes to alter clocks and synchronize times.
• A master election algorithm is used if the master fails.

Berkeley Algorithm Problems

• It is only suitable for LAN networks.
• Nodes are synchronized with each other instead of with external systems like with Christian's algorithm.

Network Time Protocol (NTP)

• This protocol improves upon previously discussed algorithms.
• Clients can synchronize via the Internet.
• Reliable service is available in the event of lengthy losses of connectivity.
• There is protection against interference.
• NTP uses a hierarchical model with varying levels of accuracy, assigning different stratum.
• Stratum 0: High precision timekeeping devices like atomic clocks, GPS, or radio clocks which act as reference clocks.
• Stratum 1: Computers synchronized within microseconds of a Stratum 0 device, which act as primary time servers.
• Stratum 2: Nodes connected to primary time servers, connecting to multiple primary time servers is possible.
• There are up to 15 stratum that are possible in NTP.
• With NTP, the higher the stratum number decreases the accuracy of the node's clock due to the increased RTT.
• Timestamps use 64 bits, comprising 32 bits for seconds and 32 bits for fractional seconds
• The theoretical resolution of NTP timestamps is 233 picoseconds.
• There is a timescale that rolls over every 136 years and the first rollover will occur on February 7th 2036.

NTP Algorithm

• NTP client will regularly poll one or more servers.
• Time offset θ is derived from (t1 - t0)+(t2-t3) / 2.
• Round trip delay δ is derived from (t3 - t0) - (t2 - t1).
• After this data is returned to the client, the client must eliminate outliers using a statistical filter.
• Offset is estimated from the best three remaining candidates favoring higher stratum messages.
• Adjusts the client's clock gradually reduces the offset.

Synchronization Requirements

• Causality: Real-time order is similar to timestamp order.
• Groups/replicated: Same order of member visibility for group events.
• Multiple-copy-updates: Consistency conflicts and order of updates.
• Serializability of transactions: Common order of transaction order.

Happened-Before Relations (a->b)

• a and b are defined as events in the same process.
• If a occurs before b then a happens before b (a->b).
• If a is a message being sent and b is a message being received, then a->b.
• a || b occurs if is neither a->b and b->a (a and b are concurrent).
• If a->b and b->c then a->c.

Lamport Timestamps

• All timestamps include: the process increments its counter before each event.

• A process includes its counter when it sends a message.

• Upon receiving a message: The recipient's counter updates to the greater of its current value or the timestamp.

• The event counter is then incremented to show the message has been received.

• Where p is the process, e the event, L is the counter and t is the timestamp:

• Where pi is the process, before each event L₁ = Li + 1.

• Whenever a process sends a message 'm' to pj:

• pi: Li = Li + 1; t = Li; message = (m,t).

• pj: Lj = max(Lj, t); Lj = Lj + 1.

• Lj receives the event as Lj.

Lamport Timestamps Problems

• The Lamport timestamp of event a is less than the Lamport timestamp of event b if there is any way that event a could have influenced event b.
• If two Lamport timestamps exist where L(a) < L(b), a->b cannot explicitly be stated because these timestamps do not fulfill the strong clock consistency condition.
• Lamport timestamps only accomplish partial event ordering.
• They can provide a 'total event ordering' by incorporating a mechanism to resolves ties (however causality cannot be implied).

Total Ordered Lamport Timestamps

• Timestamps can be expanded to (Li(e), i).
• (Li(e), i) < (Lj(e), j).
• If Li(e) < Lj (e) or (Li(e) = Lj (e) and i < j).

Vector Clocks

• These expand on Lamport Timestamps through the incorporation of causality violation detection data.
• Each Process Pi maintains a vector Vi
• Vi[i] represents the events that have occurred at Pi.
• If Vi[j] = k, then Pi knows about the k events that have occurred at Pj.

Vector clock ordering

• V = V' iff V[j] = V' [j].
• V ≤ V' iff V[j] ≤ V' [j].
• V.
• e -> e' => V(e) V(e').
• If not V(e)≤ V(e') and not V(e') ≤ V(e), then e || e'.

Vector Clocks algorithm is as follows

• Pi multicasts Vi[i] = Vi[i] + 1.
• Each message includes Vi.
• For each Pj, which is receiving a message.
• The message can be delivered when Vi[i] = Vj [i] + 1 (Every message from i has arrived).
• When Vj [k] >= Vi[k] for all k, k≠i (j must have read every message that i has read when the sent message was sent).
• Upon delivery of message: Vj [i] = Vj [i] + 1.

Global State

• Timestamps can be used to save a snapshot of a distributed system for many purposes.
• States of Processes and Messages in Transfer are needed to create a snapshot.
• Snapshot validity can be affected by Garbage Collection, Deadlock, and Termination problems.

Garbage Collection

• An automatic form of memory management.
• Distributed systems benefit because of difficulties in multiple systems manual memory management.
• It is important in a distributed messaging system.
• Messages must be kept until they can be processed and then discarded by a garbage collector.
• In a snapshot, messages are examined to determine whether they are discarded.

Deadlock

• Results when two processes wait for each other to take an action associated with a resource through releasing a lock.
• P₁ has a lock on resource R₁, and p₂ has a lock on resource R₂ creating an example of deadlock.
• P1 must obtain R2 before R1 is released in order to resolve lock, P2 must do the opposite.
• Both P₁ and P₂ will remain in deadlock with the locks not being obtained unless intervened.
• Solving deadlocks and preventing them are useful for consistent progress in distributed systems.

Global Snapshot

• A particular algorithm can achieve a global snapshot .
• At each node i: Record the current time (Ti) using a local clock; record a state (Si) through containing {event, timestamp} tuples.
• S, the system state, is described through individual node states. (Si).
• T indicates up to which information on the node is contained in a snapshot
• Snapshots can be consistent or inconsistent.

Consistent Snapshot

• Occurs if all events taking place before the snapshot time T are tracked .
• xį describes local values during threshold value changes.
• Send is given to another processor following a threshold being exceeded.
• Increment vector after 'changes' to make S record changes.

Chandy-Lamport Algorithm

• Provides consistent global distributed systems states, with its use.
• The algorithm requires two assumptions: There are no network failures and all communications arrive intact; and the integrity of the standard activities processes must be retained during snapshots.
• This may be modified with tcp/ip to remove no network failures assumptions.
• A process (initiating the snapshot) saves its state and dispatches a snapshot request to processes using a snapshot token.
• Upon receipt , the snapshot then receives its saved state.
• A snapshot token is then attached to all messages, or the token the process uses to save its state.
• If a non token message is received on receipt that it has the token it forward it .

Resource Reservation

• Useful in resource management.
• Can be either centralized or distributed and the decision affects potential fault tolerances.
• Typically can be implemented easily, and are harder to debug.
• Fault tolerant properties are increased at the cost of greater debugging and design requirements.
• Mutual Exclusion is another name used for this.

Centralized Resource Allocation

• First, the process asks a resource coordinator for use.
• Then, the coordinator checks for a queue, or issues use.
• If there are any other competing processes, insert contact into a queue and do not respond.
• Tell the coordinator when finished.

Centralized Resource Allocation Requirements

• There are many exclusion requirements that can be given.
• A single process must be allowed to use resource is a safety requirement.
• Liveness is necessary with requested processes . Deadlock is not assured fully otherwise and timeout prevention may be best.
• Honor a timely request before newer request following some delay is a fairness requirement.

Distributed Resource Allocation

• Alternative schemes can be given, when asking to multi contact a all process request while waiting for a reply.
• Responses are given to immediate processes which do not want the resource.
• If there are requests with later receipts or greater use push the processes.
• Then provide resource use when resource gets abandoned .

Token Ring Resource Allocation

• A logical ring token structure can be done where the process '0' starts with a token when algorithm starts.
• Then, passes ring to neighbor processes in adjacent tokens.
• If the resource is desired after reception, utilize such resource and return after completion in the token.
• The token is then used by every resource.

Resource Allocation Algorithm Comparison

Election Algorithms

• Algorithm in the event of failure of a leader or more particularly Burk algorithm is the best selection for a leader.
• Both Bully and Ring are Election Algorithm processes.

Bully Algorithm

• Process receive a unique weight.
• Requests for more processes with higher process stops a controller (sending election to the other processes).
• All elections must answer.
• If a process still hasn't had a response, it indicates completion and the election will begin.

Ring Algorithm

• The process gets a ring structure for what it has.
• The message sent and given to the new logical processes is 'Ring Algorithm'.
• Receive the same message a lot until acknowledgement . The addition ring provides processes.
• Lastly, when a message that needs attention receives that message in a ring and this provides the coordinator.
• Reduces head weight.