CS3551 Unit 1

CS3551 Distributed Computing
UNIT I INTRODUCTION
Introduction: Definition-Relation to Computer System Components – Motivation – Message -

Passing ystems versus Shared Memory Systems – Primitives for Distributed Communication
– Synchronous versus Asynchronous Executions – Design Issues and Challenges; A Model of
Distributed Computations: A Distributed Program – A Model of Distributed Executions –
Models of Communication Networks – Global State of a Distributed System.
UNIT II LOGICAL TIME AND GLOBAL STATE
Logical Time: Physical Clock Synchronization: NTP – A Framework for a System of Logical
Clocks – Scalar Time – Vector Time; Message Ordering and Group Communication: Message
Ordering Paradigms – Asynchronous Execution with Synchronous Communication –
Synchronous Program Order on Asynchronous System – Group Communication – Causal
Order – Total Order; Global State and Snapshot Recording Algorithms: Introduction – System
Model and Definitions – Snapshot Algorithms for FIFO Channels.
UNIT III DISTRIBUTED MUTEX AND DEADLOCK
Distributed Mutual exclusion Algorithms: Introduction – Preliminaries – Lamport’s algorithm

– RicartAgrawala’s Algorithm –– Token-Based Algorithms – Suzuki-Kasami’s Broadcast
Algorithm; Deadlock Detection in Distributed Systems: Introduction – System Model –
Preliminaries – Models of Deadlocks – Chandy-Misra-Haas Algorithm for the AND model and
OR Model.
UNIT IV CONSENSUS AND RECOVERY
Consensus and Agreement Algorithms: Problem Definition – Overview of Results –

Agreement in a Failure-Free System(Synchronous and Asynchronous) – Agreement in
Synchronous Systems with Failures; Checkpointing and Rollback Recovery: Introduction –
Background and Definitions – Issues in Failure Recovery – Checkpoint-based Recovery –
Coordinated Checkpointing Algorithm – – Algorithm for Asynchronous Checkpointing and
Recovery
UNIT V CLOUD COMPUTING
Definition of Cloud Computing – Characteristics of Cloud – Cloud Deployment Models –

Cloud Service Models – Driving Factors and Challenges of Cloud – Virtualization – Load
Balancing – Scalability and Elasticity – Replication – Monitoring – Cloud Services and
Platforms: Compute Services – Storage Services – Application Services
TEXT BOOKS
1. Kshemkalyani Ajay D, Mukesh Singhal, “Distributed Computing: Principles, Algorithms

and Systems”, Cambridge Press, 2011.
2. Mukesh Singhal, Niranjan G Shivaratri, “Advanced Concepts in Operating systems”,
McGraw Hill Publishers, 1994.
REFERENCES
1. George Coulouris, Jean Dollimore, Time Kindberg, “Distributed Systems Concepts and
Design”, Fifth Edition, Pearson Education, 2012.
2. Pradeep L Sinha, “Distributed Operating Systems: Concepts and Design”, Prentice Hall of
India, 2007.
3. Tanenbaum A S, Van Steen M, “Distributed Systems: Principles and Paradigms”, Pearson
Education, 2007.
4. Liu M L, “Distributed Computing: Principles and Applications”, Pearson Education, 2004.
5. Nancy A Lynch, “Distributed Algorithms”, Morgan Kaufman Publishers, 2003.
6. Arshdeep Bagga, Vijay Madisetti, “ Cloud Computing: A Hands-On Approach”,
Universities Press, 2014.
UNIT I Distributed systems CS3551
UNIT I
INTRODUCTION TO DISTRIBUTED SYSTEMS
1. 1 INTRODUCTION
The process of computation was started from working on a single processor.
This uni-processor computing can be termed as centralized computing. As the
demand for the increased processing capability grew high, multiprocessor systems
came to existence. The advent of multiprocessor systems, led to the development of
distributed systems with high degree of scalability and resource sharing. The modern
day parallel computing is a subset of distributed computing
A distributed system is a collection of independent computers, interconnected via a network,
capable of collaborating on a task. Distributed computing is computing performed in a
distributed system.
A distributed system is a collection of independent entities that cooperate to solve a

problem that cannot be individually solved. Distributed computing is widely used due
to advancements in machines; faster and cheaper networks. In distributed systems, the
entire network will be viewed as a computer. The multiple systems connected to the
network will appear as a single system to the user. Thus the distributed systems hide
the complexity of the underlying architecture to the user. Distributed computing is a
special version of parallel computing where the processors are in different computers
and tasks are distributed to computers over a network.
The definition of distributed systems deals with two aspects that:
➢ Deals with hardware: The machines linked in a distributed system are
autonomous.
➢ Deals with software: A distributed system gives an impression to the users that
they are dealing with a single system.
Features of Distributed Systems:
No common physical clock - This is an important assumption because it introduces
the element of “distribution” in the system and gives rise to the inherent asynchrony
amongst the processors.
No shared memory - A key feature that requires message-passing for
communication. This feature implies the absence of the common physical clock.
Geographical separation – The geographically wider apart that the processors are,
the more representative is the system of a distributed system.
Autonomy and heterogeneity – Here the processors are “loosely coupled” in that
they have different speeds and each can be running a different operating system.
Issues in distributed systems

