Cloud Computing

Unit I
Introduction to Distributed Systems

Characteristics

Issues in Distributed Systems

Request/Reply Protocols

RMI

Logical Clocks and Casual Ordering of Events

RPC- Election Algorithm

Distributed Mutual Exclusion

- Distributed Deadlock Detection Algorithms

1) Distributed Systems

A distributed system contains multiple nodes that are physically separate but linked together
using the network. All the nodes in this system communicate with each other and handle
processes in tandem. Each of these nodes contains a small part of the distributed operating
system software.
A diagram to better explain the distributed system is −
2)Types of Distributed Systems

The nodes in the distributed systems can be arranged in the form of client/server systems or peer
to peer systems. Details about these are as follows –

a) Client/Server Systems
In client server systems, the client requests a resource and the server provides that resource. A
server may serve multiple clients at the same time while a client is in contact with only one
server. Both the client and server usually communicate via a computer network and so they are a
part of distributed systems.
b) Peer to Peer Systems
The peer to peer systems contains nodes that are equal participants in data sharing. All the tasks
are equally divided between all the nodes. The nodes interact with each other as required as share
resources. This is done with the help of a network.

3) Advantages of Distributed Systems

Some advantages of Distributed Systems are as follows −

● All the nodes in the distributed system are connected to each other. So nodes can easily
share data with other nodes.
● More nodes can easily be added to the distributed system i.e. it can be scaled as required.
 ● Failure of one node does not lead to the failure of the entire distributed system. Other
nodes can still communicate with each other.
● Resources like printers can be shared with multiple nodes rather than being restricted to
just one.

4) Disadvantages of Distributed Systems

Some disadvantages of Distributed Systems are as follows −

● It is difficult to provide adequate security in distributed systems because the nodes as

well as the connections need to be secured.
● Some messages and data can be lost in the network while moving from one node to
another.
● The database connected to the distributed systems is quite complicated and difficult to
handle as compared to a single user system.
● Overloading may occur in the network if all the nodes of the distributed system try to
send data at once.

5) Key Characteristics of Distributed Systems

A distributed system is a system in which components are located on different networked

computers, which can communicate and coordinate their actions by passing messages to one
another. The components interact with one another in order to achieve a common goal.

Key characteristics of distributed systems are

● Resource Sharing

Resource sharing means that the existing resources in a distributed system can be accessed or
remotely accessed across multiple computers in the system.

Computers in distributed systems shares resources like hardware (disks and

printers), software (files, windows and data objects) and data.

Hardware resources are shared for reductions in cost and convenience. Data is shared for
consistency and exchange of information.
Resources are managed by a software module known as a resource manager. Every resource has
its own management policies and methods.

● Heterogeneity

In distributed systems components can have variety and differences in Networks, Computer
hardware, Operating systems, Programming languages and implementations by different
developers.

● Openness

Openness is concerned with extensions and improvements of distributed systems. The distributed
system must be open in terms of Hardware and Softwares. In order to make a distributed system
open,

1. A detailed and well-defined interface of components must be published.

2. Should standardize the interfaces of components

3. The new component must be easily integrated with existing components

● Concurrency

Concurrency is a property of a system representing the fact that multiple activities are executed
at the same time. The concurrent execution of activities takes place in different components
running on multiple machines as part of a distributed system. In addition, these activities may
perform some kind of interactions among them. Concurrency reduces the latency and increases
the throughput of the distributed system.

● Scalability

Scalability is mainly concerned about how the distributed system handles the growth as the
number of users for the system increases. Mostly we scale the distributed system by adding more
computers in the network. Components should not need to be changed when we scale the system.
Components should be designed in such a way that it is scalable.

● Fault Tolerance
In a distributed system hardware, software, network anything can fail. The system must be
designed in such a way that it is available all the time even after something has failed.

● Transparency

Distributed systems should be perceived by users and application programmers as a whole rather
than as a collection of cooperating components. Transparency can be of various types like
access, location, concurrency, replication, etc.

6) Banker’s Algorithm in Operating System

The banker’s algorithm is a resource allocation and deadlock avoidance algorithm that tests for
safety by simulating the allocation for predetermined maximum possible amounts of all
resources, then makes an “s-state” check to test for possible activities, before deciding whether
allocation should be allowed to continue.

a)Why Banker’s algorithm is named so?

Banker’s algorithm is named so because it is used in banking system to check whether loan can
be sanctioned to a person or not.

Suppose there are n number of account holders in a bank and the total sum of their money is S. If
a person applies for a loan then the bank first subtracts the loan amount from the total money that
bank has and if the remaining amount is greater than S then only the loan is sanctioned. It is done
because if all the account holders comes to withdraw their money then the bank can easily do it.

