CST 402 - DISTRIBUTED COMPUTING

Module - II
 Syllabus Topics

Logical time – A framework for a system of logical clocks, Scalar time; Vector
time. Leader election algorithm – Bully Algorithm, Ring Algorithm. Global
state and snapshot recording algorithms – System model and definitions.
Snapshot algorithm for FIFO channels – Chandy Lamport algorithm.
Termination detection – System model of a distributed computation.
Termination detection using distributed snapshots. Termination detection by
weight throwing, Spanning tree-based algorithm.
 Logical time
▪ Causality between events - fundamental to design and analysis of
parallel and distributed computing and operating systems

▪ Causality -> usually tracked in physical time

▪ In distributed systems,

▪ not possible to have global physical time

▪ we can realize only an approximation of it

▪ asynchronous distributed computations make progress in spurts

▪ the logical time advances in jumps and is sufficient to capture the

ordering associated with causality
 Logical time
▪ Causality (causal precedence relation) among events is a powerful concept in
reasoning, analysing, and drawing inferences about a computation

▪ Causal precedence relation helps solve a variety of problems:

➢ Distributed algorithms design : Fair mutual exclusion algos, correct
deadlock detection algos, consistency in replicated databases

➢ Knowledge about the progress : useful in discarding obsolete info, garbage

collection and termination detection

➢ Tracking of dependent events : Helps to construct consistent states for

resuming re-execution during distributed debugging; helps build checkpoints
in failure recovery; detection of inconsistencies in replicated databases

➢ Concurrency measure
➢ How many events are causally related ->concurrency in the computation
➢ All the events not causally related can be executed concurrently
 Logical time
▪ The concept of causality is widely used by human beings, often
unconsciously, in the planning, scheduling, and execution

▪ In day-to-day life, the global time to deduce causality relation is

obtained from loosely synchronized clocks (i.e., wrist watches, wall
clocks).

▪ In distributed computing systems, the rate of occurrence of events is

several magnitudes higher and the event execution time is several
magnitudes smaller.

▪ Consequently, if the physical clocks are not precisely synchronized,

the causality relation between events may not be accurately
captured
 Logical time
▪ Network Time Protocols
▪ can maintain time accurate to a few tens of milliseconds on the
Internet
▪ not adequate to capture the causality relation in distributed
systems.

▪ In a distributed computation, the progress is made in spurts and the

interaction between processes occurs in spurts

▪ Causality can be accurately captured by logical clocks

 Logical clock
▪ In a system of logical clocks, every process has a logical clock that
is advanced using a set of rules.

▪ Every event is assigned a timestamp and the causality relation

between events can be generally inferred from their timestamps.

▪ The timestamps assigned to events obey the fundamental

monotonicity property -
If an event a causally affects an event b, then the timestamp of a is
smaller than the timestamp of b
 A framework for a system of logical
clocks

Three ways to implement Logical time

1. Scalar time

2. Vector time

3. Matrix Time
 A framework for a system of logical
clocks : Definition
➢ A system of logical clocks consists of a time domain T and a logical clock C

➢ Elements of T form a partially ordered set over a relation ‘< ’

➢ This relation is
➢ usually called the happened before or causal precedence.
➢ analogous to the earlier than relation provided by the physical time.

➢ The logical clock C is a function that maps an event e in a distributed system

to an element in the time domain T, denoted as C(e) and called the
timestamp of e.
 A framework for a system of logical
clocks
➢ The timestamp of e and is defined as follows:
 Implementing logical clocks

▪ Implementation of logical clocks -> two issues

➢Data structures local to every process to represent

logical time

➢A Protocol (set of rules) to update the data structures

to ensure the consistency condition.
Implementing logical clocks contd…
Implementing logical clocks contd…
 Scalar Time
➢ Scalar time representation -> proposed by Lamport in 1978

➢ An attempt to totally order events in a distributed system

➢ Time domain in this representation is the set of non-negative

integers