Heterogeneity
Openness
Security
Scalability
Failure handling
Dr. Gopikrishnan M 1
Concurrency
Transparency
Quality of service
QOS parameters
The distributed systems must offer the following QOS:
➢ Performance
➢ Reliability
➢ Availability
➢ Security
Differences between centralized and distributed systems
Centralized Systems Distributed Systems
In Centralized Systems, several jobs are done In Distributed Systems, jobs are distributed
on a particular central processing unit(CPU) among several processors. The Processor are
interconnected by a computer network
They have shared memory and shared They have no global state (i.e.) no shared memory
variables. and no shared variables.
Clocking is present. No global clock.
1.2 Relation to Computer System Components
Fig 1.1: Example of a Distributed System

As shown in Fig 1.1, Each computer has a memory-processing unit and the computers
are connected by a communication network. Each system connected to the distributed
networks hosts distributed software which is a middleware technology. This drives the
Distributed System (DS) at the same time preserves the heterogeneity of the DS. The
term computation or run in a distributed system is the execution of processes to
achieve a common goal.
Fig 1.2: Interaction of layers of network
The interaction of the layers of the network with the operating system and
middleware is shown in Fig 1.2. The middleware contains important library functions
for facilitating the operations of DS.
The distributed system uses a layered architecture to break down the complexity of
system design. The middleware is the distributed software that drives the distributed
system, while providing transparency of heterogeneity at the platform level
Examples of middleware:Object Management Group’s (OMG), Common Object

Request Broker Architecture (CORBA) [36], Remote Procedure Call (RPC), Message
Passing Interface (MPI)
1.3 Motivation
The following are the keypoints that acts as a driving force behind DS:
• Inherently distributed computations: DS can process the computations at

geographically remote locations.
• Resource sharing: The hardware, databases, special libraries can be shared between
systems without owning a dedicated copy or a replica. This is cost effective and
reliable.
• Access to geographically remote data and resources: As mentioned previously,
computations may happen at remote locations. Resources such as centralized servers
can also be accessed from distant locations.
• Enhanced reliability: DS provides enhanced reliability, since they run on multiple
copies of resources. The distribution of resources at distant locations makes them less
susceptible for faults. The term reliability comprises of:
1. Availability:the resource/ service provided by the resource should be accessible
at all times
2. Integrity: the value/state of the resource should be correct and consistent.
3. Fault-Tolerance:the ability to recover from system failures
• Increased performance/cost ratio: The resource sharing and remote access features
of DS naturally increase the performance / cost ratio.
• Scalable: The number of systems operating in a distributed environment can be
increased as the demand increases.
1.5 MESSAGE-PASSING SYSTEMS VERSUS SHARED MEMORY SYSTEMS

Communication among processors takes place via shared data variables,
and control variables for synchronization among the processors. The
communications between the tasks in multiprocessor systems take place through two
main modes:
Message passing systems:

• This allows multiple processes to read and write data to the message queue without
being connected to each other.
• Messages are stored on the queue until their recipient retrieves them. Message queues
are quite useful for interprocess communication and are used by most operating
systems.
Shared memory systems:
• The shared memory is the memory that can be simultaneously accessed by multiple
processes. This is done so that the processes can communicate with each other.
• Communication among processors takes place through shared data variables, and
control variables for synchronization among the processors.
• Semaphores and monitors are common synchronization mechanisms on shared
memory systems.
• When shared memory model is implemented in a distributed environment, it is termed
as distributed shared memory.
a) Message Passing Model b) Shared Memory Model
Fig 1.11: Inter-process communication models
Differences between message passing and shared memory models
Message Passing Distributed Shared Memory

Services Offered:
Variables have to be marshalled The processes share variables directly, so no
from one process, transmitted and marshalling and unmarshalling. Shared
unmarshalled into other variables at the variables can be named, stored and accessed in
receiving process. DSM.
Processes can communicate with other Here, a process does not have private address
processes. They can be protected from one space. So one process can alter the execution of
another by having private address spaces. other.
This technique can be used in heterogeneous This cannot be used to heterogeneous
computers. computers.
Synchronization between processes is through Synchronization is through locks and
message passing primitives. semaphores.
Processes communicating via message passing Processes communicating through DSM
must execute at the same time. may execute with non-overlapping lifetimes.
Efficiency:
All remote data accesses are explicit and Any particular read or update may or may not
therefore the programmer is always aware of involve communication by the underlying
whether a particular operation is in-process or runtime support.
involves the expense of communication.
1.5.1 Emulating message-passing on a shared memory system (MP → SM)

The shared memory system can be made to act as message passing system. The
shared address space can be partitioned into disjoint parts, one part being assigned to
each processor.
Send and receive operations care implemented by writing to and reading from the
destination/sender processor’s address space. The read and write operations are
synchronized.
Specifically, a separate location can be reserved as the mailbox for each
ordered pair of processes.
1.5.2 Emulating shared memory on a message-passing system (SM → MP)

This is also implemented through read and write operations. Each shared
location can be modeled as a separate process. Write to a shared location is emulated
by sending an update message tothe corresponding owner process and read operation
to a shared location is emulatedby sending a query message to the owner process.
This emulation is expensive as the processes has to gain access to other
process memory location. The latencies involvedin read and write operations may be
high even when using shared memoryemulation because the read and write operations
are implemented by using network-wide communication.
1.6 PRIMITIVES FOR DISTRIBUTED COMMUNICATION

