Unit –III

Distributed Snapshot
 Introduction
• Sometimes you want to collect the current state of the distributed computation, called
Distributed Snapshot.
• Computation is a sequence of atomic actions that transforms a given initial state to
the final state.
• While such actions are totally ordered in a sequential process, they are only partially
ordered in a Distributed System.
• It is customary to reason about the properties of a program in terms of states and
state transitions.
• In distributed snapshot, state is also called as global state.
• The global state of a distributed computation is the set of local states of all individual
processes involved in the computation plus the state of the communication channel.
• Since the local physical clocks are never perfectly synchronized, the components of a
global state can never be recorded at the same time.
• In an asynchronous distributed system, actions are not related to time.
 Requirement of Global States
Distributed Garbage Collection:
• An object is considered to be garbage if there are no longer any references to it
anywhere in the distributed system.
• It is based on the reference counting and should include the state of communication
channels.
 Requirement of Global States
Distributed Deadlock Detection:
• It occurs when each of collection of processes waits for another process to send it a
message and look for “waits-for” relationship.

Distributed Termination Detection:

• Look for state in which all processes are passive.

Distributed Debugging:
• Need collect values of distributed variables at the same time.
 Properties of Consistent Snapshot
• The global state of a distributed system is a collection of the local states of the
processes and the channels.
• Operating system cannot know the current state of all process in the DS.
• A process can only know the current state of all processes on the local system.
• Remote processes only know state information that is received by messages.

Need for Global States:

• Many problems in distributed computing can be cast as executing some action on
reaching a particular state.
• Below diagram shows the stages of a computation of when $100 is transferred from
account A to account B.
• The communication channel C1 and C2 are assumed to be FIFO.
 Properties of Consistent Snapshot

• Bank account is distributed over two branches (A and B).

• The total amount in the account is the sum at each branch.
• At 3pm the account balance is determined.
 Properties of Consistent Snapshot
• Messages are sent to request the information.
• If at the time of balance determination, the balance from branch A is in transit to
branch B.
• The result is a false reading.
• All messages in transit must be examined at time of observation.
• Total consists of balance at both branches and amount in message.
• Each amount sent and just received, must be added only one time.
 Properties of Consistent Snapshot
• If clocks at the two branches are not perfectly synchronized then the transfer amount
at 3:01 from branch A.
• The amount arrives at branch B at 2:59.
• At 3:00 the amount is counted twice.
 Common Terminologies for Snapshot
Channel:
• Exists between two processes if they exchange messages.

State:
• Sequence of messages that have been sent and received along channels incident with
the process.

Snapshot:
• Records the state of a process.

Distributed Snapshot:
• A collection of snapshots, one for each process.
 Global State
• We can define the global state with the union of all the snapshots.
• To have a global consistent state then process state has registered a received message,
the sending process state must own this message.
• Useful to adapt any centralized algorithm over a DS.
• Sometimes you want to collect the current state of the distributed computation, called
Distributed Snapshot.
• It consists of all local states and messages in transit.
• Global state of a distributed system consist of the local state of each process, together
with the messages that are currently in transit (sent but not delivered).
• A distributed snapshot should reflect a consistent state.
• The notation of the Global state can be graphically represented by what is called a cut.
• Diagram shows the consistent and non- consistent cut.
 Global State

Cut:
• A cut is a set of cut events, one per node, each of which captures the state of the node
on which it occurs.
 Global State
• In a consistent cut it is possible to have the sending of a message before a cut, but the
receiving of that message after the cut.
• That means, when considering consistent cuts we have also to worry about and save
the ‘ in transit’ messages, ie. Messages sent before the cut but received after the cut.

Example of a cut:
• Consider this solution for the common problem of deadlock detection.
• System has 3 processes P1, P2, P3.
• An external process P0 sends a message to each process.
• Each process on getting this message reports its local state.
• This global state thus collected at P0 is a cut.
• P0 uses this information to create a wait for graph.
 Global State

• A cut C is consistent if for all events e and e’ (e ∈ C) Ʌ (e’  e) ⇒ e’ ∈ C

• Intuitively if an event is part of a cut then all events that happened before it must also
be part of the cut.
 Chandy-Lamport Algorithm