➢ The logical local clock of a process pi and its local view of the
global time are squashed into one integer variable Ci.
 SCALAR TIME
Rules R1 and R2 to update the clocks are as follows:
 SCALAR TIME
• Figure shows evolution of scalar time with d=1
 SCALAR TIME
Basic properties
1. Consistency property

2. Total Ordering
▪ Scalar clocks can be used to totally order events in a distributed system
▪ The main problem in totally ordering events is that two or more events at
different processes may have an identical timestamp.
 Scalar Time

▪ For two events

▪ A tie-breaking mechanism is needed to order such events

▪ A tie is broken as follows:

▪ Process identifiers are linearly ordered and a tie among events with identical
scalar timestamp is broken on the basis of their process identifiers.
▪ The lower the process identifier in the ranking, the higher the priority.

▪ The timestamp of an event is denoted by a tuple (t, i) where t is its

time of occurrence and i is the identity of the process where it
occurred.
• Total order relation <
• 2 events x and y; timestamps are (h,i) (k,j)

• x < y  ( h< k or (h=k and i < j ) )

• x< y => x→ y V x|| y

 Scalar Time
3. Event counting
➢ If the increment value d =1, the scalar time has the following
property:
➢ if event e has a timestamp h, then h-1 represents the minimum logical
duration, counted in units of events, required before producing the event
e;
➢ We call it the height of the event e.
➢ i.e., h-1 events have been produced sequentially before the event e regardless
of the processes that produced these events.
➢ For e.g. five events precede event b on the longest causal path
ending at b.
Scalar Time
Scalar Time
4. No strong consistency
➢ The system of scalar clocks is not strongly consistent;
that is, for two events ei and ej

➢ The third event of process P1 has smaller scalar Timestamp than the third
event of process P2. However, the former did not happen before the latter.

➢ The reason that scalar clocks are not strongly consistent is that the logical local
clock and logical global clock of a process are squashed into one, resulting in
the loss causal dependency information among events at different processes.
 Vector Time
▪ The system of vector clocks was developed independently by Fidge ,
Mattern, and Schmuck .

▪ In the system of vector clocks, the time domain is represented by a set

of n-dimensional non-negative integer vectors.

▪ Vector Clock: a data structure used for determining the partial

ordering of events in a distributed system and detecting causality
violations

▪ Vector Clocks are used in a distributed systems to determine whether

pairs of events are causally related
Vector Time
Vector Time
Vector Time
 Basic properties
Vector Time
Isomorphism
• relation “→” induces a partial order on the set of events that
are produced by a distributed execution.

• If events in a distributed system are time stamped using a

system of vector clocks, we have the following property.
Vector Time
• Strong consistency
• The system of vector clocks is strongly consistent;
i.e. by examining the vector timestamp of two events, we
can determine if the events are causally related

• For this n = no. of processes in the dc

• Event counting
 Vector Time :Applications

Since vector time tracks causal dependencies exactly, it finds a

wide variety of applications.

▪ distributed debugging
▪ implementations of causal ordering communication
▪ causal distributed shared memory
▪ establishment of global breakpoints
▪ determining the consistency of checkpoints in optimistic
recovery
 Leader election algorithm

▪ An algorithm for choosing a unique process to play a particular role

(coordinator) is called an election algorithm.
▪ All the processes should agree on the choice.

▪ If the process that plays the role of coordinator wishes to retire then
another election is required to choose a replacement.

▪ We say that a process calls the election if it takes an action that initiates
a particular run of the election algorithm.

▪ At any point in time, a process Pi is either a participant – meaning that it

is engaged in some run of the election algorithm – or a non-participant
– meaning that it is not currently engaged in any election.
 Two Election Algorithms

● A ring-based election algorithm