In other words, the bank would never allocate its money in such a way that it can no longer
satisfy the needs of all its customers. The bank would try to be in safe state always.
Following Data structures are used to implement the Banker’s Algorithm:

Let ‘n’ be the number of processes in the system and ‘m’ be the number of resources types.

Available :
● It is a 1-d array of size ‘m’ indicating the number of available resources of each type.
● Available[ j ] = k means there are ‘k’ instances of resource type Rj

Max :
● It is a 2-d array of size ‘n*m’ that defines the maximum demand of each process in a system.
● Max[i, j ] = k means process Pi may request at most ‘k’ instances of resource type Rj.

Allocation:
● It is a 2-d array of size ‘n*m’ that defines the number of resources of each type currently
allocated to each process.
● Allocation[i, j ] = k means process Pi is currently allocated ‘k’ instances of resource type Rj

Need:
● It is a 2-d array of size ‘n*m’ that indicates the remaining resource need of each process.
● Need [ i, j ] = k means process Pi currently need ‘k’ instances of resource type Rj
for its execution.
● Need [ i, j ] = Max [ i, j ] – Allocation [ i, j ]

Allocationi specifies the resources currently allocated to process Pi and Needi specifies the
additional resources that process Pi may still request to complete its task.
Banker’s algorithm consists of Safety algorithm and Resource request algorithm

b)Safety Algorithm

The algorithm for finding out whether or not a system is in a safe state can be described as
follows:

1) Let Work and Finish be vectors of length ‘m’ and ‘n’ respectively.
Initialize: Work = Available
Finish[i] = false; for i=1, 2, 3, 4….n
2) Find an i such that both
a) Finish[i] = false
b) Needi <= Work
if no such i exists goto step (4)
3) Work = Work + Allocation[i]
Finish[i] = true
goto step (2)
4) if Finish [i] = true for all i
then the system is in a safe state

c)Resource-Request Algorithm

Let Requesti be the request array for process Pi. Requesti [j] = k means process Pi wants k
instances of resource type Rj. When a request for resources is made by process Pi, the following
actions are taken:

1) If Requesti <= Needi

Goto step (2) ; otherwise, raise an error condition, since the process has exceeded its
maximum claim.
2) If Requesti <= Available
Goto step (3); otherwise, Pi must wait, since the resources are not available.
3) Have the system pretend to have allocated the requested resources to process Pi by modifying
the state asfollows:
Available = Available – Requesti
Allocationi = Allocationi + Requesti
Needi = Needi– Requesti

d)Example:

Considering a system with five processes P0 through P4 and three resources of type A, B, C.
Resource type A has 10 instances, B has 5 instances and type C has 7 instances. Suppose at time
t0 following snapshot of the system has been taken:

Question1. What will be the content of the Need matrix?

Need [i, j] = Max [i, j] – Allocation [i, j]

So, the content of Need Matrix is:
Question2. Is the system in a safe state? If Yes, then what is the safe sequence?

Applying the Safety algorithm on the given system,

Question3. What will happen if process P1 requests one additional instance of resource type
A and two instances of resource type C?
We must determine whether this new system state is safe. To do so, we again execute Safety
algorithm on the above data structures.
Hence the new system state is safe, so we can immediately grant the request for process P1 .

e)Code for Banker’s Algorithm in Java

//Java Program for Bankers Algorithm

public class GfGBankers
{
int n = 5; // Number of processes
int m = 3; // Number of resources
int need[][] = new int[n][m];
int [][]max;
int [][]alloc;
int []avail;
int safeSequence[] = new int[n];
void initializeValues()
{
// P0, P1, P2, P3, P4 are the Process names here
// Allocation Matrix
alloc = new int[][] { { 0, 1, 0 }, //P0
{ 2, 0, 0 }, //P1
{ 3, 0, 2 }, //P2
{ 2, 1, 1 }, //P3
{ 0, 0, 2 } }; //P4
// MAX Matrix
max = new int[][] { { 7, 5, 3 }, //P0
{ 3, 2, 2 }, //P1
{ 9, 0, 2 }, //P2
{ 2, 2, 2 }, //P3
{ 4, 3, 3 } }; //P4

// Available Resources
avail = new int[] { 3, 3, 2 };
}
void isSafe()
{
int count=0;
//visited array to find the already allocated process
booleanvisited[] = new boolean[n];
for (int i = 0;i< n; i++)
{
visited[i] = false;
}
//work array to store the copy of available resources
int work[] = new int[m];
for (int i = 0;i< m; i++)
{
work[i] = avail[i];
}

while (count<n)
{
boolean flag = false;
for (int i = 0;i< n; i++)
{
if (visited[i] == false)
{
int j;
for (j = 0;j< m; j++)
{
if (need[i][j] > work[j])
break;
}
if (j == m)
{
safeSequence[count++]=i;
visited[i]=true;
flag=true;

for (j = 0;j< m; j++)

{
work[j] = work[j]+alloc[i][j];
}
}
}
}
if (flag == false)
{
break;
}
}
if (count < n)
{
[Link]("The System is UnSafe!");
}
else
{
//[Link]("The given System is Safe");
[Link]("Following is the SAFE Sequence");
for (int i = 0;i< n; i++)
{
 [Link]("P" + safeSequence[i]);
if (i != n-1)
[Link](" -> ");
}
}
}

void calculateNeed()
{
for (int i = 0;i< n; i++)
{
for (int j = 0;j< m; j++)
{
need[i][j] = max[i][j]-alloc[i][j];
}
}
}

public static void main(String[] args)

{
int i, j, k;
GfGBankersgfg = new GfGBankers();

[Link]();
//Calculate the Need Matrix
[Link]();

// Check whether system is in safe state or not

[Link]();
}
}

