UNIT – I

DISTRIBUTED COMPUTING

Definition and introduction to distributed computing

A Distributed Computing System is a collection of systems which are distributed at different
remote sites and connected using a common network like LAN, WAN etc. and are capable of
collaborating a task.
Earlier computing was performed on a single processor or Uniprocessor called as
Monolithic computing, which makes use of a single CPU processor to execute one or more
programs for each application.
Computers are considered to be independent if they don‟t share memory or program
execution space with each other. Such computers are called loosely coupled computers. And
opposite to that, we have tightly coupled computers which share memory space with each
other.
The computer programs running on independent computers collaborate with each other to
perform computing such as network services and web-based applications. Network
services are the services that run on a network provided by a special kind of program called a
server. Examples include WWW, e-mail and FTP applications.
History of distributed computing
In the beginning there were standalone computers each of which was capable of executing
stored programs. They needed to be connected using cables to exchange information with
each other.
Then came the Internet Request for Comments (RFC), RFC1, which specifies how
participating hosts can exchange information with each other through messages, whereas
there may have been individual attempts to create network applications, where the earliest
one was e-mail in which the message was sent in 1972 using a four node ARPANET. After
that, the automated file transfer mechanism was introduced, which allowed data files to be
exchanged between two or more hosts. To this day e-mail and file transfer mechanisms
remain two of the most popular network services.
After that, came the best known network service which was the World Wide Web Server
(WWW), which could allow the exchange of hypertexts (Web pages) over the network. The
WWW has since become the common platform for network applications and services
including emails, search engines, e-commerce etc.
The web was originally conceived in the 1980s by scientists at the Swiss research Institute,
CERN in GENEVA. The WWW was responsible for an explosion in the scale of the internet.
Until 1990 ARPANET was the primary data network used by scientists, researchers and
learners. But after 1990, WWW completely took over ARPANET as the primary data network
throughout the world.
Different forms of computing:
There are basically 4 forms of computing: Monolithic, Distributed, Parallel and Cooperative
computing.
Monolithic or Centralized Computing:
It is the simplest form of computing where a single computer such as a PC is used for
computing. The computer is not connected to any network and thus it can use only those
resources available locally inside that computer.
Here the computing is performed on a single processor or Uniprocessor, which makes use of
a single CPU to execute one or more programs for each application and most of the times
used by only one user at a time.
Multiple users can also engage in monolithic computing, where the users share the resources
of a single computer. This technique is known as timesharing. The computer that provides
the centralized resource is usually called as a mainframe to differentiate it from smaller
computers such as minicomputers and microcomputers. The devices called as terminals are
used to interact with the central mainframe computers.
Distributed Computing:
In contrast we have distributed computing which involves computing performed among
multiple network-connected computers, each of which has their own processor and resources.
In this method whenever a task is given it is shared among all the computers connected in the
network. Here, the user on one computer can also access the resources from some other
remote computer connected in the network. The WWW is a good example for this type of
computing where on requesting a file or web page from the browser, the file may be fetched
from yet another remote server or computer.