● Bully algorithm
1. A ring-based election algorithm
➢ Each process pi has a communication channel to the next process
in the ring, p(i + 1) mod N
➢ All messages are sent clockwise around the ring.
➢ Goal of this algorithm: To elect a single process called the
coordinator
➢ Initially, every process is marked as a non-participant in an
election.
➢ Any process can begin an election.
➢ It proceeds by marking itself as a participant
➢ placing its identifier in an election message and
➢ sending it to its clockwise neighbour.
➢ When a process receives an election message, it compares the identifier
in the message with its own.
➢ If the arrived identifier is greater, then it forwards the message to its
neighbour.
➢ If the arrived identifier is smaller and the receiver is not a participant, then
➢ it substitutes its own identifier in the message and forwards it;
➢ but it does not forward the message if it is already a participant.
➢ If, the received identifier is that of the receiver itself, then this process’s
identifier must be the greatest, and it becomes the coordinator.
➢ The coordinator marks itself as a non-participant once more and sends an
elected message to its neighbour, announcing its election and enclosing its
identity

➢ On forwarding an election message in any case, the process marks itself

as a participant.
 1. Initially, every process is marked as non-
A ring-based election in progress participant. Any process can begin an election.
2. The starting process marks itself as participant
and place its identifier in a message to its
3 neighbour.
17
3. A process receives a message and compare it
4 with its own. If the arrived identifier is larger, it
passes on the message.
24 4. If arrived identifier is smaller and receiver is not
a participant, substitute its own identifier in the
9 message and forward if. It does not forward the
message if it is already a participant.
1 5. On forwarding of any case, the process marks
itself as a participant.
15 6. If the received identifier is that of the receiver
itself, then this process’s identifier must be the
28 24
greatest, and it becomes the coordinator.
7. The coordinator marks itself as non-participant,
set electedi and sends an elected message to
its neighbour enclosing its ID.
8. When a process receives elected message, it
marks itself as a non-participant, sets its variable
electedi and forwards the message.
2. The bully algorithm

➢ Process with highest id will be the coordinator

➢ There are three types of message in this algorithm:
➢ an election message is sent to announce an election;
➢ an answer message is sent in response to an election message
➢ a coordinator message is sent to announce the identity of the elected
process.

➢ The process that knows it has the highest identifier can elect itself as the
coordinator simply by sending a coordinator message to all processes
with lower identifiers.
➢ A process with a lower identifier can begin an election by sending an
election message to those processes that have a higher identifier and
awaiting answer messages in response.
➢ If none arrives within time T, the process considers itself the
coordinator and sends a coordinator message to all processes with
lower identifiers announcing this.

➢ Otherwise, the process waits a further period T for a coordinator

message to arrive from the new coordinator.

➢ If a process p i receives a coordinator message, it sets its variable

elected i to the identifier of the coordinator contained within it and
treats that process as the coordinator.

➢ If a process receives an election message, it sends back an answer

message and begins another election – unless it has begun one
already.
When a process, P, notices that the coordinator is no longer
responding to requests, it initiates an election.

● P sends an ELECTION message to all processes with higher no.

● If no one responds, P wins the election and becomes a coordinator.

● If one of the higher-ups answers, it takes over. P’ s job is done.

When a process gets an ELECTION message from one of its lower-

numbered colleagues:
● Receiver sends an OK message back to the sender to indicate that
he is alive and will take over.
● Receiver holds an election, unless it is already holding one.
● Eventually, all processes give up but one, and that one is the new
coordinator.
● The new coordinator announces its victory by sending all
processes a message telling them that starting immediately it is the
new coordinator.

If a process that was previously down comes back:

● It holds an election.
● If it happens to be the highest process currently running, it will
win the election and take over the coordinator’ s job.
● Biggest guy” always wins and hence the name “ bully” algorithm.
 The bully algorithm

electi on
1. The process begins an election by C
electi on
sending an election message to these Stag e1
processes that have a higher ID and p answe r
p p p
1 2 3 4
awaits an answer in response. answe r
2. If none arrives within time T, the election

process considers itself the coordinator election electi on C