f) Python3

# Banker's Algorithm

# Driver code:
if __name__=="__main__":

# P0, P1, P2, P3, P4 are the Process names here

n = 5 # Number of processes
m = 3 # Number of resources
# Allocation Matrix
alloc = [[0, 1, 0 ],[ 2, 0, 0 ],
[3, 0, 2 ],[2, 1, 1] ,[ 0, 0, 2]]
# MAX Matrix
max = [[7, 5, 3 ],[3, 2, 2 ],
[ 9, 0, 2 ],[2, 2, 2],[4, 3, 3]]
avail = [3, 3, 2] # Available Resources
f = [0]*n
ans = [0]*n
ind = 0
for k in range(n):
f[k] = 0
need = [[ 0 for i in range(m)]fori in range(n)]
for i in range(n):
for j in range(m):
need[i][j] = max[i][j] - alloc[i][j]
y=0
for k in range(5):
for i in range(n):
if (f[i] == 0):
flag = 0
for j in range(m):
if (need[i][j] > avail[j]):
flag = 1
break

if (flag == 0):
ans[ind] = i
ind += 1
for y in range(m):
avail[y] += alloc[i][y]
f[i] = 1

print("Following is the SAFE Sequence")

for i in range(n - 1):

print(" P", ans[i], " ->", sep="", end="")
print(" P", ans[n - 1], sep="")
7) Distributed System Models is as follows:

1. Architectural Models
2. Interaction Models
3. Fault Models

1. Architectural Models

Architectural model describes responsibilities distributed between system components and how
are these components placed.

a) Client-server model

The system is structured as a set of processes, called servers, that offer services to the users,
called clients.
 ● The client-server model is usually based on a simple request/reply protocol, implemented
with send/receive primitives or using remote procedure calls (RPC) or remote method
invocation (RMI):
● The client sends a request (invocation) message to the server asking for some service;
● The server does the work and returns a result (e.g. the data requested) or an error code if
the work could not be performed.

A server can itself request services from other servers; thus, in this new relation, the server
itself acts like a client.

c) Peer-to-peer

All processes (objects) play similar role.

● Processes (objects) interact without particular distinction between clients and servers.
● The pattern of communication depends on the particular application.
● A large number of data objects are shared; any individual computer holds only a small
part of the application database.
● Processing and communication loads for access to objects are distributed across many
computers and access links.
● This is the most general and flexible model.
● Peer-to-Peer tries to solve some of the above.
● It distributes shared resources widely -> share computing and communication loads.

c)Problems with peer-to-peer:

● High complexity due to

o Cleverly place individual objects
o retrieve the objects
o maintain potentially large number of replicas.

2. Interaction Model
Interaction model are for handling time i. e. for process execution, message delivery, clock drifts
etc.

a)Synchronous distributed systems

Main features:
 ● Lower and upper bounds on execution time of processes can be set.
● Transmitted messages are received within a known bounded time.
● Drift rates between local clocks have a known bound.

Important consequences:
1. In a synchronous distributed system there is a notion of global physical time (with a
known relative precision depending on the drift rate).
2. Only synchronous distributed systems have a predictable behavior in terms of timing.
Only such systems can be used for hard real-time applications.
3. In a synchronous distributed system it is possible and safe to use timeouts in order to
detect failures of a process or communication link.
4. It is difficult and costly to implement synchronous distributed systems.

b)Asynchronous distributed systems

● Many distributed systems (including those on the Internet) are asynchronous. - No bound
on process execution time (nothing can be assumed about speed, load, and reliability of
computers).
● No bound on message transmission delays (nothing can be assumed about speed, load,
and reliability of interconnections) - No bounds on drift rates between local clocks.

Important consequences:

1. In an asynchronous distributed system there is no global physical time. Reasoning can be

