lOMoARcPSD|11981679
DS Notes
Distributed computing (Anna University)
Studocu is not sponsored or endorsed by any college or university
Downloaded by NADHIYA S ()
, lOMoARcPSD|11981679
CS3551 DISTRIBUTED COMPUTING
UNIT-1
UNIT I INTRODUCTION 8
Introduction: Definition-Relation to Computer System Components – Motivation – Message - Passing Systems 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.
INTRODUCTION
A distributed system is a collection of independent entities that cooperate to solve a problem that cannot
be individually solved.
FEATURES
● No common physical clock
There is no global time in a distributed system, so the clocks on different computers do not necessarily
give the same time as one another.
● No shared memory
The distributed systems has no shared memory.
● Geographical separation
The processors are geographically wider apart. However, it is not necessary for the processors to be on a
wide-area network (WAN). Recently, the network/cluster of workstations (NOW/COW)
configuration connecting processors on a LAN is also being increasingly regarded as a small distributed
system. This NOW configuration is becoming popular because of the low-cost high-speed off-the-shelf
processors now available. The Google search engine is based on the NOW architecture.
● Autonomy and heterogeneity
The processors are “loosely coupled” in that they have different speeds and each can be running a
different operating system. They are usually not part of a dedicated system, but cooperate with one
another by offering services or solving a problem jointly.
RELATION TO COMPUTER SYSTEM COMPONENTS
Each computer has a memory-processing unit and the computers are connected by a communication
network.
Downloaded by NADHIYA S ()
, lOMoARcPSD|11981679
Figure 1.2 shows the relationships of the software components that run on each of the computers and use
the local operating system and network protocol stack for functioning. The distributed software is also termed as
middleware. A distributed execution is the execution of processes across the distributed system to
collaboratively achieve a common goal. An execution is also sometimes termed a computation or a run.
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. Figure 1.2 schematically shows the interaction of this software with these
system components at each processor. Here we assume that the middleware layer does not contain the
traditional application layer functions of the network protocol stack, such as http, mail, ftp, and telnet.
Various primitives and calls to functions defined in various libraries of the middleware layer are
embedded in the user program code. There exist several libraries to choose from to invoke primitives for the
more common functions – such as reliable and ordered multicasting – of the middleware layer.
There are several standards such as Object Management Group’s (OMG) common object request broker
architecture (CORBA), and the remote procedure call (RPC) mechanism. The RPC mechanism conceptually
works like a local procedure call, with the difference that the procedure code may reside on a remote machine,
and the RPC software sends a message across the network to invoke the remote procedure. It then awaits a reply,
after which the procedure call completes from the perspective of the program that invoked it.
Other Examples: RMI, DCOM
MOTIVATION
1. Inherently distributed computations In many applications such as money transfer in banking, or reaching
consensus among parties that are geographically distant, the computation is inherently distributed.
2. Resource sharing Resources such as peripherals, complete data sets in databases, special libraries, as well as
data (variable/files) cannot be fully replicated at all the sites because it is often neither practical nor cost-
effective. Further, they cannot be placed at a single site because access to that site might prove to be a
bottleneck. Therefore, such resources are typically distributed across the system. For example, distributed
Downloaded by NADHIYA S ()
, lOMoARcPSD|11981679
databases such as DB2 partition the data sets across several servers, in addition to replicating them at a few sites
for rapid access as well as reliability.
3. Access to geographically remote data and resources In many scenarios, the data cannot be replicated at
every site participating in the distributed execution because it may be too large or too sensitive to be replicated.
For example, payroll data within a multinational corporation is both too large and too sensitive to be replicated
at every branch office/site. It is therefore stored at a central server which can be queried by branch offices.
Similarly, special resources such as supercomputers exist only in certain locations, and to access such
supercomputers, users need to log in remotely.
4. Enhanced reliability A distributed system has the inherent potential to provide increased reliability because
of the possibility of replicating resources and executions, as well as the reality that geographically distributed
resources are not likely to crash/malfunction at the same time under normal circumstances. Reliability entails
several aspects:
● availability, i.e., the resource should be accessible at all times;
● integrity, i.e., the value/state of the resource should be correct, in the face of concurrent access from
multiple processors;
● fault-tolerance, i.e., the ability to recover from system failures.
5. Increased performance/cost ratio By resource sharing and accessing geographically remote data and
resources, the performance/cost ratio is increased.
6. Scalability As the processors are usually connected by a wide-area network, adding more processors does not
pose a direct bottleneck for the communication network.
7. Modularity and incremental expandability Heterogeneous processors may be easily added into the system
without affecting the performance, as long as those processors are running the same middleware algorithms.
Similarly, existing processors may be easily replaced by other processors.
MESSAGE-PASSING SYSTEMS VERSUS SHARED MEMORY SYSTEMS
Shared memory systems are those in which there is a (common) shared address space throughout the
system. Communication among processors takes place via shared data variables, and control variables for
synchronization among the processors.
All multicomputer (NUMA as well as message-passing) systems that do not have a shared address space
provided by the underlying architecture and hardware necessarily communicate by message passing.
Conceptually, programmers find it easier to program using shared memory than by message passing.
Emulating message-passing on a shared memory system (MP →SM)
The shared address space can be partitioned into disjoint parts, one part being assigned to each
processor. “Send” and “receive” operations can be implemented by writing to and reading from the
destination/sender processor’s address space, respectively. Specifically, a separate location can be reserved as
the mailbox for each ordered pair of processes. A Pi–Pj message-passing can be emulated by a write by Pi to the
Downloaded by NADHIYA S ()
DS Notes
Distributed computing (Anna University)
Studocu is not sponsored or endorsed by any college or university
Downloaded by NADHIYA S ()
, lOMoARcPSD|11981679
CS3551 DISTRIBUTED COMPUTING
UNIT-1
UNIT I INTRODUCTION 8
Introduction: Definition-Relation to Computer System Components – Motivation – Message - Passing Systems 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.
INTRODUCTION
A distributed system is a collection of independent entities that cooperate to solve a problem that cannot
be individually solved.
FEATURES
● No common physical clock
There is no global time in a distributed system, so the clocks on different computers do not necessarily
give the same time as one another.
● No shared memory
The distributed systems has no shared memory.
● Geographical separation
The processors are geographically wider apart. However, it is not necessary for the processors to be on a
wide-area network (WAN). Recently, the network/cluster of workstations (NOW/COW)
configuration connecting processors on a LAN is also being increasingly regarded as a small distributed
system. This NOW configuration is becoming popular because of the low-cost high-speed off-the-shelf
processors now available. The Google search engine is based on the NOW architecture.
● Autonomy and heterogeneity
The processors are “loosely coupled” in that they have different speeds and each can be running a
different operating system. They are usually not part of a dedicated system, but cooperate with one
another by offering services or solving a problem jointly.
RELATION TO COMPUTER SYSTEM COMPONENTS
Each computer has a memory-processing unit and the computers are connected by a communication
network.
Downloaded by NADHIYA S ()
, lOMoARcPSD|11981679
Figure 1.2 shows the relationships of the software components that run on each of the computers and use
the local operating system and network protocol stack for functioning. The distributed software is also termed as
middleware. A distributed execution is the execution of processes across the distributed system to
collaboratively achieve a common goal. An execution is also sometimes termed a computation or a run.
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. Figure 1.2 schematically shows the interaction of this software with these
system components at each processor. Here we assume that the middleware layer does not contain the
traditional application layer functions of the network protocol stack, such as http, mail, ftp, and telnet.
Various primitives and calls to functions defined in various libraries of the middleware layer are
embedded in the user program code. There exist several libraries to choose from to invoke primitives for the
more common functions – such as reliable and ordered multicasting – of the middleware layer.
There are several standards such as Object Management Group’s (OMG) common object request broker
architecture (CORBA), and the remote procedure call (RPC) mechanism. The RPC mechanism conceptually
works like a local procedure call, with the difference that the procedure code may reside on a remote machine,
and the RPC software sends a message across the network to invoke the remote procedure. It then awaits a reply,
after which the procedure call completes from the perspective of the program that invoked it.
Other Examples: RMI, DCOM
MOTIVATION
1. Inherently distributed computations In many applications such as money transfer in banking, or reaching
consensus among parties that are geographically distant, the computation is inherently distributed.
2. Resource sharing Resources such as peripherals, complete data sets in databases, special libraries, as well as
data (variable/files) cannot be fully replicated at all the sites because it is often neither practical nor cost-
effective. Further, they cannot be placed at a single site because access to that site might prove to be a
bottleneck. Therefore, such resources are typically distributed across the system. For example, distributed
Downloaded by NADHIYA S ()
, lOMoARcPSD|11981679
databases such as DB2 partition the data sets across several servers, in addition to replicating them at a few sites
for rapid access as well as reliability.
3. Access to geographically remote data and resources In many scenarios, the data cannot be replicated at
every site participating in the distributed execution because it may be too large or too sensitive to be replicated.
For example, payroll data within a multinational corporation is both too large and too sensitive to be replicated
at every branch office/site. It is therefore stored at a central server which can be queried by branch offices.
Similarly, special resources such as supercomputers exist only in certain locations, and to access such
supercomputers, users need to log in remotely.
4. Enhanced reliability A distributed system has the inherent potential to provide increased reliability because
of the possibility of replicating resources and executions, as well as the reality that geographically distributed
resources are not likely to crash/malfunction at the same time under normal circumstances. Reliability entails
several aspects:
● availability, i.e., the resource should be accessible at all times;
● integrity, i.e., the value/state of the resource should be correct, in the face of concurrent access from
multiple processors;
● fault-tolerance, i.e., the ability to recover from system failures.
5. Increased performance/cost ratio By resource sharing and accessing geographically remote data and
resources, the performance/cost ratio is increased.
6. Scalability As the processors are usually connected by a wide-area network, adding more processors does not
pose a direct bottleneck for the communication network.
7. Modularity and incremental expandability Heterogeneous processors may be easily added into the system
without affecting the performance, as long as those processors are running the same middleware algorithms.
Similarly, existing processors may be easily replaced by other processors.
MESSAGE-PASSING SYSTEMS VERSUS SHARED MEMORY SYSTEMS
Shared memory systems are those in which there is a (common) shared address space throughout the
system. Communication among processors takes place via shared data variables, and control variables for
synchronization among the processors.
All multicomputer (NUMA as well as message-passing) systems that do not have a shared address space
provided by the underlying architecture and hardware necessarily communicate by message passing.
Conceptually, programmers find it easier to program using shared memory than by message passing.
Emulating message-passing on a shared memory system (MP →SM)
The shared address space can be partitioned into disjoint parts, one part being assigned to each
processor. “Send” and “receive” operations can be implemented by writing to and reading from the
destination/sender processor’s address space, respectively. Specifically, a separate location can be reserved as
the mailbox for each ordered pair of processes. A Pi–Pj message-passing can be emulated by a write by Pi to the
Downloaded by NADHIYA S ()