1.6.1 Blocking / Non blocking / Synchronous / Asynchronous
Message send and message receive communication primitives are done
through Send() and Receive(), respectively.
A Send primitive has two parameters: the destination, and the buffer in the
user space that holds the data to be sent.
The Receive primitive also has two parameters: the source from which the
data is to be received and the user buffer into which the data is to be received.
There are two ways of sending data when the Send primitive is called:
➢ Buffered: The standard option copies the data from the user buffer to the kernel
buffer. The data later gets copied from the kernel buffer onto the network. For the
Receive primitive, the buffered option is usually required because the data may
already have arrived when the primitive is invoked, and needs a storage place in the
kernel.
➢ Unbuffered: The data gets copied directly from the user buffer onto thenetwork.
Blocking primitives
• The primitive commands wait for the message to be delivered. The execution of the
processes is blocked.
• The sending process must wait after a senduntil an acknowledgement is made by the
receiver.
• The receiving process must wait for the expected message from the sending process
• The receipt is determined by polling common buffer or interrupt
• This is a form of synchronization or synchronous communication.
• A primitive is blocking if control returns to the invoking process after the processing
for the primitive completes.
Non Blocking primitives
• If send is nonblocking, it returns control to the caller immediately, before the message
is sent.
• The advantage of this scheme is that the sending process can continue computing in
parallel with the message transmission, instead of having the CPU go idle.
• This is a form of asynchronous communication.
• A primitive is non-blocking if control returnsback to the invoking process
immediately after invocation, even thoughthe operation has not completed.
• For a non-blocking Send, control returnsto the process even before the data is copied
out of the user buffer.
• For anon-blocking Receive, control returns to the process even before the datamay
have arrived from the sender.
Synchronous
• A Send or a Receive primitive is synchronous if both the Send() and Receive()
handshake with each other.
• The processing for the Send primitive completes only after the invoking processor
learns
that the other corresponding Receive primitive has also been invoked andthat the
receive operation has been completed.
• The processing for theReceive primitive completes when the data to be received is
copied intothe receiver’s user buffer.
Asynchronous
• A Send primitive is said to be asynchronous, if control returns back to the invoking
process after the data item to be sent has been copied out of the user-specified buffer.
• It does not make sense to define asynchronous Receive primitives.
• Implementing non -blocking operations are tricky.

• For non-blocking primitives, a return parameter on the primitive call returns a system-
generated handle which can be later used to check the status of completion of the call.
The process can check for the completion:
➢ checking if the handle has been flagged or posted
➢ issue a Wait with a list of handles as parameters: usually blocks until one of the
parameter handles is posted.
The send and receive primitives can be implemented in four modes:
• Blocking synchronous
• Non- blocking synchronous
• Blocking asynchronous
• Non- blocking asynchronous
Four modes of send operation
Blocking synchronous Send:
• The data gets copied from the user buffer to the kernel buffer and is then sent over the
network.
• After the data is copied to the receiver’s system buffer and a Receive call has been
issued, an acknowledgement back to the sender causes control to return to the process
that invoked the Send operation and completes the Send.
Non-blocking synchronous Send:
• Control returns back to the invoking process as soon as the copy of data from the user
buffer to the kernel buffer is initiated.
• A parameter in the non-blocking call also gets set with the handle of a location that
the user process can later check for the completion of the synchronous send operation.
• The location gets posted after an acknowledgement returns from the receiver.
• The user process can keep checking for the completion of the non-blocking
synchronous Send by testing the returned handle, or it can invoke the blocking Wait
operation on the returned handle
Blocking asynchronous Send:
• The user process that invokes the Send is blocked until the data is copied from the
user’s buffer to the kernel buffer.
Non-blocking asynchronous Send:
• The user process that invokes the Send is blocked until the transfer of the data from
the user’s buffer to the kernel buffer is initiated.
• Control returns to the user process as soon as this transfer is initiated, and a parameter
in the non-blocking call also gets set with the handle of a location that the user
process can check later using the Wait operation for the completion of the
asynchronous Send.
• The asynchronous Send completes when the data has been copied out of the user’s
Fig 1.12 a) Blocking synchronous send and blocking Fig 1.12 b) Non-blocking synchronous send and
receive blocking receive
Fig 1.12 c) Blocking asynchronous send Fig 1.12 d) Non-blocking asynchronous send
buffer. The checking for the completion may be necessary if the user wants to reuse
the buffer from which the data was sent.
Modes of receive operation

Blocking Receive:
• The Receive call blocks until the data expected arrives and is written in the specified
user buffer. Then control is returned to the user process.
Non-blocking Receive:
• The Receive call will cause the kernel to register the call and return the handle of a
location that the user process can later check for the completion of the non-blocking
Receive operation.
• This location gets posted by the kernel after the expected data arrives and is copied to
the user-specified buffer. The user process can check for the completion of the non-
blocking Receive by invoking the Wait operation on the returned handle.
1.6.2 Processor Synchrony
Processor synchrony indicates that all the processors execute in lock-step with their clocks
synchronized.
Since distributed systems do not follow a common clock, this abstraction is

implemented using some form of barrier synchronization to ensure that no processor
begins executing the next step of code until all the processors have completed
executing the previous steps of code assigned to each of the processors.
1.6.3 Libraries and standards