only in terms of logical time.
2. Asynchronous distributed systems are unpredictable in terms of timing.
3. No timeouts can be used.
4. Asynchronous systems are widely and successfully used in practice.
5. In practice timeouts are used with asynchronous systems for failure detection.
6. However, additional measures have to be applied in order to avoid duplicated messages,
duplicated execution of operations, etc.

3. Fault Models
● Failures can occur both in processes and communication channels. The reason can be
both software and hardware faults.
● Fault models are needed in order to build systems with predictable behavior in case of
faults (systems which are fault tolerant).
 ● such a system will function according to the predictions, only as long as the real faults
behave as defined by the “fault model”.

8)Request/Reply Communication

Queues are the key to connectionless communication. Each server is assigned an Inter-Process
Communication (IPC) message queue called a request queue and each client is assigned a
reply queue. Therefore, rather than establishing and maintaining a connection with a server, a
client application can send requests to the server by putting those requests on the server's
queue, and then check and retrieve messages from the server by pulling messages from its
own reply queue.
The request/reply model is used for both synchronous and asynchronous service requests as
described in the following topics.

a)Synchronous Messaging
In a synchronous call, a client sends a request to a server, which performs the requested action
while the client waits. The server then sends the reply to the client, which receives the reply.
This is known as Synchronous Request/Reply Communication.

b) Asynchronous Messaging
In an asynchronous call, the client does not wait for a service request it has submitted to finish
before undertaking other tasks. Instead, after issuing a request, the client performs additional
tasks (which may include issuing more requests). When a reply to the first request is
available, the client retrieves [Link] is known as Asynchronous Request/Reply
Communication.
9) RMI

RMI stands for Remote Method Invocation. It is a mechanism that allows an object residing in
one system (JVM) to access/invoke an object running on another JVM.
RMI is used to build distributed applications; it provides remote communication between Java
programs. It is provided in the package [Link].

a) Architecture of an RMI Application

In an RMI application, we write two programs, a server program (resides on the server) and
a client program (resides on the client).
● Inside the server program, a remote object is created and reference of that object is made
available for the client (using the registry).
● The client program requests the remote objects on the server and tries to invoke its
methods.
The following diagram shows the architecture of an RMI application.
Let us now discuss the components of this architecture.
● Transport Layer − This layer connects the client and the server. It manages the existing
connection and also sets up new connections.
● Stub − A stub is a representation (proxy) of the remote object at client. It resides in the
client system; it acts as a gateway for the client program.
● Skeleton − This is the object which resides on the server side. stub communicates with
this skeleton to pass request to the remote object.
● RRL(Remote Reference Layer) − It is the layer which manages the references made by
the client to the remote object.

b)Working of an RMI Application

The following points summarize how an RMI application works −

● When the client makes a call to the remote object, it is received by the stub which
eventually passes this request to the RRL.
● When the client-side RRL receives the request, it invokes a method called invoke() of
the object remoteRef. It passes the request to the RRL on the server side.
● The RRL on the server side passes the request to the Skeleton (proxy on the server)
which finally invokes the required object on the server.
 ● The result is passed all the way back to the client.

c)Marshalling and Unmarshalling

Whenever a client invokes a method that accepts parameters on a remote object, the parameters
are bundled into a message before being sent over the network. These parameters may be of
primitive type or objects. In case of primitive type, the parameters are put together and a header
is attached to it. In case the parameters are objects, then they are serialized. This process is
known as marshalling.
At the server side, the packed parameters are unbundled and then the required method is
invoked. This process is known as unmarshalling.

d)RMI Registry

RMI registry is a namespace on which all server objects are placed. Each time the server creates
an object, it registers this object with the RMIregistry (using bind() or reBind() methods).
These are registered using a unique name known as bind name.
To invoke a remote object, the client needs a reference of that object. At that time, the client
fetches the object from the registry using its bind name (using lookup() method).
The following illustration explains the entire process −
e)Goals of RMI

Following are the goals of RMI −

● To minimize the complexity of the application.

● To preserve type safety.
● Distributed garbage collection.
● Minimize the difference between working with local and remote objects.

10) Logical Clock in Distributed System

● Logical Clocks refer to implementing a protocol on all machines within your distributed
system, so that the machines are able to maintain consistent ordering of events within
some virtual timespan.

● A logical clock is a mechanism for capturing chronological and causal relationships in a

distributed system.

● Distributed systems may have no physically synchronous global clock, so a logical clock
allows global ordering on events from different processes in such systems.

a) Example

If we go outside then we have made a full plan that at which place we have to go first, second
and so on. We don’t go to second place at first and then the first place. We always maintain the
procedure or an organization that is planned before. In a similar way, we should do the
operations on our PCs one by one in an organized way.