• Chandy-Lampory algorithm records a set of process and channel states such that the
combination is a consistent global state.
• Here, communication channels assumed to be FIFO.

Assumptions for Algorithm:

 No failure, all messages arrive intact, exactly once
 Communication channels are unidirectional and FIFO – ordered
 There is a communication channel between each pair of processes
 Any process may initiate the snapshot
 Snapshot does not interfere with normal execution
• The Chandy - Lamport algorithm uses a control message, called a marker whose role
in a FIFO system is to separate messages in the channels.
 Chandy-Lamport Algorithm
• After the 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 from those not to be recorded in the snapshot.
• A process must record its snapshot no later than when it receives a marker on any of
its incoming channels.

Algorithm:
• Initiator process P0 records its state locally
• Marker sending rule for process Pi:
After Pi has recorded its state, for each outgoing channel Chij, Pi sends one marker
message over Chij
 Chandy-Lamport Algorithm
• Marker receiving rule for process Pi :
Process Pi on receipt of a marker over channel Chij
If (Pi has not yet recorded its state) it,
Records its process state now;
Records the state of Chij as empty set;
Starts recording messages arriving over other incoming channels;
else(Pi has already recorded its state)
Pi records the state of Chij as the set of all messages it has received over Chij since it
saved its state.
 Lai - Yang Algorithm
• The Lie - Yang algorithm fulfills this role of a marker in a non FIFO system by using a
coloring skill on computation messages that works as follows messages:
1: Every process is initially white it and turns read while taking a snapshot. The
equivalent of the "Marker Sending Rule" is executed when a process turns red.

2: Every message sent by a white/(red) process is colored white/(red).

3: Thus, a white/(red) message in a message that what sent before/(after) the sender
of the message recorded its local snapshot.

4: Every white process takes its snapshot at its convenience, but no later than the
instant it receives a red message. Every white process records a history of all white
messages sent or received buy it along each channel.
 Lai - Yang Algorithm
5: When a process turns red, it sends the histories along with its snapshot to the
initiator process that collects the Global snapshot.

6: The initiator process evaluates transit (LSi, LSj) to 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

• Thus, when a white process receives a read message, it records its local snapshot
before processing the message.
• This ensures that no message sent bi a process after recording its local snapshot is
processed by a destination process before the destination records its local snapshot.
 Lai - Yang Algorithm
• Thus, an explicit marker message is not required in this algorithm and the marker is
piggybacked on computation messages using a coloring scheme.
• Though marker messages are not required in the algorithm, each process has to
record the entire message history on each channel as part of the local snapshot.
• Thus the space requirements of the algorithm may be large.
• Lai and Yang describe how the size of the local storage and snapshot recording can be
reduced by storing only the messages sent and received since the previous snapshot
recording, assuming that the previous snapshot is still available.
• This approach can be very useful two applications that required repeated snapshot of
a distributed system.
 Distributed Debugging
• To examine the problem of recording a system’s global state so that we may make
useful statements about whether a transitory state – as opposed to a stable state –
occurred in an actual execution.
• We can determine whether the system is stable or transitory in an execution.
• This is what we require, debugging a DS.
• Practical example is a DS controlling a system of pipes in a factory where we are
interested in whether all the valves (controlled by different processes) were open at
some time.
• In this examples, we cannot in general observe the states of the valves simultaneously.
• The challenge is to monitor the system’s execution over time – to capture ‘trace’
information rather than a single snapshot.
• So that we can establish post hoc whether the required safety condition was or may
have been violated.
 Distributed Debugging
• According to Chandy and Lamport’s snapshot algorithm, collects state in a
distributed fashion, and we pointed out how the processes in the system could send the
state they gather to a monitor process for collection.
• The algorithm we describe next (Marzullo and Neiger [1991]) is centralized.
• The observed processes send their states to a process called a monitor, which
assembles globally consistent states from what it receives.
• We consider the monitor to lie outside the system, observing its execution.
• Our aim is to determine cases where a given global state predicate φ was definitely
True at some point in the execution we observed, and cases where it was possibly True.
• The notion ‘possibly’ arises as a natural concept because we may extract a consistent
global state S from an executing system and find that φ(S) is True.
• No single observation of a consistent global state allows us to conclude whether a
non-stable predicate ever evaluated to True in the actual execution.
 Distributed Debugging