There exists a wide range of primitives for message-passing. The message-passing
interface (MPI) library and the PVM (parallel virtual machine) library are used largely
by the scientific community
• Message Passing Interface (MPI): This is a standardized and portable message-
passing system to function on a wide variety of parallel computers. MPI primarily
addresses the message-passing parallel programming model: data is moved from the
address space of one process to that of another process through cooperative operations
on each process.
The primary goal of the Message Passing Interface is to provide a widely used
standard for writing message passing programs.
• Parallel Virtual Machine (PVM): It is a software tool for parallel networking of
computers. It is designed to allow a network of heterogeneous Unix and/or Windows
machines to be used as a single distributed parallel processor.
• Remote Procedure Call (RPC): The Remote Procedure Call (RPC) is a common
model of request reply protocol. In RPC, the procedure need not exist in the same
address space as the calling procedure. The two processes may be on the same system,
or they may be on different systems with a network connecting them.
• Remote Method Invocation (RMI): RMI (Remote Method Invocation) is a way that
a programmer can write object-oriented programming in which objects on different
computers can interact in a distributed network. It is a set of protocols being
developed by Sun's JavaSoft division that enables Java objects to communicate
remotely with other Java objects.
• Remote Procedure Call (RPC): RPC is a powerful technique for constructing
distributed, client-server based applications. In RPC, the procedure need not exist in
the same address space as the calling procedure. The two processes may be on the
same system, or they may be on different systems with a network connecting them.
By using RPC, programmers of distributed applications avoid the details of the
interface with the network. RPC makes the client/server model of computing more
powerful and easier to program.
Differences between RMI and RPC
RMI RPC
RMI uses an object oriented paradigm RPC is not object oriented and does not
where the user needs to know the object deal with objects. Rather, it calls specific
and the method of the object he needs to subroutines that are already established
invoke.
With RPC looks like a local call. RPC RMI handles the complexities of passing
handles the complexities involved with along the invocation from the local to the
passing the call from the local to the remote computer. But instead of passing a
remote computer. procedural call, RMI passes a reference to
the object and the method that is being
called.
The commonalities between RMI and RPC are as follows:
✓ They both support programming with interfaces.

✓ They are constructed on top of request-reply protocols.
✓ They both offer a similar level of transparency.
• Common Object Request Broker Architecture (CORBA): CORBA describes a

messaging mechanism by which objects distributed over a network can communicate
with each other irrespective of the platform and language used to develop those
objects. The data representation is concerned with an external representation for the
structured and primitive types that can be passed as the arguments and results of
remote method invocations in CORBA. It can be used by a variety of programming
languages.
1.7 SYNCHRONOUS VS ASYNCHRONOUS EXECUTIONS
The execution of process in distributed systems may be synchronous or
asynchronous.
Asynchronous Execution:
A communication among processes is considered asynchronous, when every
communicating process can have a different observation of the order of the messages
being exchanged. In an asynchronous execution:
• there is no processor synchrony and there is no bound on the drift rate of processor
clocks
• message delays are finite but unbounded
• no upper bound on the time taken by a process
Fig 1.13: Asynchronous execution in message passing system
Synchronous Execution:
A communication among processes is considered synchronous when every
process observes the same order of messages within the system. In the same manner,
the execution is considered synchronous, when every individual process in the system
observes the same total order of all the processes which happen within it. In an
synchronous execution:
• processors are synchronized and the clock drift rate between any two processors is
bounded
• message delivery times are such that theyoccur in one logical step or round
• upper boundon the time taken by a process to execute a step.
Fig 1.14: Synchronous execution

Emulating an asynchronous system by a synchronous system (A → S)
An asynchronous program can be emulated on a synchronous system fairly trivially as
the synchronous system is a special case of an asynchronous system – all
communication finishes within the same round in which it is initiated.
Emulating a synchronous system by an asynchronous system (S → A)

A synchronous program can be emulated on an asynchronous system using a
tool called synchronizer.
Emulation for a fault free system
Fig 1.15: Emulations in a failure free message passing system

If system A can be emulated by system B, denoted A/B, and if a problem is
not solvable in B, then it is also not solvable in A. If a problem is solvable in A, it is
also solvable in B. Hence, in a sense, all four classes are equivalent in terms of
computability in failure-free systems.
1.8 DESIGN ISSUES AND CHALLENGES IN DISTRIBUTED SYSTEMS

The design of distributed systems has numerous challenges. They can be
categorized into:
• Issues related to system and operating systems design
• Issues related to algorithm design
• Issues arising due to emerging technologies
The above three classes are not mutually exclusive.
1.8.1 Issues related to system and operating systems design

The following are some of the common challenges to be addressed in
designing a distributed system from system perspective:
➢ Communication: This task involves designing suitable communication mechanisms