Suppose, we have more than 10 PCs in a distributed system and every PC is doing it’s own work
but then how we make them work together. There comes a solution to this i.e. LOGICAL
CLOCK.

Method-1:

● To order events across process, try to sync clocks in one approach.

● This means that if one PC has a time 2:00 pm then every PC should have the same time
which is quite not possible. Not every clock can sync at one time. Then we can’t follow
this method.
Method-2:
●
Another approach is to assign Timestamps to events.

● Taking the example into consideration, this means if we assign the first place as 1, second
place as 2, third place as 3 and so on. Then we always know that the first place will
always come first and then so on. Similarly, If we give each PC their individual number
than it will be organized in a way that 1st PC will complete its process first and then
second and so on. But Timestamps will only work as long as they obey causality.

b)Causality

Causality is fully based on HAPPEN BEFORE RELATIONSHIP.

● Taking single PC only if 2 events A and B are occurring one by one then TS(A) < TS(B). If
A has timestamp of 1, then B should have timestamp more than 1, then only happen before
relationship occurs.

● Taking 2 PCs and event A in P1 (PC.1) and event B in P2 (PC.2) then also the condition will
be TS(A) < TS(B). Taking example- suppose you are sending message to someone at 2:00:00
pm, and the other person is receiving it at 2:00:02 [Link] it’s obvious that TS(sender) <
TS(receiver).

c)Properties Derived from Happen Before Relationship

● Transitive Relation
If, TS(A) <TS(B) and TS(B) <TS(C), then TS(A) < TS(C)

● Causally Ordered Relation

a->b, this means that a is occurring before b and if there is any changes in a it will surely
reflect on b.

● Concurrent Event
This means that not every process occurs one by one, some processes are made to happen
simultaneously i.e., A || B.

d)Causal ordering
Causal ordering is a vital tool for thinking about distributed systems. Once you understand it,
many other concepts become much simpler.
(i)The fundamental property of distributed systems:
Messages sent between machines may arrive zero or more times at any point after they are sent
This is the sole reason that building distributed systems is hard.
For example, because of this property it is impossible for two computers communicating over a
network to agree on the exact time. You can send me a message saying "it is now 10:00:00" but I
don't know how long it took for that message to arrive. We can send messages back and forth all
day but we will never know for sure that we are synchronized.
If we can't agree on the time then we can't always agree on what order things happen in. Suppose
I say "my user logged on at 10:00:00" and you say "my user logged on at 10:00:01". Maybe mine
was first or maybe my clock is just fast relative to yours. The only way to know for sure is if
something connects those two events.
For example, if my user logged on and then sent your user an email and if you received that
email before your user logged on then we know for sure that mine was first.
This concept is called causal ordering and is written like this:
A -> B (event A is causally ordered before event B)
Let's define it a little more formally. We model the world as follows: We have a number of
machines on which we observe a series of events. These events are either specific to one
machine (eg user input) or are communications between machines. We define the causal ordering
of these events by three rules:
If A and B happen on the same machine and A happens before B then A -> B

If I send you some message M and you receive it then (send M) -> (recv M)

If A -> B and B -> C then A -> C

We are used to thinking of ordering by time which is a total order - every pair of events can be
placed in some order. In contrast, causal ordering is only a partial order - sometimes events
happen with no possible causal relationship i.e. not (A -> B or B -> A).
This diagram shows a nice way to picture these relationships.
On a single machine causal ordering is exactly the same as time ordering (actually, on a
multi-core machine the situation is more complicated, but let's forget about that for now).
Between machines causal ordering is conveyed by messages. Since sending messages is the only
way for machines to affect each other this gives rise to a nice property:
If not(A -> B) then A cannot possibly have caused B
Since we don't have a single global time this is the only thing that allows us to reason about
causality in a distributed system. This is really important so let's say it again:
Communication bounds causality.
The lack of a total global order is not just an accidental property of computer systems, it is
a fundamental property of the laws of physics. I claimed that understanding causal order makes
many other concepts much simpler.

(ii)Clocks

Lamport clocks and Vector clocks are data-structures which efficiently approximate the causal
ordering and so can be used by programs to reason about causality.
If A -> B then LC_A < LC_B

If VC_A < VC_B then A -> B

Different types of vector clock trade-off compression vs accuracy by storing smaller or larger
portions of the causal history of an event.
⮚ Lamport clocks
• The algorithm follows some simple rules:
 • A process increments its counter before each local event (e.g., message sending event);
• When a process sends a message, it includes its counter value with the message after
executing step 1;
• On receiving a message, the counter of the recipient is updated, if necessary, to the
greater of its current counter and the timestamp in the received message. The counter is
then incremented by 1 before the message is considered received
⮚ Vector clocks
• A vector clock is a data structure used for determining the partial ordering of events in a
distributed system and detecting causality violations.
• Just as in Lamport timestamps, inter-process messages contain the state of the sending
process's logical clock.
• A vector clock of a system of N processes is an array/vector of N logical clocks, one
clock per process; a local "largest possible values" copy of the global clock-array is kept
in each process.

11. Consistency

When mutable state is distributed over multiple machines each machine can receive update
events at different times and in different orders.
If the final state is dependent on the order of updates then the system must choose a single
serialisation of the events, imposing a global total order.
A distributed system is consistent exactly when the outside world can never observe two
different serialisations.

12. CAP Theorem

The CAP (Consistency-Availability-Partition) theorem also boils down to causality. When a

machine in a distributed system is asked to perform an action that depends on its current state it
must decide that state by choosing a serialisation of the events it has seen. It has two options:

● Choose a serialisation of its current events immediately

● Wait until it is sure it has seen all concurrent events before choosing a serialisation

The first choice risks violating consistency if some other machine makes the same choice with a
different set of events.
The second violates availability by waiting for every other machine that could possibly have
received a conflicting event before performing the requested action.
There is no need for an actual network partition to happen - the trade-off between availability
and consistency exists whenever communication between components is not instant.
Ordering requires waiting
Even your hardware cannot escape this law. It provides the illusion of synchronous access to
memory at the cost of availabilty. If you want to write fast parallel programs then you need to
understand the messaging model used by the underlying hardware.

13. Election algorithm and distributed processing

a)Distributed Algorithm:

This is a algorithm that runs on a distributed system.

Distributed system is a collection of independent computers that do not share their memory.

Each processor has its own memory and they communicate via communication networks.

Communication in networks is implemented in a process on one machine communicating with a

process on other machine.

Many algorithms used in distributed system require a coordinator that performs functions needed
by other processes in the system.

Election algorithms are designed to choose a coordinator.

b)Election Algorithms:

Election algorithms choose a process from group of processors to act as a coordinator. If the
coordinator process crashes due to some reasons, then a new coordinator is elected on other
processor.

Election algorithm basically determines where a new copy of coordinator should be restarted.

Election algorithm assumes that every active process in the system has a unique priority number.
The process with highest priority will be chosen as a new coordinator. Hence, when a
coordinator fails, this algorithm elects that active process which has highest priority number.
Then this number is send to every active process in the distributed system.
We have two election algorithms for two different configurations of distributed system.

(i) The Bully Algorithm –

This algorithm applies to system where every process can send a message to every other process
in the system.

Algorithm – Suppose process P sends a message to the coordinator.

1. If coordinator does not respond to it within a time interval T, then it is assumed that
coordinator has failed.
2. Now process P sends election message to every process with high priority number.
3. It waits for responses, if no one responds for time interval T then process P elects itself as a
coordinator.
4. Then it sends a message to all lower priority number processes that it is elected as their new
coordinator.
5. However, if an answer is received within time T from any other process Q,
● (I) Process P again waits for time interval T’ to receive another message from Q that it
has been elected as coordinator.
● (II) If Q doesn’t responds within time interval T’ then it is assumed to have failed and
algorithm is restarted.

Bully Election Algorithm

When any process notices that the coordinator is no longer responding to request, it initiates an
ELECTION. The process holds an ELECTION message as follows:

Example:

We start with 6 processes, all directly connected to each other. Process 6 is the leader,
as it has the highest number.
Process 6 fails.

Process 3 notices that Process 6 does not respond. So it starts an election, notifying
those processes with ids greater than 3.
Both Process 4 and Process 5 respond, telling Process 3 that they'll take over from here.

Process 4 sends election messages to both Process 5 and Process 6.

Only Process 5 answers and takes over the election.

Process 5 sends out only one election message to Process 6.

When Process 6 does not respond Process 5 declares itself the winner.

(ii). The Ring Algorithm –

This algorithm applies to systems organized as a ring(logically or physically). In this algorithm

we assume that the link between the process are unidirectional and every process can message to
the process on its right only. Data structure that this algorithm uses is active list, a list that has
priority number of all active processes in the system.

Algorithm –
1. If process P1 detects a coordinator failure, it creates new active list which is empty initially.
It sends election message to its neighbour on right and adds number 1 to its active list.
2. If process P2 receives message elect from processes on left, it responds in 3 ways:
● (I) If message received does not contain 1 in active list then P1 adds 2 to its active list
and forwards the message.
● (II) If this is the first election message it has received or sent, P1 creates new active list
with numbers 1 and 2. It then sends election message 1 followed by 2.
● (III) If Process P1 receives its own election message 1 then active list for P1 now
contains numbers of all the active processes in the system. Now Process P1 detects
highest priority number from list and elects it as the new coordinator.

Token Ring Election Algorithm