and sends coordinator message to all Stage2

answe r
p1 p p p
processes with lower identifiers. 2 3 4
3. Otherwise, it waits a further time T’ for p3 fails before it can send
coordinator msg
coordinator message to arrive. If none, timeou t

begins another election. Stage3

p
4. If a process receives a coordinator 1
p
2
p
3
p
4
message, it sets its variable electedi to Eventu ally.....
be the coordinator ID. coord inat or
C
5. If a process receives an election Stag e4
message, it sends back an answer p p p p
1
message and begins another election 2 3 4

unless it has begun one already.

 Ring algorithm – work out
• In a ring topology 7 processes are connected with different
ID’s as shown: P20->P5->P10->P18->P3->P16->P9 If process
P10 initiates election after how many message passes will the
coordinator be elected and known to all the processes. What
modification will take place to the election message as it
passes through all the processes?
• Calculate total number of election messages and coordinator
messages
 P20

P5

P9

P10
P3

P18

P3
 Bully Algorithm – Work out
• Pid’s 0,4,2,1,5,6,3,7
P7 was the initial coordinator and crashed
Illustrate Bully algorithm, if P4 initiates election , Calculate total
number of election messages and coordinator messages
 Global state and snapshot recording algorithms
▪ Recording the global state of a distributed system on-the-fly is an important
paradigm when one is interested in analyzing, testing, or verifying properties
associated with distributed execution

▪ Unfortunately, the lack of both a globally shared memory and a global clock in a
distributed system, added to the fact that message transfer delays in these systems are
finite but unpredictable, makes this problem non-trivial.

▪ A distributed computing system consists of spatially separated processes that do not

share a common memory and communicate asynchronously with each other by
message passing over communication channels

▪ Each component of a distributed system has a local state.

▪ The state of a process is characterized by the state of its local memory and a history
of its activity.

▪ The state of a channel is characterized by the set of messages sent along the channel
 Global state and snapshot recording algorithms
▪ The global state of a distributed system is a collection of the local states of its
components

▪ Recording the global state of a distributed system is an important paradigm

and it finds applications in several aspects of distributed system design

▪ For examples, in detection of stable properties such as deadlocks, and

termination , global state of the system is examined for certain properties;

▪ for failure recovery, a global state of the distributed system (called a

checkpoint) is periodically saved and recovery from a processor failure is done
by restoring the system to the last saved global state

▪ If shared memory were available, an up-to-date state of the entire system

would be available to the processes sharing the memory.

▪ The absence of shared memory necessitates ways of getting a coherent and

complete view of the system based on the local states of individual processes.
 Global state and snapshot recording algorithms
▪ A meaningful global snapshot can be obtained if the components of the
distributed system record their local states at the same time

System model
▪ The system consists of a collection of n processes, p1, p2, , pn, that are
connected by channels.
▪ There is no globally shared memory and processes communicate solely by
passing messages.
▪ There is no physical global clock in the system. Message send and receive is
asynchronous.
▪ Messages are delivered reliably with finite but arbitrary time delay.
▪ The system can be described as a directed graph in which vertices represent
the processes and edges represent unidirectional communication channels.
 Global state and snapshot recording algorithms
System model
▪ 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

▪ The state of channel Cij, denoted by SCij

▪ The actions performed by a process are modeled as three types of events, namely,
internal events, message send events, and message receive events.

▪ For a message mij that is sent by process pi to process pj, let send(mij) and rec(mij)
denote its send and receive events, respectively.

▪ Occurrence of events changes the states of respective processes and channels,

thus causing transitions in the global system state
 Global state and snapshot recording algorithms
▪ For example, an internal event changes the state of the process at which it
occurs.

▪ A send event (or a receive event) changes the state of the process that sends
(or receives) the message and the state of the channel on which the message
is sent (or received).

▪ The events at a process are linearly ordered by their order of occurrence.

▪ At any instant, the state of process pi, denoted by LSi, is a result of the
sequence of all the events executed by pi up to that instant
 Global state and snapshot recording algorithms