Parallel Computing
Similar to but distinct from distributed computing is a form of computing known as parallel
computing or parallel processing, which uses more than one processor simultaneously to
execute a single program. Parallel computing is typically performed on a single computer that
has multiple CPUs, but it is also possible to perform parallel processing by connecting the
computers in a network. However, this type of parallel processing requires very sophisticated
software called distributed processing software.
Cooperative Computing
Recently, the term distributed computing has also been applied to cooperative computing
projects such as the Search for Extraterrestrial Intelligence (SETI) and [Link]. These
are projects that parcel out large-scale computing to workstations on Internet hosts, making
use of surplus CPU cycles. Here, whenever a task is given to a computer, if the task is very
big, it can share it with another computer which is having a small task to complete and hence
the name cooperative computing.
Strengths and Weaknesses of Distributed Computing
Strength:
a) The affordability of computers and availability of network access:
Today's personal computer has computing power superior to that of the mainframe computers
of the early days, at a fraction of the size and the cost. Coupled with the fact that connectivity
to the Internet has become universally available and generally affordable, the large number of
interconnected computers makes for an ideal community for distributed computing.
b) Information Sharing among Distributed Users:
Distributed Computing provides efficient person-to-person communication facility by sharing
information over great distances. In a distributed computing system, information generated
by one of the users can be easily and efficiently shared by the users working at other nodes of
the system.
For example, a user can access his bank account details from one branch of a bank, located in
his current state from another state‟s branch.
c) Resource sharing:
Using distributed computing, organizations can pool their resources very effectively.
Different resources like information, software and hardware resources like printers, antivirus
applications etc can be effectively shared in a distributed environment. The Web, for
example, is a powerful platform for sharing documents and other resources within and among
organizations.
d) Fault tolerance:
Compared to monolithic computing, distributed computing provides the opportunity for fault
tolerance in that a resource can be replicated (or mirrored) to sustain its availability in the
presence of failures. For example, backup copies of a database can be maintained on different
systems on the network, so that when one system fails, other copies can be accessed without
disrupting the service.
e) Scalability:
With monolithic computing, the available resources are limited to the capacity of one
computer. By contrast, distributed computing provides scalability in that increasing demand
for resources can be addressed effectively with additional resources. For example, more
computers providing a service such as email can be added to the network to satisfy an
increase in the demand for that service.
f) Shorter response Times and Higher Throughput:
Due to multiplicity of processors, distributed computing systems are expected to have better
performance and provide faster results than single-processor centralized systems.
weaknesses in distributed computing are:
a) Multiple points of failure:
There are more points of failure in distributed computing. Since multiple computers are
involved, all of which depend on the network for communication, the failure of one or more
computers, or one or more network links, can spell trouble for a distributed computing
system. Thus in a distributed system, "the failure of a computer you didn't even know existed
can make your own computer unusable."
b) Security concerns:
In a distributed system, there are more opportunities for security breaches and unauthorized
attacks, whereas in a centralized system all the computers and resources are typically under
the control of a single administration and hence less vulnerable to attacks.
c) Maintenance:
As there are many computers connected to each at different remote sites, it is difficult as well
as expensive to maintain the distributed system.
Computer Programs and Processes:
A software program is an artefact constructed by a software developer using some form of
programming language. Typically, the language is a high-level one that requires a compiler or
an interpreter to translate it into machine language.
When a program is "run" or executed on a computer, it is represented as a process. On
modern computers, a process consists of an executing program, its current values, state
information, and the resources used by the operating system to manage the execution of the
program. In other words, a process is dynamic entity that exists only when a program is run.
Figure 1.2 illustrates the state transitions during the lifetime of a process. A process enters a
ready state when a program is at the start of its execution, where it is placed in a queue by the
operating system, along with other programs that are to be executed
When system resources (such as the CPU) are available for its actual execution, the process is
dispatched, at which point it enters the running state. It continues to execute until the process
must wait for the occurrence of an event (such as the completion of some input/output
operation), at which time it enters a blocked state. Once the anticipated event occurs, the
process will be placed on the execution queue and await its turn to execute once again. The
process repeats the ready-running-blocked cycle for as many times as necessary until the
execution of the process is completed, at which time the process is said to be terminated.
INTERPROCESS COMMUNICATION:
The backbone of distributed computing is Interprocess communications (IPC): the ability for
separate, independent processes to communicate among themselves to collaborate on a task.
Figure 2.1 illustrates basic IPC: Two independent processes, possibly running on separate
machines, exchange data over the interconnecting network. In this case, process 1 acts as the
sender, which transmits data to process 2, the receiver.

Fig 2.1 Interprocess Communication

In distributed computing, two or more processes engage in IPC in a protocol - a set of rules
that must be observed by the participants in data communication agreed upon by the
processes. A process may be a sender at some points during a protocol, a receiver at other
points.
When communication is from one process to a single other process, the IPC is said to be a
unicast. When communication is from one process to a group of processes, the IPC is said to
be a multicast. Figure 2.2 illustrates the concept of the two types of Interprocess
communications.

Fig 2.2 Unicast versus Multicast

Modern-day operating systems such as UNIX and Windows provide facilities for Interprocess
communications. We will call these facilities operating system-level IPC facilities, to
distinguish them from higher-level IPCs. System-level IPC facilities include message queues,
semaphores, and shared memory. It is possible to develop network software using these
system-level facilities directly. Examples of such programs are network device drivers and
system evaluation programs.
An IPC application program interface (API), also commonly expanded to application
programming interface provides an abstraction of the details and intricacies of the system-
level facilities, thereby allowing the programmer to concentrate on the application logic.

