UNIT-II

Logical time – Scalar Time – Vector Time - Efficient implementations of vector clocks – Virtual
Time. Global state and snapshot recording algorithms: System model - Snapshot algorithms for
FIFO channels and non-FIFO channels.

Explain Logical Clock with example.

Logical clock

Logical clocks are based on capturing chronological and causal relationships of processes and
ordering events based on these relationships.

Three types of logical clock are maintained in distributed systems:

 Scalar clock
 Vector clock
 Matrix clock

Scalar clock

 Scalar time is designed by Lamport to synchronize all the events in distributed systems.
 A Lamport logical clock is an incrementing counter maintained in each process.
 When a process receives a message, it resynchronizes its logical clock with that
sender maintaining causal relationship.

The Lamport’s algorithm is governed using the following rules

 All the process counters start with value 0.

 A process increments its counter for each event (internal event, message
sending, message receiving) in that process.
 When a process sends a message, it includes its incremented counter value with the message.
 On receiving a message, the counter of the
recipient is updated by Max(receiver –
counter,message-timestamp)+1
Basic properties of scalar time

1.Consistency property:

Scalar clock always satisfies monotonicity. C(ei) < C(ej)

2. Total Reordering:

Scalar clocks order the events in distributed systems.But all the events do not follow a common identical
timestamp. Hence a tie breaking mechanism is essential to order the events. The tie breaking is done
through:

 Linearly order process identifiers.

 Process with low identifier value will be given higher priority.

3. Event Counting

Event Counting represents the number of events executed by process.

Vector clock

 Vector Clocks use a vector counter instead of an integer counter.

 The vector clock of a system with N processes is a vector of N counters, one counter per process.

Vector counters have to follow the following update rules:

 Initially, all counters are zero.

 Each time a process experiences an event, it increments its own counter in the vector by one.

 Each time a process sends a message, it includes a copy of its own

(incremented) vector in the message.
 Each time a process receives a message, it increments its own counter in the
vector by one and updates each element in its vector by
Basic Properties of Vector Clock

1. Isomorphism:
 If events in a distributed system are timestamped using a system of vector clocks, we have the following
property.
 If two events x and y have timestamps vh and vk, respectively, then

2. Strong consistency

 The system of vector clocks is strongly consistent; thus, by examining the vector timestamp
of two events, we can determine if the events are causally related.

3. Event Counting

 Event Counting represents the number of events executed by process.

Global state and snapshot recording algorithms

System Model

 The system consists of a collection of n processes, p1, p2,…, pn that are connected
by channels.
 Let Cij denote the channel from process pi to process pj.
 Processes and channels have states associated with them.
 The state of a process at any time is defined by the contents of processor
registers, stacks, local memory, etc.,
 The state of channel Cij, denoted by SCij, is given by the set of messages in
transit in the channel.
 In the FIFO model, each channel acts as a first-in first-out message queue and, thus,
message ordering is preserved by a channel.
 In the non-FIFO model, a channel acts like a set in which the sender process adds
messages and the receiver process removes messages from it in a random order.

A consistent global state

The global state of a distributed system is a collection of the local states of the processes and the
channels. The global state is given by:

The two conditions for global state are:

 Consistent global state

A message cannot be received if it was not sent; that is, the state should not violate causality. Such
states are called consistent global states.

Inconsistent global state

An inconsistent global state in a distributed system is a snapshot of the system that violates causality
and does not represent a valid state the system could achieve during its execution.

Explain Snapshot algorithms for FIFO channels in detail.

 A snapshot captures the local states of each process along with the state of each
communication channel.
 Snapshots are required to:
 Check pointing
 Collecting garbage
 Detecting deadlocks
 Debugging

Chandy–Lamport algorithm
 Chandy–Lamport algorithm records a set of process and channel states such that the combination is a
global state. Communication channels assumed to be FIFO.

Assumptions
 No Failure in process and channels
 Communication channels are unidirectional and FIFO channels
 There is a communication channel between each pair of processes.
 Any process may initiate the snapshot.

The Algorithm

 A process initiates snapshot collection by executing the marker sending rule by which it records
its local state and sends a marker on each outgoing channel.
 A process executes the marker receiving rule on receiving a marker. If the process has not yet
recorded its local state, it records the state of the channel on which the marker is received as
empty and executes the marker sending rule to record its local state.
 Otherwise, the state of the incoming channel on which the marker is received is recorded as the
set of computation messages received on that channel after recording the local state but
before receiving the marker on that channel.
Example:

Process p1 records its state in the actual global state S0 , when the state of p1 is <$1000,
0>.Following the marker sending rule, process p1 then emits a marker message over its outgoing
channel c2 before it sends the next application-level message: (Order 10, $100), over channel c2 .
The system enters actual global state S1. Before p2 receives the marker, it emits an application
message (five widgets) over c1 in response to p1’s previous order, yielding a new actual global state
S2 .Now process p1 receives p2’s message (five widgets), and p2 receives the marker. Following the
marker receiving rule, p2 records its state as <$50, 1995> and that of channel c2 as the empty
sequence. Following the marker sending rule, it sends a marker message over c1 .When
 process p1 receives p2 ’s marker message, it records the state of channel c1 as the single
message (five widgets) that it received after it first recorded its state. The final recorded state
is p1 : <$1000, 0>; p2 : <$50, 1995>; c1 : <(five widgets)>; c2 : < >. Note that this state differs
from all the global states through which the system actually passed.

Explain Snapshot algorithms for non-FIFO channels in detail.

Lai–Yang Algorithm
 The Lai–Yang algorithm is a distributed snapshot algorithm for non-FIFO systems.
 It uses a coloring scheme to ensure consistent snapshots without requiring explicit marker
messages.
The Lai-Yang Algorithm works as follows to capture a consistent global snapshot in distributed
system:
 Every process is initially white.
 A process turns red when it takes its local snapshot.
 Messages sent by white processes are colored white.
 Messages sent by red processes are colored red.
 A white message represents a message sent before the sender recorded its local snapshot.
 A red message represents a message sent after the sender recorded its local snapshot.
 A white process takes its local snapshot at a convenient time.
 However, a white process must take its snapshot before processing a red message.
 Each white process records the history of all white messages it sends or receives along its
communication channels.
 When a process turns red, it sends its local snapshot and the recorded histories of white
messages to the initiator process.
 The initiator process is responsible for collecting these snapshots and computing the global
state.
 The initiator process compute the state of a channel Cij as given below:

SCj = white messages sent by Pi on Cij – white messages received by Pj on Cij

Mattern’s Algorithm
Mattern’s algorithm is based on vector clocks. All process agree on some future virtual time s or a set
of virtual time instants s1 ,…Sn which are mutually concurrent and did not yet occur.
Mattern’s algorithm assumes a single initiator process and works as follows:
 1. Pi ticks and then fixes its next time s=Ci +(0,…,0,1,0,…,0) to be the common snapshot time
2. Pi broadcasts s.
3. Pi blocks waiting for all the acknowledgements.
4. Pi ticks again (setting Ci =s), takes its snapshot and broadcast a dummy message.
5. Each process takes its snapshot and sends it to Pi when its local clock becomes ≥S.
6. Picollects all local snapshots from the processes.
7. The collected snapshots and the coordinated snapshot time sss are used to construct a
global snapshot.

Explain efficient implementations of vector clocks in detail.

 If the number of processes in a distributed computation is large, then vector clocks will require
piggybacking of huge amount of information in messages
 The message overhead grows linearly with the number of processors in the system and when
there are thousands of processors in the system, the message size becomes huge even if there
are only a few events occurring in few processors.
 We discuss an efficient way to maintain vector clocks.

Singhal-Kshemkalyani’s Differential Technique

1.In this technique, when a process pi sends a message to a process pj, it piggybacks only those
entries of its vector clock that differ since the last message sent to pj.

2.If entries i1, i2. . . in1 of the vector clock at pi have changed to v1, v2, . . . , vn1 , respectively, since the
last message sent to pj , then process pi piggybacks a compressed timestamp of the form:

to the next message to pj .

3. When pj receives this message, it updates its vector clock as follows:

2. Fowler–Zwaenepoel’s direct-dependency technique

Fowler–Zwaenepoel direct dependency technique reduces the size of messages by transmitting only
a scalar value in the messages.
 Explain Virtual Time in detail.

 Virtual Time is a conceptual framework for tracking and coordinating events in a distributed
system.
 It provides a global, one-dimensional temporal coordinate system to measure progress and
define synchronization across processes.
 In a distributed system, processes run concurrently and communicate with each other by
exchanging messages.
 Every message is characterized by four values:
1. name of the sender
2. virtual send time
3. name of the receiver
4. virtual receive time
 Virtual send time is the virtual time at the sender when the message is sent, whereas virtual
receive time specifies the virtual time when the message must be received by the receiver.

Virtual time systems are subject to two semantic rules

Rule 1:
Virtual send time of each message < virtual receive time of that message.
Rule 2:
Virtual time of each event in a process < virtual time of next event in that process.

Characteristics of virtual time

1. Virtual time systems are not all isomorphic; they may be either discrete or continuous.
2. Virtual time may be only partially ordered .
3. Virtual time may be related to real time or may be independent of it.
4. Virtual time systems may be visible to programmers and manipulated explicitly as values, or
hidden and manipulated implicitly according to some system-defined discipline
5. Virtual times associated with events may be explicitly calculated by user programs or they may be
assigned by fixed rules.