among the various processes in the networks.
Examples: RPC, RMI
➢ Processes:The main challenges involved are:process and thread management at both
client and server environments, migration of code between systems, design of
software and mobile agents.
➢ Naming: Devising easy to use and robust schemes for names, identifiers,and
addresses is essential for locating resources and processes in a transparent and
scalable manner. The remote and highly varied geographical locations make this task
difficult.
➢ Synchronization: Mutual exclusion, leader election, deploying physical clocks,
global state recording are some synchronization mechanisms.
➢ Data storage and access Schemes: Designing file systems for easy and efficient data
storage with implicit accessing mechanism is very much essential for distributed
operation
➢ Consistency and replication: The notion of Distributed systems goes hand in hand
with replication of data, to provide high degree of scalability. The replicas should be
handed with care since data consistency is prime issue.
➢ Fault tolerance:This requires maintenance of fail proof links, nodes, and processes.
Some of the common fault tolerant techniques are resilience, reliable communication,
distributed commit, checkpointing andrecovery, agreement and consensus, failure
detection, and self-stabilization.
➢ Security:Cryptography, secure channels, access control, key management –
generation and distribution, authorization, and secure group management are some of
the security measure that is imposed on distributed systems.
➢ Applications Programming Interface (API) and transparency:The user
friendliness and ease of use is very important to make the distributed services to be
used by wide community. Transparency, which is hiding inner implementation policy
from users, is of the following types:
▪ Access transparency: hides differences in data representation
▪ Location transparency: hides differences in locations y providing uniform
access to data located at remote locations.
▪ Migration transparency: allows relocating resources without changing
names.
▪ Replication transparency: Makes the user unaware whether he is working on
original or replicated data.
▪ Concurrency transparency: Masks the concurrent use of shared resources
for the user.
▪ Failure transparency: system being reliable and fault-tolerant.
➢ Scalability and modularity: The algorithms, data and servicesmust be as distributed
as possible. Various techniques such as replication,caching and cache management,
and asynchronous processing help toachieve scalability.
1.8.2 Algorithmic challenges in distributed computing
➢ Designing useful execution models and frameworks
The interleaving model, partial order model, input/output automata model and the
Temporal Logic of Actions (TLA) are some examples of models that provide different
degrees of infrastructure.
➢ Dynamic distributed graph algorithms and distributed routingalgorithms
• The distributed system is generally modeled as a distributed graph.
• Hence graphalgorithms are the base for large number of higher level communication,
data dissemination, object location, and object search functions.
• These algorithms must have the capacity to deal with highly dynamic graph
characteristics. They are expected to function like routing algorithms.
• The performance of these algorithms has direct impact on user-perceived latency, data
traffic and load in the network.
➢ Time and global state in a distributed system
• The geographically remote resources demands the synchronization based on logical
time.
• Logical time is relative and eliminates the overheads of providing physical time for
applications.Logical time can
(i) capturethe logic and inter-process dependencies
(ii) track the relative progress at each process
• Maintaining the global state of the system across space involves the role of time
dimension for consistency. This can be done with extra effort in a coordinated
manner.
• Deriving appropriate measures of concurrency also involves the timedimension, as the
execution and communication speed of threads may vary a lot.
➢ Synchronization/coordination mechanisms
• Synchronization is essential for the distributed processes to facilitate concurrent
execution without affecting other processes.
• The synchronization mechanisms also involveresource management and concurrency
managementmechanisms.
• Some techniques for providing synchronization are:
✓ Physical clock synchronization: Physical clocks usually diverge in theirvalues
due to hardware limitations. Keeping them synchronized is a fundamental
challenge to maintain common time.
✓ Leader election: All the processes need to agree on which process willplay the
role of a distinguished process or a leader process. A leaderis necessary even for
many distributed algorithms because there is often some asymmetry.
✓ Mutual exclusion:Access to the critical resource(s) has to be coordinated.
✓ Deadlock detection and resolution:This is done to avoid duplicate work, and
deadlock resolution shouldbe coordinated to avoid unnecessary aborts of
processes.
✓ Termination detection: cooperation among the processesto detect the specific
global state of quiescence.
✓ Garbage collection: Detecting garbage requirescoordination among the
processes.
➢ Group communication, multicast, and ordered message delivery
• A group is a collection of processes that share a common context and collaborate on a
common task within an application domain. Group management protocols are needed
for group communication wherein processes can join and leave groups dynamically,
or fail.
• The concurrent execution of remote processes may sometimes violate the semantics
and order of the distributed program. Hence, a formal specification of the semantics
ofordered delivery need to be formulated, and then implemented.
➢ Monitoring distributed events and predicates
• Predicates defined on program variables that are local to different processesare used
for specifying conditions on the global system state.
• On-line algorithms for monitoring such predicates are henceimportant.

• An important paradigm for monitoring distributed events is thatof event streaming,
wherein streams of relevant events reported from different processes are examined
collectively to detect predicates.
• Thespecification of such predicates uses physical or logical time relationships.
➢ Distributed program design and verification tools
Methodically designed and verifiably correct programs can greatly reduce
theoverhead of software design, debugging, and engineering.Designing these is a big
challenge.
➢ Debugging distributed programs
Debugging distributed programs is much harder because of the concurrency and
replications. Adequate debugging mechanisms and tools are need of the hour.
➢ Data replication, consistency models, and caching
• Fast access to data and other resources is important in distributed systems.
• Managing replicas and their updates faces concurrency problems.
• Placement of the replicas in the systems is also a challengebecause resources usually
cannot be freely replicated.
➢ World Wide Web design – caching, searching, scheduling
• WWWis a commonly known distributed system.
• The issues of object replication and caching, prefetching of objects have to be done on
WWW also.
• Object search and navigationon the web are important functions in the operation of
the web.
➢ Distributed shared memory abstraction
• A shared memory is easier to implement since it does not involve managing the
communication tasks.
• The communication is done by the middleware by message passing.
• The overhead of shared memory is to be dealt by the middleware technology.
• Some of the methodologies that does the task of communication in shared memory
distributed systems are:
✓ Wait-free algorithms: The ability of a process to complete its execution
irrespective of theactions of other processes is wait free algorithm. They control
the access to shared resources in the shared memory abstraction. They are
expensive.
✓ Mutual exclusion: Concurrent access of processes to a shared resource or data is
executed in mutually exclusive manner. Only one process is allowed to execute
the critical section at any given time. In a distributed system, shared variables or a
local kernel cannot be used to implement mutual exclusion. Message passing is
the sole means for implementing distributed mutual exclusion.
✓ Register constructions:Architectures must be designed in such a way that,
registers allows concurrent access without any restrictions on the concurrency
permitted.
➢ Reliable and fault-tolerant distributed systems
The following are some of the fault tolerant strategies:
✓ Consensus algorithms: Consensus algorithms allow correctly functioning
processes to reach agreement among themselves in spite of the existence of
malicious processes. The goal of the malicious processesis to prevent the correctly
functioning processes from reaching agreement.The malicious processes operate
by sending messages with misleadinginformation, to confuse the correctly