Notations
• φ : a global state predicate
• Possibly φ : There is a consistent global state S through which a linearization of H
(history) passes such that φ(S) is True.
• Definitely φ : All linearization's of H passes such that φ(S) is True.
• Evaluating possibly φ entails search through all consistent Global States derived from
the observed execution.
• Processes may react to what condition is being tested for and respond accordingly.
• The monitor must assemble consistent Global States against which it evaluates φ.
• The monitor uses the vector clock values of each message to determine the consistent
Global state.
 Distributed Debugging
For possibly φ
• The monitor process starts at the initial state and steps through all consistent States
reachable from that point, evaluating φ at each state. When φ is true, it stops.

For definitely φ
• The monitor process must attempt to find a set of states to which all linearization's
must pass, and at each of which φ is true.

Cost of Distributed Debugging

• Development of code to respond to the snapshot request, with different variables.
• Processing of the request and messaging cost to the monitor.
• Cost of comparing all the states of each of the observed processes.
• It also consider space of storing all the values for comparison.
 Distributed Debugging
Debugging in Synchronous System
• An asynchronous system requires the vector timestamps to determine a consistent
Global state.
• A synchronous system can send vector timestamps to the monitor.
• The monitor can then determine more accurately whether events occurred
simultaneously, crossed paths etc.
 Global States Collection
• In a distributed system, each process evaluates actions on the basis of local
information that consist of its own state, and neighbor's state or messages through the
incoming channels.
• Many applications need to find out the Global state of the system by collecting the
local States of the component processes. These include;
1. Computation of the network topology.
2. Counting the number of processes in a distributed system.
3. Detecting termination.
4. Detecting deadlock.
5. Detecting loss of coordination .
• The algorithms for global state collection are divided into to probe-echo algorithm,
wave algorithm, and heartbeat algorithm.
 Global States Collection
• Let us consider, strongly connected N processes network.
• Processes are numbered from process_0 to process_N-1.
• Each process has a stable value s(i) associated with it.
• The goal is to devise an algorithm by which every process i can broadcast its value s(i)
to every other process in this system.
• At the end, each process i will have a set V.
i = { ∀ k : 0 ≤ k ≤ N -1 : s(k)}.
• One-way to perform and all-to-all broadcast is to perform p one-to-all broadcasts, one
starting at each node.
• If performed naively, on some architecture this approach may take up to p times as
long as a one-to-all broadcast.
 Global States Collection
• It is possible to use the communication links in the interconnection network more
efficiently by performing all p one-to-all all broadcasts simultaneously so that all
messages traversing the same path at the same time are connected into a single
message whose size is the sum of the sizes of individual messages.
• To complete the broadcast, every process i will periodically send its current (Vi) along
each of its outgoing channel, and receive whatever values have been received by it
along the incoming channels to update Vi.
• The operation resembles the pumping of blood in the heart, so these type of
algorithms are called heartbeat algorithms.
 Termination Detection Algorithm
• In distributed processing systems, inferring that a distributed computation has ended
is essential so that the results produced by the protocol can be used.
• Conventionally, in the fault free case, the underlying system is said to be terminated if,
1. All its process are idle
2. No message in transmitted
• The messages transmitted by underlying system as the basic message.
• The detector may send extra message called control message.
• Termination: Completion of the sequence of algorithm. (E.g.) leader election, deadlock
detection, deadlock resolution.
• Use a controlling agent or a monitor process.
• Initially, all processes are idle, weight of controlling agent is 1 (0 for others).
• Start of computation: Message from controller to a process, weight split into half (0.5
for each).
 Termination Detection Algorithm
• Repeat this: Anytime a process send a computation message to another process, split
the weights between the two processes (e.g. 0.25 each for the third time).
• End Of Computation: Process sends its weight to the controller. Add this weight to
that of controller's.(Sending process's weight becomes 0).
• Rule: Sum of W always 1.
• Termination: When width of controller becomes 1 again.