When any process notice that the coordinator is not functioning, it builds an ELECTION
MESSAGE containing its own process number and sends the message to its successor.

Example:
We start with 6 processes, connected in a logical ring. Process 6 is the leader, as it has the highest
number.

Process 6 fails

Process 3 notices that Process 6 does not respond. So it starts an election, sending a message
containing its id to the next node in the ring.
Process 5 passes the message on, adding its own id to the message.

Process 0 passes the message on, adding its own id to the message.
Process 1 passes the message on, adding its own id to the message.

Process 4 passes the message on, adding its own id to the message.
When Process 3 receives the message back, it knows the message has gone around the ring, as its
own id is in the list. Picking the highest id in the list, it starts the coordinator message "5 is the
leader" around the ring.

Process 5 passes on the coordinator message.

Process 0 passes on the coordinator message.

Process 1 passes on the coordinator message.

Process 4 passes on the coordinator message.

Process 3 receives the coordinator message, and stops it.

Bully Algorithm Code in Java:

import [Link].*;
import [Link];

class Anele{
static int n;
static int pro[] = new int[100];
static int sta[] = new int[100];
static int co;

public static void main(String args[])throws IOException

{
[Link]("Enter the number of process");
Scanner in = new Scanner([Link]);
n = [Link]();

int i,j,k,l,m;

for(i=0;i<n;i++)
{
[Link]("For process "+(i+1)+":");
[Link]("Status:");
sta[i]=[Link]();
[Link]("Priority");
pro[i] = [Link]();
}

[Link]("Which process will initiate election?");

 int ele = [Link]();

elect(ele);
[Link]("Final coordinator is "+co);
}

static void elect(int ele)

{
ele = ele-1;
co = ele+1;
for(int i=0;i<n;i++)
{
if(pro[ele]<pro[i])
{
[Link]("Election message is sent from "+(ele+1)+" to "+(i+1));
if(sta[i]==1)
elect(i+1);
}
}
}
}

Output:
Enter the number of process
7
For process 1:
Status:
1
Priority
1
For process 2:
Status:
1
Priority
2
For process 3:
Status:
1
Priority
3
For process 4:
Status:
1
Priority
4
For process 5:
Status:
1
Priority
5
For process 6:
Status:
1
Priority
6
For process 7:
Status:
0
Priority
7
Which process will initiate election?
4
Election message is sent from 4 to 5
Election message is sent from 5 to 6
Election message is sent from 6 to 7
Election message is sent from 5 to 7
Election message is sent from 4 to 6
Election message is sent from 6 to 7
Election message is sent from 4 to 7
Final coordinator is 6

Ring Algorithm code in Java:

import [Link];
class Process{
public int id;
public boolean active;

public Process(int id){

[Link]=id;
active=true;
}

}
public class Ring{
int noOfProcesses;
Process[] processes;
Scanner sc;

public Ring(){
sc=new Scanner([Link]);
}
public void initialiseRing(){
[Link](“Enter no of processes”);
noOfProcesses=[Link]();
processes = new Process[noOfProcesses];
for(int i=0;i<[Link];i++){
processes[i]= new Process(i);
}
}

public int getMax(){

int maxId=-99;
int maxIdIndex=0;
for(int i=0;i<[Link];i++){
if(processes[i].active && processes[i].id>maxId){
maxId=processes[i].id;
maxIdIndex=i;

}
}
return maxIdIndex;
}
public void performElection(){

[Link](“Process no “+processes[getMax()].id+” fails”);

processes[getMax()].active=false;
[Link](“Election Initiated by”);
int initiatorProcesss=[Link]();

int prev = initiatorProcesss;

int next = prev+1;

while(true){
if(processes[next].active){
[Link](“Process “+processes[prev].id+” pass Election(“+processes[prev].id+”)
to”+processes[next].id);
prev=next;
}

next = (next+1)%noOfProcesses;
if(next == initiatorProcesss){
break;
}
}
[Link](“Process “+ processes[getMax()].id +” becomes coordinator”);
int coordinator = processes[getMax()].id;

prev = coordinator;
next =(prev+1)%noOfProcesses;

while(true){

if(processes[next].active)
{
[Link](“Process “+ processes[prev].id +” pass Coordinator(“+coordinator+ “)
message to process “+processes[next].id );
prev = next;
}
next = (next+1) % noOfProcesses;
if(next == coordinator)
{
[Link](“End Of Election “);
break;
}
}

public static void main(String arg[]){

Ring r= new Ring();
[Link]();
[Link]();
}

Output:

C:\Users\Garry\Desktop\CLIX\Bully>java Bully
Enter No of Processes
5
Process no 4 fails
Process 0Passes Election(0) message to process 1
Process 0Passes Election(0) message to process 2
Process 0Passes Election(0) message to process 3
Process 1Passes Ok(1) message to process 0
Process 2Passes Ok(2) message to process 0
Process 3Passes Ok(3) message to process 0
Process 1Passes Election(1) message to process 2
Process 1Passes Election(1) message to process 3
Process 2Passes Ok(2) message to process 1
Process 3Passes Ok(3) message to process 1
Process 2Passes Election(2) message to process 3
Process 3Passes Ok(3) message to process 2
Finally Process 3 Becomes Coordinator
Process 3Passes Coordinator(3) message to process 2
Process 3Passes Coordinator(3) message to process 1
Process 3Passes Coordinator(3) message to process 0
End of Election

14. Mutual exclusion in distributed system

Mutual exclusion is a concurrency control property which is introduced to prevent race

conditions. It is the requirement that a process cannot enter its critical section while another
concurrent process is currently present or executing in its critical section i.e only one process is
allowed to execute the critical section at any given instance of time.

a)Mutual exclusion in single computer system Vs. distributed system:

In single computer system, memory and other resources are shared between different processes.
The status of shared resources and the status of users is easily available in the shared memory so
with the help of shared variable (For example: Semaphores) mutual exclusion problem can be
easily solved.

In Distributed systems, we neither have shared memory nor a common physical clock and there
for we cannot solve mutual exclusion problem using shared variables. To eliminate the mutual
exclusion problem in distributed system approach based on message passing is used.
A site in distributed system does not have complete information of state of the system due to lack
of shared memory and a common physical clock.

b)Requirements of Mutual exclusion Algorithm:

● No Deadlock:

Two or more site should not endlessly wait for any message that will never arrive.

● No Starvation:
 Every site who wants to execute critical section should get an opportunity to execute it in
finite time. Any site should not wait indefinitely to execute critical section while other site
are repeatedly executing critical section

● Fairness:

Each site should get a fair chance to execute critical section. Any request to execute critical
section must be executed in the order they are made i.e Critical section execution requests
should be executed in the order of their arrival in the system.

● Fault Tolerance:

In case of failure, it should be able to recognize it by itself in order to continue functioning

without any disruption.

c)Solution to distributed mutual exclusion:

As we know shared variables or a local kernel can not be used to implement mutual exclusion in
distributed systems. Message passing is a way to implement mutual exclusion. Below are the
three approaches based on message passing to implement mutual exclusion in distributed
systems:

1. Token Based Algorithm:

● A unique token is shared among all the sites.
● If a site possesses the unique token, it is allowed to enter its critical section
● This approach uses sequence number to order requests for the critical section.
● Each requests for critical section contains a sequence number. This sequence number is
used to distinguish old and current requests.
● This approach insures Mutual exclusion as the token is unique

Example:
● Suzuki-Kasami’s Broadcast Algorithm

2. Non-token based approach:

● A site communicates with other sites in order to determine which sites should execute
critical section next. This requires exchange of two or more successive round of messages
among sites.
● This approach use timestamps instead of sequence number to order requests for the
critical section.
● When ever a site make request for critical section, it gets a timestamp. Timestamp is also
used to resolve any conflict between critical section requests.
● All algorithm which follows non-token based approach maintains a logical clock. Logical
clocks get updated according to Lamport’s scheme
 Example:
● Lamport's algorithm, Ricart–Agrawala algorithm

3. Quorum based approach

● Instead of requesting permission to execute the critical section from all other sites, Each
site requests only a subset of sites which is called a quorum.
● Any two subsets of sites or Quorum contains a common site.
● This common site is responsible to ensure mutual exclusion

15. Deadlock detection in Distributed systems

In a distributed system deadlock can neither be prevented nor avoided as the system is so vast
that it is impossible to do so. Therefore, only deadlock detection can be implemented. The
techniques of deadlock detection in the distributed system require the following:

● Progress –

The method should be able to detect all the deadlocks in the system.

● Safety –

The method should not detect false or phantom deadlocks.

There are three approaches to detect deadlocks in distributed systems. They are as follows:

I. Centralized approach –

In the centralized approach, there is only one responsible resource to detect deadlock. The
advantage of this approach is that it is simple and easy to implement, while the drawbacks
include excessive workload at one node, single-point failure (that is the whole system is
dependent on one node if that node fails the whole system crashes) which in turns makes the
system less reliable.

II. Distributed approach –

In the distributed approach different nodes work together to detect deadlocks. No single point
failure (that is the whole system is dependent on one node if that node fails the whole system
crashes) as the workload is equally divided among all nodes. The speed of deadlock detection
also increases.
III. Hierarchical approach –

This approach is the most advantageous. It is the combination of both centralized and
distributed approaches of deadlock detection in a distributed system. In this approach, some
selected nodes or clusters of nodes are responsible for deadlock detection and these selected
nodes are controlled by a single node.