functioning processes.
✓ Replication and replica management: The Triple Modular Redundancy (TMR)
technique is used in software and hardware implementation. TMR is a fault-
tolerant form of N-modular redundancy, in which three systems perform a process
and that result is processed by a majority-voting system to produce a single
output.
✓ Voting and quorum systems: Providing redundancy in the active or passive
components in the systemand then performing voting based on some quorum
criterion is a classicalway of dealing with fault-tolerance. Designing efficient
algorithms for thispurpose is the challenge.
✓ Distributed databases and distributed commit: The distributeddatabases
should also follow atomicity, consistency, isolation and durability (ACID)
properties.
✓ Self-stabilizing systems: All system executions have associated good(or legal)
states and bad (or illegal) states; during correct functioning,the system makes
transitions among the good states. A self-stabilizing algorithm guarantee to take
the system to a good state even if a bad state were toarise due to some error. Self-
stabilizing algorithms require some in-builtredundancy to track additional
variables of the state and do extra work.
✓ Checkpointing and recovery algorithms:Checkpointing is periodically
recording the current state on secondary storage so that, in case ofa failure. The
entire computation is not lost but can be recovered from oneof the recently taken
checkpoints. Checkpointing in a distributed environment is difficult because if the
checkpoints at the different processes arenot coordinated, the local checkpoints
may become useless because theyare inconsistent with the checkpoints at other
processes.
✓ Failure detectors:The asynchronous distributed do not have a bound on the
message transmission time. This makes the message passing very difficult, since
the receiver do not know the waiting time. Failure detectors probabilistically
suspect another process as havingfailed and then converge on a determination of
the up/down status of thesuspected process.
➢ Load balancing
The objective of load balancing is to gain higher throughput, and reduce the
userperceived latency. Load balancing may be necessary because of a variety
offactors such as high network traffic or high request rate causing the
networkconnection to be a bottleneck, or high computational load. The following
aresome forms of load balancing:
✓ Data migration: The ability to move data around in the system, based on the
access pattern of the users
✓ Computation migration: The ability to relocate processes in order toperform a
redistribution of the workload.
✓ Distributed scheduling: This achieves a better turnaround time for theusers by
using idle processing power in the system more efficiently.
➢ Real-time scheduling
Real-time scheduling becomes more challenging when a global view of the system
state is absent with more frequent on-line or dynamic changes. The message
propagation delays which are network-dependentare hard to control or predict. This is
an hindrance to meet the QoS requirements of the network.
➢ Performance
User perceived latency in distributed systems must be reduced. The common issues in
performance:
✓ Metrics: Appropriate metrics must be defined for measuring the performance of
theoretical distributed algorithms and its implementation.
✓ Measurement methods/tools:The distributed system is a complexentity
appropriate methodology andtools must be developed for measuring the
performance metrics.
1.8.3 Applications of distributed computing and newer challenges
The deployment environment of distributed systems ranges from mobile
systems to cloud storage. All the environments have their own challenges:
➢ Mobile systems
• Mobile systems which use wireless communication in shared broadcast mediumhave
issues related to physical layer such as transmission range, power, battery power
consumption, interfacing with wired internet, signal processing and interference.
• The issues pertaining to other higher layers includerouting, location management,
channel allocation, localization and position estimation, and mobility management.
• Apart from the above mentioned common challenges, the architectural differences of
the mobile network demands varied treatment. The two architectures are:
✓ Base-station approach (cellular approach): The geographical region is divided
into hexagonal physical locations called cells. The powerful base station transmits
signals to all other nodes in its range
✓ Ad-hoc network approach:This is an infrastructure-less approach which do not
have any base station to transmit signals. Instead all the responsibilityis distributed
among the mobile nodes.
✓ It is evident that both the approaches work in different environment with different
principles of communication. Designing a distributed system to cater the varied
need is a great challenge.
➢ Sensor networks
• A sensor is a processor with an electro-mechanical interface that is capable ofsensing
physical parameters.
• They are low cost equipment with limited computational power and battery life. They
are designed to handle streaming data and route it to external computer network and
processes.
• They are susceptible to faults and have to reconfigure themselves.
• These features introduces a whole newset of challenges, such as position estimation
and time estimation when designing a distributed system .
➢ Ubiquitous or pervasive computing
• In Ubiquitous systems the processors are embedded in the environment to
performapplication functions in the background.
• Examples: Intelligent devices, smart homes etc.
• They are distributed systems with recent advancements operating in wireless
environments through actuator mechanisms.
• They can be self-organizing and network-centricwith limited resources.
➢ Peer-to-peer computing
• Peer-to-peer (P2P) computing is computing over an application layernetwork where
all interactions among the processors are at a same level.
• This is a form of symmetric computation against the client sever paradigm.