An Archetypal IPC Program Interface

Consider a basic API that provides the minimum level of abstraction to facilitate IPC. Four
primitive operations are needed. They are:

Send: This operation is issued by a sending process for the purpose of transmitting data to a
receiving process. The operation must allow the sending process to identify the receiving
process and specify the data to be transmitted.

Receive: This operation is issued by a receiving process for the purpose of accepting data
from a sending process. The operation must allow the receiving process to identify the
sending process and specify a memory space that allows the data to be stored, to be
subsequently accessed by the receiver.

Connect: For connection-oriented IPC, there must be operations that allow a logical
connection to be established between the issuing process and a specified process: one process
issues a request-to-connect (connect for short) operation while the other process issues an
accept-connection operation.

Disconnect: For connection-oriented IPC, this operation allows a previously established

logical connection to be de-allocated at both sides of the communication.
A process involved in IPC issues these operations in some predetermined order. The issuance
of each operation causes the occurrence of an event. For example, a send operation issued by
a sending process results in the event wherein data is transmitted to the receiving process,
while a receive operation issued by a receiving process results in data being delivered to the
process.
 Fig 2.3 Interprocess Communication in basic HTTP
Network service protocols can be implemented using primitive IPC operations. For example,
in basic HTTP (Hypertext Transfer Protocol, used extensively on the World Wide Web), one
process and a Web browser issues a connect operation to establish a logical connection to
another process. A Web server, followed by a send operation to the Web server, transmits data
representing a request. The Web server process in turn issues a send operation that transmits
data requested by the Web browser process. At the end of the communication, each process
issues a disconnect operation to terminate the connection. Figure 2.3 illustrates the sequence
of operations.
Event Synchronization:
A main difficulty with IPC is to execute multiple processes involved in a system
independently, with neither process knowing what takes place in the process at the other end.
Consider basic HTTP, as described above. As you can see, the two sides involved in the
protocol must issue the IPC operations in a specific order. For example the browser process
must not issue the send operation until the connect operation has completed. It is also
important that the Web server does not begin to transmit the requested data until the browser
process is ready to receive.
Furthermore, the browser process needs to be notified when the requested data has been
received so that it may subsequently process the data, including formatting and displaying the
data to the browser user.
The simplest way for an IPC facility to provide for event synchronization is using blocking,
which is the suspension of the execution of a process until operation issued by the process has
been completed.
To illustrate the use of blocking for event synchronization, consider again basic HTTP. A
browser process issues a blocking connect operation, which blocks further execution of the
process until the connection has been acknowledged by the server side. Subsequently, the
browser process issues a blocking receive operation, which suspends execution of the process
until the operation is completed (whether successfully or not). The blocking or unblocking is
performed by the operating system and is initiated by the IPC facilities, not by the
programmer. The programs for the two processes are shown in Figure 2.4.
Fig 2.4 Program flow in 2 programs involved in an IPC
The blocking will terminate subsequently when the operation is fulfilled, at which time the
process is said to be unblocked. An unblocked process transits to the ready state and will
resume execution in time. In the event that the operation cannot be fulfilled, a blocked
process will experience indefinite blocking and will remain in the blocked state indefinitely,
unless intervening measures are taken.
Blocking operations are also referred to as synchronous operations. Alternatively, IPC
operations may be asynchronous or non-blocking operations. An asynchronous operation
issued by a process will not cause blocking and therefore the process is free to continue with
its execution once the asynchronous operation is issued to the IPC facility. The process will
subsequently be notified by the IPC facility when and if the operation is fulfilled.
A non-blocking or asynchronous operation can be issued by a process when that process
may proceed without waiting for the completion of the event that the operation initiates. For
example, the receive operation issued by the Web browser must be blocking, because the
browser process must wait for the response from the Web server in order to proceed with
further processing. On the other hand, the send operation issued by the Web server can be
non-blocking, because the Web server need not wait for the completion of the send operation
before proceeding with the next operation (the disconnect), so that it may proceed to service
other Web browser processes.
Timeouts and Threading:
Although blocking provides the necessary synchronization for IPC, it is generally
unacceptable to allow a process to be suspended indefinitely. There are two measures to
address this issue. First, timeouts may be used to set a maximum time period for blocking.
Timeouts are provided by the IPC facility and may be specified in a program with an
operation. Second, a program may spawn a child process or a thread to issue a blocking
operation, allowing the main thread or parent process of the program to proceed with other
processing while the child process or child thread is suspended. Figure 2.9 illustrates this use
of a thread.
Timeouts are important if the execution of a synchronous operation has the potential of
resulting in indefinite blocking. For example, a blocking connect request can result in the
requesting process being suspended indefinitely if the connection is unfulfilled or cannot be
fulfilled as a result of a breakdown in the network connecting the two processes. In such a
situation, it is typically unacceptable for the requesting process to "hang" indefinitely.
Indefinite blocking can be avoided by using a timeout. For example, a timeout period of 30
seconds may be specified with the connect request. If the request is not completed within
approximately 30 seconds, it will be aborted by the IPC facility, at which time the requesting
process will be unblocked, allowing it to resume processing.