Huang’s Algorithm:
• Huang's algorithm is used to solve this problem.
• Huang's algorithm can be described by the following,
a. Initially all processor idle.
 Termination Detection Algorithm
b. A distributed task is started by a process sending a computational message to
another process. This initial process is send the message is the "controlling agent". The
initial weight of the controlling agent is usually 1.
c. The following rules are applied throughout the computation,
i. A process sending a message splits its current weight between itself and the
message.
ii. A process receiving a message add the weight of the message to itself.
iii. Upon becoming idle, a process sends a message containing its entire weight
back to the controlling agent.
iv. Termination occurs when the controlling agent has a weight of and is in the idle
state.
 Termination Detection Algorithm
•
 Dijkstra – Scholten Algorithm
Diffusion Algorithms:
• In a Diffusion algorithm A the activity begins by some pre-specified source node pi
diffuses through some portion of the network via messages.
• A Global state of A is said to be quiescent provided that no process is enabled to
perform any state and there are no messages in the channels.

Termination-Detection Problem for A:

• If, sometimes after the initiation of A by process pi, A ever richest a quiescent global
state, then eventually pi most determined termination why setting a local variable done
to have the value TRUE.
 Dijkstra – Scholten Algorithm
Dijkstra – Scholten Algorithm Main Idea:
• Each process other than the source designates the neighbor from which it first
receives message as its parent in the spanning tree.
• Any subsequent message is immediately acknowledged, only the first remains
unacknowledged.
• The source process immediately acknowledges any message it receives.

Algorithm:
• Execute A as usual, adding acks for all messages.
• Messages of A of treated like search messages in AsynchSpanningTree.
• When a process receives an external input, it becomes the root, and begins executing
A.
 Dijkstra – Scholten Algorithm
• When any non-root process receives its first A message, it designates the sender as its
parent in the tree, and begins participating in A.
• Root process acks every message immediately.
• Other processes acks all but the first message immediately.

• Dijkstra – Scholten algorithm is an example of a probe-echo algorithm, the signals are

the probes, and the acknowledgements are the echoes.
 Wave Algorithm
• The wave algorithms is very important for message passing schemes.
• A wave algorithm is a distributed algorithm that satisfies the following three
requirements:
i. Termination: Each computation is finite.
ii. Decision: Each computation contains at least one decide event.
iii. Dependence: In each computation each decide event is causally preceded by
an event in each process.
Need of Wave Algorithm:
• First, the introduction of the concept facilitates the later treatment war involved
algorithms because the properties of their subroutines have already been studied.
• Second, certain problems in distributed computing can be solved by generic
Constructions that yield a specific algorithm when parameterized with a specific wave
algorithm.
 Wave Algorithm
• Examples of algorithms are ring algorithm, tree algorithm, echo algorithm.

Traversal Algorithm:
• A traversal algorithm is a centralized wave algorithm, i.e. There is one initiator, which
sends around a token.
• It representing a combined send and receive event.
• In each computation, the token first visits all processes.
• Finally, a decide event happens at the initiator, who at that time holds the token.
• In traversal algorithms, the father of non initiator is the neighbor from which it
received the token first.
 Wave Algorithm
Echo Algorithm:
• The echo algorithm is a centralized wave algorithm for undirected graphs.
1. Initiator sends a message to all neighbors.
2. The father of a non initiator is the neighbor from which it receives the first
message.
3. A non initiator sends a message to all neighbors except its father.
4. When a non initiator has received a message from all neighbors, it sends a
message to its father.
5. When the initiator has received a message from all neighbors, it decides.
• The Echo algorithms consist of two phases or waves; a forward wave of explorer
messages which spread through a net, and a backward wave of echo messages which
is created give the explorer wave front hits the border of the net.
 Wave Algorithm
• The explorer wave travels from the initiator to the border of the distributed system
and can be used to disseminate information, the Echo wave travels from the border of
the system back to the initiator and can be used to collect information from the system.
• During the propagation of the first Explorer wave, a spanning tree is constructed
which consists of all the predecessor nodes store in the parameter "pred" at each node.
• The Echo wave travels back along this spanning-tree to the initiator.
• If it reaches the initiator, the algorithm is terminated.
• Given a General graph with intelligent nodes which can communicate along its edges,
the first idea is that message passing is the fundamental operation of any echo
algorithm.
• Traversal of the graph therefore means passing messages from one node to another.
• For any particular node i which starts the execution of an echo algorithm, the
messages originating from i form a family, sharing the identity of i in common.
 Wave Algorithm