• They are self-organizing with or without regular structure to the network.
• Some of the key challenges include: object storage mechanisms, efficient object
lookup, and retrieval in a scalable manner; dynamic reconfiguration with nodes as
well as objects joining and leaving the networkrandomly; replication strategies to
expedite object search; tradeoffs betweenobject size latency and table sizes;
anonymity, privacy, and security.
➢ Publish-subscribe, content distribution, and multimedia
• The users in present day require only the information of interest.
• In a dynamic environment where the informationconstantly fluctuates there is great
demand for
(i) Publish:an efficient mechanism for distributing this information
(ii)Subscribe: an efficient mechanism to allow end users to indicate interest in
receiving specific kinds of information
(iii)An efficient mechanism foraggregating large volumes of published information
and filtering it as per theuser’s subscription filter.
• Content distribution refers to a mechanism that categorizes the information based on
parameters.
• The publish subscribe and content distribution overlap each other.
• Multimedia data introduces special issue because of its large size.
➢ Distributed agents
• Agents are software processes or sometimes robots that move around the systemto do
specific tasks for which they are programmed.
• Agents collect and process information and can exchangesuch information with other
agents.
• Challenges in distributed agent systems include coordination mechanisms among the
agents, controlling the mobility of the agents,their software design and interfaces.
➢ Distributed data mining
• Data mining algorithms process large amount of data to detect patternsand trends in
the data, to mine or extract useful information.
• Themining can be done by applying database and artificial intelligence techniquesto a
data repository.
➢ Grid computing
• Grid computing is deployed to manage resources. For instance, idle CPU cycles of
machines connected to the network will be available to others.
• The challenges includes:scheduling jobs, framework for implementing quality of
service, real-time guarantees,security.
➢ Security in distributed systems
• The challenges of security in a distributed setting include: confidentiality,
authentication and availability. This can be addressed usingefficient and scalable
solutions.
1.9 A MODEL OF DISTRIBUTED COMPUTATIONS: DISTRIBUTED
PROGRAM
• A distributed program is composed of a set of asynchronous processes that
communicate by message passing over thecommunication network. Each process may
run on different processor.
• The processes do not share a global memory and communicate solely by passing
messages. These processes do not share a global clock that is instantaneously
accessible tothese processes.
• Process execution and message transfer are asynchronous – aprocess may execute an
action spontaneously and a process sending a message does not wait for the delivery
of the message to be complete.
• The global state of a distributed computation is composed of the states of the
processes and the communication channels. The state of a process ischaracterized by
the state of its local memory and depends upon the context.
• The state of a channel is characterized by the set of messages in transit in thechannel.
1.9.1 A MODEL OF DISTRIBUTED EXECUTIONS
• The execution of a process consists of a sequential execution of its actions.

• The actions are atomic and the actions of a process are modeled as three types of
events: internal events, message send events, and message receive events.
• The occurrence of events changes the states of respective processes and channels, thus
causing transitions in the global system state.
• An internal event changes the state of the process at which it occurs.
• A send event changes the state of the process that sends the message and the state of
the channel on which the message is sent.
• The execution of process pi produces a sequence of events e1, e2, e3, …, and it is
denoted by Hi: Hi =(hi→i). Here hiare states produced by pi and →are the casual
dependencies among events pi.
• →msgindicates the dependency that exists due to message passing between two events.
Fig 1.16: Space time distribution of distributed systems

• An internal event changes the state of the process at which it occurs.A send event
changes the state of the process that sends the message andthe state of the channel on
which the message is sent.
• A receive event changes the state of the process that receives the messageand the state
of the channel on which the message is received.
1.9.2 Casual Precedence Relations
Causal message ordering is a partial ordering of messages in a distributed
computing environment. It is the delivery of messages to a process in the order in
which they were transmitted to that process.
It places a restriction on communication between processes by requiring that if the transmission of

message mi to process pk necessarily preceded the transmission of message mj to the same process,
then the delivery of these messages to that process must be ordered such that mi is delivered before
mj.
Happen Before Relation

The partial ordering obtained by generalizing the relationship between two
process is called as happened-before relation or causal ordering or potential causal
ordering. This term was coined by Lamport. Happens-before defines a partial order
of events in a distributed system. Some events can’t be placed in the order. If say A
→B if A happens before B. A→B is defined using the following rules:
✓ Local ordering:A and B occur on same process and A occurs before B.
✓ Messages: send(m) → receive(m) for any message m
✓ Transitivity: e → e’’ if e → e’ and e’ → e’’
• Ordering can be based on two situations:
1. If two events occur in same process then they occurred in the order observed.
2. During message passing, the event of sending message occurred before the event of
receiving it.
Lamports ordering is happen before relation denoted by →

• a→b, if a and b are events in the same process and a occurred before b.
• a→b, if a is the vent of sending a message m in a process and b is the event of the
same message m being received by another process.
• If a→b and b→c, then a→c. Lamports law follow transitivity property.
When all the above conditions are satisfied, then it can be concluded that a→b is
casually related. Consider two events c and d; c→d and d→c is false (i.e) they are not
casually related, then c and d are said to be concurrent events denoted as c||d.
Fig 1.17: Communication between processes

Fig 1.22 shows the communication of messages m1 and m2 between three
processes p1, p2 and p3. a, b, c, d, e and f are events. It can be inferred from the
diagram that, a→b; c→d; e→f; b->c; d→f; a→d; a→f; b→d; b→f. Also a||e and c||e.
1.9.3 Logical vs physical concurrency

Physical as well as logical concurrency is two events that creates confusion in
distributed systems.
Physical concurrency: Several program units from the same program that execute
simultaneously.
Logical concurrency: Multiple processors providing actual concurrency. The actual
execution of programs is taking place in interleaved fashion on a single processor.
Differences between logical and physical concurrency
Logical concurrency Physical concurrency

Several units of the same program execute Several program units of the same program
simultaneously on same processor, giving an execute at the same time on different processors.
illusion to the programmer that they are executing
on multiple processors.
They are implemented through interleaving. They are implemented as uni-processor with I/O
channels, multiple CPUs, network of uni or multi
CPU machines.
1.10 MODELS OF COMMUNICATION NETWORK