Fig 2.9 Using a thread for a blocking operation

Deadlocks and Timeouts:
Indefinite blocking may also be caused by a deadlock. In IPC, a deadlock can result from
operations that were issued improperly, perhaps owing to a misunderstanding of a protocol,
or owing to programming errors.

Fig 2.10 A deadlock caused by blocking operations

Figure 2.10 illustrates such a case. In process 1, a blocking receive operation is issued to
receive data from process 2. Concurrently, process 2 issues a blocking receive operation
where a send operation was intended. As a result, both processes are blocked awaiting data
sent from the other, which can never occur (since each process is now blocked). As a result,
each process will be suspended indefinitely until a timeout occurs, or until the operating
systems abort the processes.
Data Representation
At the physical layer (that is, the lowest layer, as opposed to the application layer, which is
the highest) of the network architecture, data is transmitted as analog signals, which represent
a binary stream. At the application layer, a more complex representation of transmitted data is
needed in order to support data types and data structures provided in programming languages,
such as character strings, integers, floating point values, arrays, records, and objects.
Consider an integer value that needs to be sent by process 1. This value is represented in the
integer representation of Host A, which is a 32-bit machine that uses the "big-endian"
representation for multi-byte data types. (The terms big endian and little endian refers to
which bytes are most significant in multi-byte data types. In big-endian architectures, the
leftmost bytes [those with a lower address] are most significant. In little-endian architectures,
the rightmost bytes are most significant.)
Host B, on the other hand, is a 16-bit machine that uses "little-endian" representation.
Suppose the value is sent as a 32-bit stream directly from process l's memory storage and
placed into process 2's memory location. Then 16 bits of the value sent will need to be
truncated, since an integer value only occupies 16 bits on host B, and the byte order of the
integer representation must be swapped in order for the value to be interpreted correctly by
process 2.
Similarly, when heterogeneous hosts are involved in IPC, it is not enough to transmit data
values or structures using raw bit streams unless the participating processes take measures to
package and interpret the data appropriately. For our example, there are three schemes for
doing so:
1. Prior to issuing the send operation, process 1 converts the value of the integer to the 16-bit,
little-endian data representation of process 2.
2. Process 1 sends the data in 32-bit, big-endian representation. Upon receiving the data,
process 2 converts it to its 16-bit, little-endian representation.
3. A third scheme is for the processes to exchange the data in an external representation:
data will be sent using this representation and the data received will be interpreted using the
external representation and converted to the native representation.
Some well known external data representation schemes are:
• Sun XDR
• ASN.1 (Abstract Syntax Notation)
• XML (Extensible Mark-up Language)
Text-based protocols:
Data marshalling is at its simplest when the data exchanged is a stream of characters or text
encoded using a representation such as ASCII. Exchanging data in text has the additional
advantage that the data can be easily parsed in a program and displayed for human perusal.
Hence it is a popular practice for protocols to exchange requests and responses in the form of
character strings. Such protocols are said to be text-based. Text-based protocols
are communication rules that use human-readable plain text (like ASCII or UTF-8) for
commands and data. Making them easy to inspect, debug, and implement, unlike binary
protocols which use compact machine code for efficiency. Many popular network protocols,
including FTP (File Transfer Protocol), HTTP and SMTP (Simple Mail Transfer Protocol) are
text-based.
Key Characteristics:
• Human-Readable: Data is presented as characters, easily understood by people.
• Interoperable: Open standards (JSON, XML, plain text) allow different systems to
communicate easily.
• Self-Descriptive: Data often includes names (semantics) explaining what it means.
• Easy to Implement: Quick to build and debug due to simplicity.
• Less Efficient: Can use more bandwidth than binary protocols because text takes more
space than compact binary data (e.g., number 20020 uses 5 bytes as text vs. 2 bytes as
a binary integer).
Request-Response Protocols:

An important type of protocol is the request-response protocol. In this protocol, one side
issues a request and awaits a response from the other side. Subsequently, another request may
be issued, which in turn elicits another response. The protocol proceeds in an iteration of
request-response, until the desired task is completed.
A request-response protocol is a communication pattern where a client sends a message
(request) to a server, and the server processes it and sends back a message (response),
forming the backbone of client-server systems like the web (HTTP). This simple, yet
powerful, exchange involves a client initiating a connection, sending a request with details
like method (GET/POST) and target, and the server returning a response with a status code
(200 OK, 404 Not Found) and requested data, enabling seamless data exchange.
The popular network protocols FTP, HTTP, and SMTP are all request-response protocols.
How it Works (HTTP Example)
1. Client Request: A browser (client) sends an HTTP request to a server, specifying
what it wants (e.g., a webpage) using a method (like GET) and a URL.
2. Server Processing: The server receives the request, processes the action (like
fetching data from a database), and prepares a response.
3. Server Response: The server sends back an HTTP response containing a status code
(success/error) and the requested content (HTML, images).
4. Client Processing: The browser receives the response, interprets the status code, and
renders the content for the user.
Key Components
• Client: Initiates communication (e.g., web browser, app).
• Server: Listens for requests and provides resources (e.g., web server, database
server).
• Request Message: Contains method, URL, headers, and body.
Response Message: Contains status code, headers, and body.
Common Protocols Using This Model
• HTTP/HTTPS: The fundamental protocol for the World Wide Web, allowing
browsers and servers to talk.
• RPC (Remote Procedure Calls): Used in distributed systems, where a client calls a
function on a remote server.

Event Diagram and Sequence Diagram:

An event diagram, introduced is a diagram that can be used to document the detailed
sequence of events and blocking during the execution of a protocol. Figure 2.11 is an event
diagram for a request-response protocol involving two concurrent processes, A and B. The
execution of each process with respect to time is represented using a vertical line, with time
increasing downward. A solid line interval along the execution line represents a time period
during which the process is active. A broken line interval represents when the process is
blocked. In the example, both processes are initially active. Process B issues a blocked
receive operation in anticipation of request 1 from process A
Process A meanwhile issues the awaited request 1 using a nonblocking send operation, then
subsequently a blocking receive operation in anticipation of process B's response. The arrival
of request 1 reactivates process B, which processes the request before issuing a send
operation to transmit response 1 to process A. Process B then issues a blocking receive for
request 2 from process A. The arrival of response 1 unblocks process A, which resumes
execution to work on the response and to issue request 2, which unblocks Process B. A
similar sequence of events follows.
Note that each round of request-response entails two pairs of send and receive operations to
exchange two messages. The protocol can extend to any number of rounds of exchange using
this pattern. Figure 2.12 uses an event diagram to describe basic HTTP. In its basic form,
HTTP is a text-based, request-response protocol that calls for only one round of exchange of
messages. A Web server process is a process that constantly listens for incoming requests
from Web browser processes. A Web browser process makes a connection to the server, and
then issues a request in a format dictated by the protocol. The server processes the request
and dispatches a response composed of a status line, header information, and the document
requested by the browser process. Upon receiving the response, the browser process parses
the response and displays the document. An event diagram is a useful device for illustrating
the synchronization events. A simplified form of diagram, known as a sequence diagram and
part of the UML notations, is more commonly used to document Interprocess
communications: In a sequence diagram, the execution flow of each participant of a protocol
is represented as a dashed line and does not differentiate between the states of blocked and
executing. Each message exchanged between the two sides shown using a directed line
between the two dashed lines, with a description label above the directed line, as illustrated in
Figure 2.12.
The sequence diagram for the basic HTTP is shown in Figure 2.13.