Distribution of list among the nodes in a mesh network :
• Each node in the network should be given a unique number.
• This will be distributed by the node S that when the algorithm starts.
• And doesn't know which nodes there are in the network.

Phase 1:
1. S starts an echo algorithm.
2. Each leaf node return the value 1 in its ECHO.
3. Each ECHO send back on a link that is not FL returns the value 0.
4. Each node register the return values for ECHO's for the corresponding links.
5. When a node has got all ECHO messages it returns an ECHO on its FL containing
the sum value of all its return values + 1(for itself).
6. When the initiating node S, has got ECHOs on all its links it knows how many
nodes that are present in the network at the given moment.
 Wave Algorithm
Phase 2:
7. The initiating node creates as many unique identifiers that are nodes in the
network and send them on its links to its neighbors.
Each link message get the number of identifier as was given in corresponding
ECHO.
8. Each other node will get a message with Unique Identities on its FL (the FL of
Phase 1).
The node keeps one of the identities and sends the rest on its links according to
the corresponding registered number of nodes. Each link gets as many as it
indicated in its ECHO.
9. Echo messages can optionally be sent back so the initiator node can get a
confirmation that the algorithm has terminated.
 Unit –III

Distributed Deadlock Detection

 Distributed Deadlock Detection
• A Distributed system consists of a number of sites connected by a network.
• Each site maintains some of the resources of the system.
• Processes with a globally unique identifier run on the distributed system.
• They make resource request to a controller.
• There is one controller per site.
• If the resource is local, the process makes the request of the local controller.
• If the desired resource is at a remote site, the process sends a message.
• After a process makes a request, but before it is granted, it is blocked and said to be
dependent it on the process that holds the desired resource. The controller at each site
could maintain a WFG (Wait-For-Graph) on the process request that it knows about.
• This is an local WFG.
• However, each site's WFG could be cycle free and yet the distributed system could be
deadlocked. This is called Global deadlock.
 Distributed Deadlock Detection
• This would occur in the following situation,
1. Process A at site 1 holds a lock on resource X.
2. Process A has requested, but has not been granted, resource Y at site 2.
3. Process B at site 2 holds a lock on resource Y.
4. Process B has requested, but has not been granted, resource X at site 1.
• Both processes are blocked by the other one.
• There is a global deadlock.
• However, the deadlock will not be discovered at either site unless they exchange
information via some detection scheme.
 Resource V/s Communication Deadlock
• People sometimes might classify deadlock into the following types,

Resource deadlock:
• Set of deadlocked processes of, where each process waits for resource held by
another process (e.g. Data object in a database, I/O resource on a server).
• This uses AND condition.
• AND condition : A process that requires resources for execution can proceed when it
has acquired all those resources.
• The condition for deadlock in a system using the AND condition is the existence of a
cycle.
 Resource V/s Communication Deadlock
Communication deadlock:
• Set of deadlocked processes, where each process waits to receive messages
(communication) from other processes in the set.
• This uses OR condition.
• OR condition: A process that requires resources for execution can proceed when it has
acquired at least one of those resources.
• The condition for deadlock in a system using the OR condition is the existence of a
knot.
• A knot (K) consists of a set of nodes such that for every node A in K, all nodes in K and
only the nodes in K are reachable from node A.
 Detection of Resource Deadlock
• The state of process - resource interaction in distributed systems can be modeled by
a bi-partite directed graph called a resource allocation graph.
• The nodes of the graph are processes and resources of a system, and edges of the
graph depict assignments for pending requests.
• A pending request is represented by request edge directed from the node of a
requesting process to the node of the requested resource.
• A resource assignment is represented by an assignment edge directed from the node
of an assigned resource to the node of the assigned process.
• A system is deadlocked if its resource allocation graph contains a directed cycle or a
knot.
 Detection of Resource Deadlock

• Diagram shows Resource Allocation Graph.