A consistent global state

The global state of a distributed system is a collection of the local states of the
processes and the channels. Global state GS is defined as

A global state GS is a consistent global state if it satisfies the following two

conditions
 Global state and snapshot recording algorithms
Interpretation in terms of cuts

▪ Cuts in a space–time diagram provide a powerful graphical aid in representing

and reasoning about the global states of a computation.

▪ A cut is a line joining an arbitrary point on each process line that slices the
space–time diagram into a PAST and a FUTURE.

▪ A consistent global state corresponds to a cut in which every message

received in the PAST of the cut has been sent in the PAST of that cut.

▪ Such a cut is known as a consistent cut.

▪ All the messages that cross the cut from the PAST to the FUTURE are captured
in the corresponding channel state.
 Global state and snapshot recording algorithms
Interpretation in terms of cuts

Cut C1 is inconsistent because message m1 is flowing from the FUTURE to the

PAST
 Global state and snapshot recording algorithms
Issues in recording a global state

▪ If a global physical clock were available, the following simple procedure could be
used to record a consistent global snapshot of a distributed system.

▪ The initiator of the snapshot collection decides a future time at which the
snapshot is to be taken and broadcasts this time to every process.
▪ All processes take their local snapshots at that instant in the global time.

▪ However, a global physical clock is not available in a distributed system and the
following two issues need to be addressed in recording of a consistent global
snapshot of a distributed system

1. How to distinguish between the messages to be recorded in the snapshot

(either in a channel state or a process state) from those not to be recorded
2. How to determine the instant when a process takes its snapshot
 Snapshot algorithms for FIFO channels
Chandy–Lamport algorithm

The Chandy-Lamport algorithm uses a control message, called a marker.

• After a site has recorded its snapshot, it sends a marker along all of its
outgoing channels before sending out any more messages.

• A marker separates the messages in the channel into those to be included in

the snapshot (i.e., channel state or process state) from those not to be
recorded in the snapshot.
 Snapshot algorithms for FIFO channels - Chandy–
Lamport Algorithm
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

The algorithm can be initiated by any process by executing the marker sending rule.

The algorithm terminates after each process has received a marker on all of its
incoming channels.

The recorded local snapshots can be put together to create the global snapshot
 Snapshot algorithms for FIFO channels
Chandy–Lamport algorithm
 Chandy-Lamport Algorithm
The essential idea of the algorithm is as follows:
• Each process records its state and also, for each incoming channel, a set of
messages sent to it.
• The process records, for each channel, any messages that arrived after it
recorded its state and before the sender recorded its own state.
• The algorithm proceeds through use of special marker messages,
– Marker msgs are distinct from any other messages the processes send
– the processes may send and receive markers while they proceed with their
normal execution.
• The marker has a dual role:
– as a prompt for the receiver to save its own state, if it has not already
done so; and
– as a means of determining which messages to include in the channel state.
 Termination Detection
▪ In distributed processing systems, a problem is typically solved in a distributed
manner with the cooperation of a number of processes.

▪ In such an environment, inferring if a distributed computation has ended is

essential so that the results produced by the computation can be used

▪ Messages used for the purpose of termination detection (by a termination

detection algorithm) are called control messages.

A termination detection (TD) algorithm must ensure the following:

1. Execution of a TD algorithm cannot indefinitely delay the underlying

computation; that is, execution of the termination detection algorithm must
not freeze the underlying computation

2. The termination detection algorithm must not require addition of new

communication channels between processes.
 Termination Detection
System model of a distributed computation

▪ A distributed computation consists of a fixed set of processes that

communicate solely by message passing.

▪ All messages are received correctly after an arbitrary but finite delay.

▪ Communication is asynchronous, i.e., a process never waits for the receiver to

be ready before sending a message.

▪ Messages sent over the same communication channel may not obey the FIFO
ordering.
 Termination Detection