The three main types of communication models in distributed systems are:
▪ FIFO (first-in, first-out): each channel acts as a FIFO message queue.
▪ Non-FIFO (N-FIFO): a channel acts like a set in which a sender process adds
messages and receiver removes messages in random order.
▪ Causal Ordering (CO): It follows Lamport’s law.
o The relation between the three models is given by CO  FIFO  N-FIFO.
A system that supports the causal ordering model satisfies the following property:
1.11 GLOBAL STATE
Distributed Snapshot represents a state in which the distributed system might have been in. A
snapshot of the system is a single configuration of the system.
▪ The global state of a distributed system is a collection of the local states of its
components, namely, the processes and the communication channels.
▪ The state of a process at any time is defined by the contents of processor registers,
stacks, local memory, etc. and depends on the local context of the distributed
application.
▪ The state of a channel is given by the set of messages in transit in the channel.
The state of a channel is difficult to state formally because a channel is a distributed entity
and its state depends upon the states of the processes it connects. Let
denote the state of a channel Cij defined as follows:
A distributed snapshot should reflect a consistent state. A global state is consistent if it could
have been observed by an external observer. For a successful Global State, all states must be
consistent:
• If we have recorded that a process P has received a message from a process Q, then
we should have also recorded that process Q had actually send that message.
• Otherwise, a snapshot will contain the recording of messages that have been received
but never sent.
• The reverse condition (Q has sent a message that P has not received) is allowed.
The notion of a global state can be graphically represented by what is called a cut. A cut
represents the last event that has been recorded for each process.
The history of each process if given by:
Each event either is an internal action of the process. We denote by sik the state of process pi
immediately before the kth event occurs. The state si in the global state S corresponding to the
cut C is that of pi immediately after the last event processed by pi in the cut – eici . The set of
events eici is called the frontier of the cut.
Fig 1.18: Types of cuts

Consistent states: The states should not violate causality. Such states are called consistent
global states and are meaningful global states.
Inconsistent global states: They are not meaningful in the sense that a distributed system
can never be in an inconsistent state.

CS3551 Unit 1

Uploaded by

Copyright:

Available Formats

CS3551 Unit 1

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CS3551 Unit 1

Uploaded by

Copyright:

Available Formats

CS3551 Distributed Computing

Introduction: Definition-Relation to Computer System Components – Motivation – Message -

UNIT II LOGICAL TIME AND GLOBAL STATE

UNIT III DISTRIBUTED MUTEX AND DEADLOCK

Distributed Mutual exclusion Algorithms: Introduction – Preliminaries – Lamport’s algorithm

UNIT IV CONSENSUS AND RECOVERY

Consensus and Agreement Algorithms: Problem Definition – Overview of Results –

UNIT V CLOUD COMPUTING

Definition of Cloud Computing – Characteristics of Cloud – Cloud Deployment Models –

1. Kshemkalyani Ajay D, Mukesh Singhal, “Distributed Computing: Principles, Algorithms

INTRODUCTION TO DISTRIBUTED SYSTEMS

A distributed system is a collection of independent entities that cooperate to solve a

Issues in distributed systems

1.2 Relation to Computer System Components

Fig 1.1: Example of a Distributed System

Fig 1.2: Interaction of layers of network

Examples of middleware:Object Management Group’s (OMG), Common Object

• Inherently distributed computations: DS can process the computations at

1.5 MESSAGE-PASSING SYSTEMS VERSUS SHARED MEMORY SYSTEMS

Message passing systems:

a) Message Passing Model b) Shared Memory Model

Fig 1.11: Inter-process communication models

Differences between message passing and shared memory models

Message Passing Distributed Shared Memory

1.5.1 Emulating message-passing on a shared memory system (MP → SM)

1.5.2 Emulating shared memory on a message-passing system (SM → MP)

1.6 PRIMITIVES FOR DISTRIBUTED COMMUNICATION

• Implementing non -blocking operations are tricky.

Modes of receive operation

Since distributed systems do not follow a common clock, this abstraction is

1.6.3 Libraries and standards

The commonalities between RMI and RPC are as follows:

✓ They both support programming with interfaces.

• Common Object Request Broker Architecture (CORBA): CORBA describes a

Fig 1.13: Asynchronous execution in message passing system

Fig 1.14: Synchronous execution

Emulating a synchronous system by an asynchronous system (S → A)

Emulation for a fault free system

Fig 1.15: Emulations in a failure free message passing system

1.8 DESIGN ISSUES AND CHALLENGES IN DISTRIBUTED SYSTEMS

1.8.1 Issues related to system and operating systems design

➢ Communication: This task involves designing suitable communication mechanisms

• On-line algorithms for monitoring such predicates are henceimportant.

by sending messages with misleadinginformation, to confuse the correctly

• This is a form of symmetric computation against the client sever paradigm.

• The execution of a process consists of a sequential execution of its actions.

Fig 1.16: Space time distribution of distributed systems

It places a restriction on communication between processes by requiring that if the transmission of

Happen Before Relation

Lamports ordering is happen before relation denoted by →

Fig 1.17: Communication between processes

1.9.3 Logical vs physical concurrency

Differences between logical and physical concurrency

Logical concurrency Physical concurrency

1.10 MODELS OF COMMUNICATION NETWORK

1.11 GLOBAL STATE

Fig 1.18: Types of cuts

You might also like