• In DS, the system state can be modeled or represented by a directed graph, called a
Wait-For-Graph (WFG).
• In a WFG, nodes are processes and there is a directed edge from node P1 to P2 if P1 is
blocked and is waiting for P2 to release some resource.
• A system is deadlocked if and only if there is a directed cycle or not ( depending upon
the underlying model) in the WFG.
 Detection of Resource Deadlock

• Resulting Wait For Graph of resource allocation graph is shown in diagram.

 Coordination Algorithms
• Fundamental issue in DS is for a set of processes, how to coordinate their actions on
one or more values.
• Further issue is how to consider and deal with failures when designing algorithms.
• So we need to focus on the goals of the problems of coordination and agreement in DS,
and algorithmic techniques for addressing the problems.
• More specifically, to introduce algorithms for distributed mutual exclusion and
election algorithms, for multicast communication, consensus and related problems.
• Failure detectors have both a practical and a theoretical importance.
• they are of practical importance because many systems have to cope with failures and
therefore to detect them, however reliably or unreliably.
• They are of theoretical importance because the presence of a failure detector with
well defined properties affects our ability to solve the problem of consensus.
 Coordination Algorithms
• Distributed mutual exclusion is needed when processes access a resource or
collection of resources and we require their updates to be consistent.
• Algorithms to achieve distributed mutual exclusion must be evaluated on the basis of
their efficiency and their behavior under failure conditions.
• Election algorithms are required when there is a need to distinguish one of the
collection of processes as a coordinator.
• These algorithms are designed to select a unique process, even under failure
conditions.
• In multicast communication we make a strong distinction between multicast
properties and how to implement those properties.
 Leader Elections
• Many distributed algorithms require one process to act as coordinator, initiator or
otherwise perform some special role.
• It does not matter which process take on this special responsibility, but one of them
has to do it.
• If all processes are exactly the same, with no distinguishing characteristics, there is no
way to select one of them to be special.
• In general, election algorithms attempt to locate the process with the highest process
number and designate it as coordinator.
• The goal of an election algorithm is to ensure that when an election starts, it
concludes with all processes agreeing on who the new coordinator is to be.
 The Bully Algorithm
• When any process notices that the coordinator is no longer responding to request, it
initiate an election.
• A process P, holds an election as follows;
1. P sends an ELECTION message to all processes with higher numbers.
2. If no one responds, P wins the election and becomes coordinator.
3. If one of the higher-ups answers, it takes over, P’s job is done.

• Diagram shows the Bully algorithm. The group consist

of eight processes, numbered from 0 to 7.
• Previously process 7 was the coordinator, but it has
just crashed.
• Process 4 is the first one to notice this, so it sends
ELECTION message to all the processes higher than it,
i.e. 5, 6, and 7.
 The Bully Algorithm
• Process 5 and 6 both respond with OK, as shown in dia.
• Upon getting the first of these responses, 4 knows that
its job is over.
• it knows that one of these will take over and become
coordinator.

• Beside in the diagram, both 5 and 6 hold elections,

each one only sending messages to those processes
higher that itself.
 The Bully Algorithm
• Beside in the diagram, process 6 tells 5 that it will take
over.
• At this point 6 knows that 7 is dead and that it (6) is
the winner.

• If there is state information to be collected from disk or

elsewhere to pick up where the old coordinator left off,
6 must now do what is needed.
• When it is ready to take over, 6 announces this by
sending a COORDINATOR message to all running
processes.
 The Bully Algorithm
• When 4 gets this message, it can now continue with the operation it was trying to do
when it discovered that 7 was dead, but using 6 as the coordinator this time.
• In this way the failure of 7 is handled and the work can continue.
• If process 7 is ever restarted, it will just send all the others a COORDINATOR message
and Bully them into submission.
 A Ring Algorithm
• When any process notices that the coordinator is not functioning, it builds an
ELECTION message containing its own process number and sends the message to its
successor.
• If the successor is down, the sender skips over the successor and goes to the next
member along the ring, or the one after that until a running process is located.
• If each step, the sender adds its own process number to the list in the message
effectively masking itself a candidate to be elected as coordinator.
• Eventually, the message gets back to the process that started it all.
• That process recognizes this event when it receives an incoming message containing
its own process number.
• At that point, the message type is changed to COORDINATOR and circulated once
again, this time to inform everyone else who the coordinator is and who the member
of the new ring are.
 A Ring Algorithm