System model of a distributed computation

A distributed computation has the following characteristics:

1. At any given time during execution of the distributed computation, a process can
be in only one of the two states: active, and idle.

2. An active process can become idle at any time

3. An idle process can become active only on the receipt of a message from another
process

4. Only active processes can send messages.

5. A message can be received by a process when the process is in either of the two
states.

6. The sending of a message and the receipt of a message occur as atomic actions.
 Termination Detection
System model of a distributed computation
 1. Termination detection using distributed
snapshots

▪ If a consistent snapshot of a distributed computation is taken after the

distributed computation has terminated, the snapshot will capture the
termination of the computation.

▪ The algorithm assumes that there is a logical bidirectional communication

channel between every pair of processes.

▪ Communication channels are reliable but non-FIFO.

▪ Message delay is arbitrary but finite.

 1. Termination detection using distributed
snapshots
Informal description

The main idea behind the algorithm is as follows:

▪ When a computation terminates, there must exist a unique process which became
idle last.

▪ When a process goes from active to idle, it issues a request to all other processes
to take a local snapshot, and also requests itself to take a local snapshot.

▪ When a process receives the request, if it agrees that the requester became idle
before itself, it grants the request by taking a local snapshot for the request.

▪ A request is said to be successful if all processes have taken a local snapshot for it.

▪ The requester or any external agent may collect all the local snapshots of a
request.
 Termination detection using distributed snapshots

Informal description

▪ If a request is successful, a global snapshot of the request can thus be

obtained and the recorded state will indicate termination of the computation.

▪ In the recorded snapshot, all the processes are idle and there is no message in
transit to any of the processes
 2. Termination detection by weight throwing

Rules that define the Algo:

• Rule R1: when a process sends a basic message to any other

process, it sends its logical clock value in the message.

• Rule R2: when a process receives a basic message, it updates its

logical clock based on the clock value contained in the message.

• Rule R3: when a process becomes idle, it updates its local clock,
sends a request for snapshot R(x, k) to every other process, and
takes a local snapshot for this request.
(x = logical clock value, k = process id, R(x, k) = control message)
 2. Termination detection by weight throwing
• Rule R4 (most interesting): On the receipt of a message R(x′ , k′),
1. The process takes a local snapshot if it is idle and (x′, k′) > (x, k), i.e., timing
in the message is later than the local time at the process, implying that the
sender of R(x′, k′) terminated after this process.
In this case, it is likely that the sender is the last process to terminate and thus,
the receiving process takes a snapshot for it. Because of this action, every
process will eventually take a local snapshot for the last request when the
computation has terminated.

2. In the second case, (x′, k′) ≤ (x, k), implying that the sender of R(x′, k′)
terminated before this process.
Hence, the sender of R(x′, k′) cannot be the last process to terminate. Thus,
the receiving process does not take a snapshot for it.

3. In the third case, the receiving process has not even terminated. Hence, the
sender of R(x′, k′) cannot be the last process to terminate and no snapshot is
taken.

• The last process to terminate will have the largest clock value. Therefore, every
process will take a snapshot for it; however, it will not take a snapshot for any
other process.
 2. Termination detection by weight throwing
▪ In termination detection by weight throwing, a process called controlling
agent monitors the computation.

▪ A communication channel exists between each of the processes and the

controlling agent and also between every pair of processes.

▪ Initially, all processes are in the idle state.

▪ The weight at each process is zero and the weight at the controlling agent
is 1.

▪ The computation starts when the controlling agent sends a basic message to
one of the processes.

▪ The process becomes active and the computation starts.

 2. Termination detection by weight throwing
A non-zero weight W (0 < W ≤ 1) is assigned to each process in the active state
and to each message in transit in the following manner:

▪ When a process sends a message, it sends a part of its weight in the message.

▪ When a process receives a message, it adds the weight received in the

message to its weight.

▪ Thus, the sum of weights on all the processes and on all the messages in
transit is always 1.