• When which message has circulated once, it is removed and everyone goes back to
work.

• Diagram shows election algorithm using a ring.

 A Ring Algorithm
• If two processes, 2 and 5discover simultaneously that the previous coordinator, process
7 has crashed.
• Each of these builds an ELECTION message and each of then starts circulating its
message, independent of the other one.
• Both messages will go all the way around, and both 2 and 5 will convert them into
COORDINATOR message with exactly the same number and in the same order.
• When both have gone around again, both will be removed.
• It does not harm to have extra message circulating at worst it consumes a little
bandwidth, but this is not considered wasteful.
 Comparing Ring and Bully Algorithm

Parameter Ring Bully

Asynchronous Yes No

Allows process to crash No Yes

Satisfies Safety Yes Depends

Dynamic process identifiers Yes No

Dynamic configuration of processes Maybe Maybe

Best case performance 2xN N -1

Worst case performance 3xN–1 O (N2)

 Synchronizers
• The synchronous model assumes a common clocking system for all nodes and a
bounded message delivery delay.
• Essentially, time can be thought of as being partitioned into slots.
• Message transmissions always occur at a fixed position in a slot.
• If a node transmits a message during slot “i” it is guaranteed that the message will be
received and processed by all neighbors by the start of slot i + I.
• Distributed algorithms that operate in phases or cycles fit naturally into this model.
• The synchronous nature of the message transmissions ensures that all the information
of the previous cycle is available to a node before sending the messages of the next
cycles.
 ABD Synchronizers
• The commonly used Asynchronous Bounded Delay (ABD) models assume a known
bound on message delay.
• It is implemented on a network where every process has a physical clock, and the
message propagation delays have a known upper bound δ.
• ABD networks are generally closer to synchronous than to fully asynchronous
networks.
• The ABD model is a nice theoretical framework, but the assumption of a bounded
message delay is often hard to satisfy in real-life networks.

• Diagram shows 2-Phase

of an ABD synchronizer.
 ABD Synchronizers
• Node B and Node D spontaneously initiate the synchronizer operation, initialize
themselves and send start signal to the non-initiators Node A and Node C as shown in
diagram (a).
• Node A and Node C wake up and complete the initialization.
• This completes the action of tick 0.
• When the physical clocks are not synchronized and the upper bound of the message
propagation delays is not known. The ABD synchronizer does not work as shown in
diagram (b).
 Awerbuch’s Synchronizers
• The main idea behind Awerbuch’s synchronizers is the determination of when a process
is safe for a given tick.
• By definition, a process is safe for a given tick when it has received every message sent
to it, and also received an acknowledgement for every message sent by it during that tick,
• Awerbuch devises three basic synchronizers, called α, β and γ.
• The synchronizer α is the simplest one, using it results in a constant overhead in time,
but in a very significant overhead in communication.
• Specially, the latter overhead is linear in the number of edges of the underlying
network.
• synchronizer α is very simple,
• It does not need an initialization.
• Using acknowledgements, each node eventually detects that it is safe.
 Awerbuch’s Synchronizers
• It then reports this fact directly to all its neighbors.
• Whenever a node learns that all its neighbors are safe, a new pulse is generated.
• The synchronizer β requires a somewhat costly initialization stage.
• In addition, using it results in a significant time overhead (linear in the number of
vertices n), but it is more communication efficient than α.
• Specifically, its communication overhead is linear in n.
• Finally, the synchronizer γ represents a tradeoff between the synchronizers α and β.
• Specifically, this synchronizer is parameterized by a positive integer parameter k.
• When k is small then the synchronizer behaves similarly to the synchronizer α and
when k is large it behaves similarly to the synchronizer β.
 Awerbuch’s Synchronizers
• A particularly important choice of k is k = log n.
• At this point on the tradeoff curve the synchronizer γ has a logarithmic in n time
overhead, and a linear in n communication overhead.
• The synchronizer γ has, however a quite costly initialization step.