▪ When a process becomes idle, it sends its weight to the controlling agent in a
control message, which the controlling agent then adds to its weight.

▪ The controlling agent concludes termination if its weight becomes 1.

2. Termination detection by weight throwing
2. Termination detection by weight throwing
 3. A spanning-tree-based termination detection algorithm
▪ The algorithm assumes there are N processes Pi, 0 ≤ i ≤ N, which are modelled as
the nodes i, 0 ≤ i ≤ N, of a fixed connected undirected graph.

▪ The edges of the graph represent the communication channels, through which a
process sends messages to neighbouring processes in the graph.

▪ The algorithm uses a fixed spanning tree of the graph with process P0 at its root
which is responsible for termination detection

▪ Process P0 communicates with other processes to determine their states and the
messages used for this purpose are called signals.

▪ All leaf nodes report to their parents, if they have terminated.

▪ A parent node will similarly report to its parent when it has completed processing
and all of its immediate children have terminated, and so on.

▪ The root concludes that termination has occurred, if it has terminated and all of its
immediate children have also terminated
 3. A spanning-tree-based termination detection algorithm
▪ The termination detection algorithm generates two waves of signals moving
inward and outward through the spanning tree.

▪ Initially, a contracting wave of signals, called tokens, moves inward from

leaves to the root.

▪ If this token wave reaches the root without discovering that termination has
occurred, the root initiates a second outward wave of repeat signals.

▪ As this repeat wave reaches leaves, the token wave gradually forms and starts
moving inward again.

▪ This sequence of events is repeated until the termination is detected

3. A spanning-tree-based termination detection algorithm
 3. A spanning-tree-based termination detection algorithm
• Initially, each leaf process is given a token.

• Each leaf process, after it has terminated, sends its token to its parent.

• When a parent process terminates and after it has received a token from
each of its children, it sends a token to its parent.

• This way, each process indicates to its parent process that the subtree
below it has become idle.

• In a similar manner, the tokens get propagated to the root.

• The root of the tree concludes that termination has occurred, after it has
become idle and has received a token from each of its children.
3. A spanning-tree-based termination detection algorithm
3. A spanning-tree-based termination detection algorithm
3. A spanning-tree-based termination detection algorithm
3. A spanning-tree-based termination detection algorithm
3. A spanning-tree-based termination detection algorithm
3. A spanning-tree-based termination detection algorithm
3. A spanning-tree-based termination detection algorithm
 Tutorial Questions
A. Logical Time B. Leader Election Algorithms
Q1. Lamport Clock Application Q3. Bully Algorithm Execution
A distributed system has three processes P1, A distributed system has five processes
P2, and P3. with IDs {2, 4, 6, 8, 10}.
The initial clock value of each process is 0. Process 10 (leader) fails, and
P1 executes internal event e1 and sends a process 4 detects the failure.
message to P2 Apply the Bully algorithm to:
P2 executes internal event e2 after receiving the List the messages exchanged
message Identify the new leader
P2 sends a message to P3 Q4. Ring Algorithm Execution
P3 executes internal event e3 after receiving the Consider a ring of six processes with IDs {1,
message 3, 5, 7, 9, 11}.
Apply Lamport’s scalar clock rules to assign Process 7 initiates a leader election.
timestamps to all events in the space-time Apply the Ring algorithm and show:
diagram. The order in which messages circulate
Q2. Vector Clock Application
The process elected as leader
For the same system in Question 1, apply vector
clock rules and assign vector timestamps to
each event.
Using the timestamps, identify whether any
two events are concurrent.
 Spanning Tree Workout
• Apply spanning tree-based termination
detection algorithm in the following scenario.
The nodes are processes 0 to 6. Leaf nodes 3,
4, 5, and 6 are each given tokens T3, T4, T5
and T6 respectively. Leaf nodes 3, 4, 5 and 6
terminate in the order, but before terminating
node 5,it sends a message to node 1