Chapter 2

Interprocess
Communication
 OUTLINE
• Message passing

• Group communication

• API for Internet protocol

© Oxford University Press 2013. All rights

 Inter process Communication
• A process is a program in execution
• When we say two computers of distributed system
are communicating with each other, we mean, two
processes, one running on each computer are in
communication with each other
• In distributed system, processes executing on
different computers needs to communicate with
each other to achieve a common goal
• For this purpose we need Inter Process
Communication ( IPC)
 IPC generally requires information sharing among
two or more processes:
• Original Sharing or Shared memory Approach: The
information to be shared is kept in a common
memory area that it accessible to all the processes
involved in IPC
• Copy sharing or message-passing approach :
Information to be shared is physically copied from
sender process’s address space to the address space
of all the receiver processes and this is done by
transmitting the data to be copied in the form of
messages
 Message Passing vs Shared Memory

P1 P2

Shared Common
P1 P2
Memory Area
 Desirable features of Good Message
Passing Systems
• Simplicity
• Uniform Semantics
• Efficiency
• Reliability
• Correctness
• Flexibility
• Security
• Portability
• Simplicity: Simple send and receive primitives
are used to enable the process to
communicate by exchanging messages.
• Uniform Semantics: It is used for both send
and receive operations and for local as well as
remote processes.
• Efficiency: An optimization technique for
efficient message passing is to avoid repeated
costs of set up and termination of correction
for multiple message transfers between the
same processes.
• Reliability: A good message passing system
should cope with failures and guarantee
message delivery.
• Correctness: correctness is related to IPC
protocols and is often required for group
communication.
• Flexibility: the message passing system should
be flexible enough to cater to the varied
requirements of the application in terms of
reliability.
• Security : A good message passing should
provide secure end to end communication
through authentication.

• Portability : It should be possible to construct

a new IPC facility on another system by
reusing the basic design of the existing
message passing system.
Message Passing Process
IPC Message Format
IPC Message
 IPC Synchronization
How the receiving process knows that the message
has arrived in the message buffer. Two methods are
used:
 Polling: A test primitive is provided to allow the
receiver to check the buffer status. So, receiver can
periodically poll the kernel to check if message is
already available in the buffer
 Interrupt: When the message has been filled in the
buffer and is ready for use by the receiver, a software
interrupt is used to notify the process. It is highly
efficient but user-level interrupts makes
programming difficult
• Message communication techniques
– Synchronous communication
– Asynchronous communication
• When both send and receive primitives of a
communication between two processes use
blocking semantics, the communication is said
to be synchronous, otherwise it is
asynchronous
• For synchronous communication, sender and
receiver must be synchronized to exchange a
message
IPC: Synchronous Communication
IPC: Asynchronous Communication
 Synchronization
• Semantics used for synchronization is broadly
classified as blocking and nonblocking types
• Further it is again divided as blocking send
primitive and nonblocking send primitive,
blocking receive primitive and nonblocking
receive primitive
• In case of blocking send primitive, after
execution of send statement, sending process
is blocked , until it receives an
acknowledgement from receiver. For non
blocking primitive, after execution of send
statement, sender is free for other work
 Synchronization
• In case of blocking receive primitive, after
execution of receive statement, receiving process
is blocked , until it receives a message. For non
blocking receive primitive, after execution of
receive statement, returns control almost
immediately just after telling the kernel where the
message buffer is.
• Message –passing primitives such as blocking and
non-blocking are used to achieve synchronization
during IPC.
 Buffering
• Messages can be transmitted from one process to
another by copying the body of message from the
address space of sending process to address space of
receiving process
• In some cases, the receiving process may not be
ready to receive the message but it wants the
operating system to save the message for later
reception
• Operating system will rely on the receiver having a
buffer in which messages can be stored prior to the
receiving process executing specific code to receive
the message
• Message buffering strategy is strongly related to
synchronization strategy
Message Buffering Strategies
 Null Buffering

In case of no buffer, there is no temporary

space to store the message
 Null Buffering with Blocked Receiver
If receiver is not ready to
receive, the sending
process is blocked and
the send is delayed until
receiver executes the
receive primitive. So
when receiver executes
receive, an
acknowledgement is sent
to the sender, causing it
to unblock and send the
message successfully
Null buffering with blocking
mechanism
Null Buffering with Non-blocked Receiver

Message is
discarded and
timeout
mechanism is
used to resend
the message.
The sender
gives up after
retrying for a
pre-decided
amount of time Null buffering with non-blocking mechanism
 Single Message Buffer
• A buffer having the capacity to store a single
message is used on the receiver’s node
• In synchronous system, an application may have
atmost one outstanding message at a time
• Main idea is to keep message ready for use at
location of the receiver
• Request message is buffered on receiver’s node, if
receiver is not ready
• Buffer may be located either on kernel’s address
space or the receiver process’s address space
• This technique involves two copy operations.
Message Buffering: Single Buffer

Single-message buffering
 Infinite capacity buffer
• Used in asynchronous mode of application
• Since sender does not wait for receiver to be ready,
there may be several pending messages that has not
been received by the receiver
• An unbounded capacity message buffer that can
store all unreceived messages is needed to support
asynchronous communication
• It has assurance that all messages will be delivered
• But this is practically impossible
Message Buffering: Multiple
Message Buffer
 Multiple Message buffer
• Since buffer is finite, a strategy is needed for handling buffer
overflow. Can be dealt in following ways:
• Receiver overflow handled using
– Unsuccessful communication indication
– Flow control mechanism

o Unsuccessful Communication: Message transfer fails when

there is no more buffer space. But this makes message
passing less reliable
o Flow-Control Communication: Sender is blocked until receiver
accepts some messages , thus creating space in buffer for new
messages. This introduces synchronization between sender
and receiver and may result in unexpected deadlocks
 Multidatagram Messages
• All networks have an upper bound on size of data that can be
transmitted at a time
• This size is known as maximum transfer unit (MTU) of a network
• Message whose size is greater than MTU has to be fragmented
into several MTU’s and are sent separately
• Each fragment is sent in a packet that has control information in
addition to message data
• Each packet is known as Datagram
• Messages smaller than MTU can be sent in a single packet and are
called single-datagram messages
• Others are called as multidatagram messages
• Different packets of multidatagram messages bear a sequential
relationship to one another
• Disassembling and reassembling of multidatagram messages is
the responsibility of message passing system
 Multidatagram Messaging
• Concept of MTU
• Message sequencing and reassembly
• Message contents
• Message representation: tagged, untagged
Message Data Transmission
Failure Handling Mechanism
 Failure Handling
• Distributed system is prone to node crash or communication
failure. Such failures may lead to:
 Loss of request message
 Loss of response message
 Unsuccessful execution of request
• IPC protocol of message passing system uses retransmission
of messages after timeouts and return of acknowledgement
message to sender by receiver
• Kernel of sending message is responsible for resending the
message after timeout and it frees the sending process only
when acknowledgement is received
 IPC Protocols
• Timeout period is slightly more than approximate round trip
between nodes plus the average time required for executing the
request
• IPC protocol is designed based on retransmission of message
after a timeout if acknowledgement is not received.
• IPC protocols are classified into the following:

• 4-message reliable IPC protocol

• 3-message reliable IPC protocol

• 2-message reliable IPC protocol

 IPC 4 Message Protocol
If
acknowledgme
nt not
received
either by
client or
server then
they
retransmit
after the time
out period
Blocked

Executing
 IPC 3 Message Protocol
If reply not
received by
Result of processed client and
Request Is sufficient acknowledgem
acknowledgement
ent not
received by
server then
retransmit after
the time out
period

Blocked

Executing
 IPC 2 Message Protocol
If reply not
received by
client then
retransmit
request after
the time out
period

Blocked

Executing
Fault tolerant communication between
client and server
 Group Communication
• Unicast –one to one communication

• Many-to-one group communication

• One-to-many or multicast group communication

Special case of multicast is broadcast communication
Unicast Group Communication
Many-to-One Communication
Multicast Communication

Broadcast Communication
• Server can multicast a message to all the server
processes, requesting that a free server volunteer to
serve the current request
• It then selects the first server that responds
• Some facilities provided are:
o Group management
o Group addressing
o Message delivery to Receiver Processes
o Flexible reliability in Multicast communication
o Atomic multicast
o Group Communications Primitives
 Types of Groups
• Receiver processes of a message forms a group
• Closed group : Closed groups are those groups in which only
the members of the group can send messages to the group
members
• Open group : Open group is one in which any process(not the
member of the group) in the system can send a message to the
group as a whole
• Peer group : is symmetric all the processes are equal No one is
boss and all the decisions are made collectively. If one of the
process crashes , the group becomes smaller but continues.
• Hierarchical group : One process is the coordinator and others
are workers. Any request for work (internal or external) is send
to the coordinator and coordinator allocates it to a worker. If
coordinator is down the entire group stops.
Group Addressing Message Delivery
• For single LAN: High For one to many
level naming and low communications -
level naming • Send to all semantics
(multicast address &
• Bulletin board
broadcast address)
semantics
• For large LANs/
MANs: send
individual message to
each group members
 Group addressing
• Two level naming scheme is used for group addressing
• High level location independent group name is ASCII string and
low level group name location dependent for a process belonging
to the group.
• On some n/w it is possible to create a special network address to
which multiple machines can listen. Such a n/w address is called
as multicast address. Multicast address is used as low level group
name
• Network with broadcasting facility declare a certain address,
such as zero, as a broadcast address. Here broadcast address is
delivered to all the members as the group members have the
same low level name.
• One to one communication mechanism can be used to
implement group communication facility for large networks. The
kernel of the sender sends the message packet separately to
each machine that has a process belonging to the group. Low
level name of a group contains the list of machine identifiers of
all machines that have a process belonging to the group
 Message delivery to Receiver Processes

Sender
Sender kernel Group Server

High level group name

Low level group name

List of process
identifiers
packet
Of all the processes
Receiver Receiver for each group
kernel attached to message
• If sender sends a message to a group specifying its high
level names then the kernel of the sending machine
contacts the group server and gets the low level names
of the group and attaches the list of process identifiers to
the message.
• low level group name is either multicast or
broadcast ,kernel simply sends the packet to the
multicast/broadcast address
• low level group name is list of machine identifiers, kernel
sends a copy of packet separately to each machine in the
list
• When the packet reaches a machine, the kernel of that
machine extracts the list of process identifiers from the
packet and forward the message in the packet to those
processes in the list that belongs to its own machine
 Message Delivery
• Two types of semantics:
o Send to all: Copy of each message is sent to all
processes of the group and the message is buffered
until it is accepted by the process
o Bulletin board: Message is addressed to a channel
instead of sending to individual processes. Channel
plays a role of bulletin board. The process that have
receive access right on the channel constitute the
multicast group. The receiver process copies it from
the channel instead of removing it. So it is like
posting on the bulletin board. The message is
withdrawn from the sender as soon as bid period is
over
 Reliability Mechanism
• In one to many communication, degree of reliability is normally expressed in the following
form:
• Classified based on number of receivers from which sender expects a response i.e. The
sender can specify the number of receivers from which the response is expected
 The 0 – reliable

• No response is expected by the sender from

any of the receivers
• Useful in asynchronous multicast in which
sender does not wait for the response
• Eg: Synchronous multicast like Time generator
signal
 The 1 – reliable

• Sender expects a response from any of the

receivers
• Egs: Server manager multicasts a message to
all servers to volunteer to serve a current
request and selects the first serevr that
responds
 The m out of n – reliable

• Sender expects a response from m out of the

n receivers
• Egs: Majority consensus algorithms used for
consistency control of replicated information
 All - reliable

• Sender expects a response form all the

receivers
• Egs: A message for updating the replicas of a
file is multicast to all file servers having a
replica of the file
 Many to Many Communication
• Multiple senders send messages to multiple receivers
• Important issue related to this is ordered message
delivery which ensures that messages are delivered to
all receivers in an order acceptable to an application
• When two senders send messages to update the same
record of a database to two server processes having a
replica of the database. If messages are received by 2
receivers from 2 senders in different order, then there is
loss of consistency
• This requires message sequencing
• Commonly used semantics for ordered delivery of
multicast messages are: absolute ordering, consistent
ordering and causal ordering
S1 R1 R2 S2

m1 m2

m2 m1

No ordering constraint
For message delivery
Message Ordering
Message Ordering: Absolute Ordering
• Ensures that all messages are delivered to all
receiver processes in the exact order in which
they were sent
• One method is to use global timestamps as
identifiers. Every system is assumed to have a
clock and are synchronized with each other
• When a sender sends a message, the clock
value is taken as the identifier of that message
and is embedded in the message
• Kernel of each receiver’s machine saves all
incoming messages meant for a receiver in a
separate queue
• Sliding window mechanism is used to
periodically deliver the messages from queue to
the receiver i.e.
• A fixed time interval is selected as a window size,
and periodically all messages whose timestamp
values fall within the current window and
delivered to the receiver
• Messages whose value falls outside the window
are left in the queue, because of the possibility
that a message having timestamp value lower than
that of other messages may still arrive
• Window size is properly chosen taking into
consideration the maximum possible time that
may be required by the message to go from one
machine to other in a network
Message Ordering: Consistent Ordering
 Message Ordering:
Consistent Ordering

• Ensures all messages are delivered to all receiver

processes in the same order
• This order may be different from the order in which
messages were sent
• One method to implement this scheme is to treat
many to many as a combination of one to many and
many to one
• Kernels of sending messages send to single server
known as sequencer that assigns sequence numbers to
the messages and then multicasts it
 Message Ordering: Consistent
Ordering
• The kernel of each receiver machine saves all
incoming messages meant for the receiver in a
separate queue
• Messages in queue are delivered immediately
to the receiver unless there is a gap in the
message identifier, in which case messages
after the gap are not delivered until the ones
in the gap have arrived
• Subject to single point failure and has poor
reliability
 Message Ordering: Causal Ordering

1 is sent to R1, R2, R3. m2 is sent to R1, R2 and R3. On receiving m1, R1 inspec
d creates a new message m3. m3 is causally related to m1, so has to be delivere
proper Order (m1 before m3)
• Ensures that if the event of sending one message is
causally related to the event of sending another
message, the two messages are delivered to all
receivers in correct order
• If 2 messages sending events are not causally related,
the two messages may be delivered to the receiver in
any order
• 2 messages are said to be causally related if there is
any possibility of the second one to be influenced by
the first one
• Basic concept is that when it matters messages are
delivered in proper order else they are not
 CBCAST protocol
• Two message sending events are causally
related, if they fallow the “Happened before”
relation i.e., they are influenced by each
other.
• The CBCAST(causal Broadcast) protocol of
the ISIS system implements causal ordering
semantics.
• Each member process maintains a vector of n
components whose ith component belongs to
the member with a sequence number i.
 CBCAST protocol
• Each member process of a group maintains a vector of n
components, where n is the total number of members in the
group.
• Each member is assigned a sequence number from 0 to n and
the ith component of the vectors corresponds to the member
with sequence number i .
• In particular, the value of the ith component of the member’s
vector is equal to the number of the last message received in
sequence by this member from member i
• To send a message, The sender process increments its own
component value in its own vector by 1 and sends the
message with the vector.
• When the message arrives at receiver process’s site, it is
buffered by the runtime system. The runtime system tests the
two conditions given below to decide whether the message
can be delivered to the user process or its delivery must be
delayed to ensure causal ordering semantics
• Let S be the vector of the sender process that is attached to
the message and R be the vector of the receiver process. Also
let i be the sequence number of the sender process
• The two conditions to be tested are:
S[i] = R[i] + 1
S[j] <= R[j] for all j != i
• The first condition ensures that the receiver has not missed
any message from the sender. This is needed because two
messages from the same sender is always causally related
• The second condition ensures that the sender has not
received any message that the receiver has not yet received.
This is needed to make sure that the sender’s message is not
causally related to a message missed by the receiver
• If the message passes these two tests, the runtime system
delivers it to the user process. Else, the message is left in the
buffer and the test is carried out again for it when a new
message arrives
 Example
At process A, it is (3 2 5 1)
At process B, it is (3 2 5 1)
At process C, it is (2 2 5 1)
At process D, it is (3 2 4 1)
o The above status of the vectors means that until now process
A has sent three messages, B has sent two messages, C has
sent five messages, and D has sent 1 message.
o Now, process A sends a new message to other processes and
attaches a vector to the message(4 2 5 1). The message is
sent to processes B, C and D. The receiver runtime systems
buffer the messages and check if both the tests are satisfied.
• The message can be delivered to B because it passes both
tests
A[1] = B[1] + 1
A[2] < = B[2]
A[3] < = B[3]
A[4] < = B[4]
• However, the message has to be delayed by the runtime
systems of sites of processes C and D because the first test
fails at the site of process C and the second test fails at the
site of process D
• A good message passing system should support atleast
consistent and causal ordering semantics and should provide
the flexibility to the users to choose one of these in their
applications
 Vectors of Vectors of Vectors of Vectors of
Process A Process B Process C Process D

5 4 2 3 5 4 2 3 4 4 2 3 5 3 1 3

Process A sends a new message

To other processes
Mess
6 4 2 3
data

deliver

Delay because the Delay because

Condition A[1] = C[1] + 1
The condition
Does not hold A[2] < = D[2]
A[3] < = D[3]
Does not hold
 API for Internet Protocol
• Synchronous Communication
Both the sending and receiving processes synchronize at every
message so that both send and receive primitives are blocking
operations. When a send is issued, the sending process is blocked
until the receive command is issued, and the other process is
blocked until the message is received.

• Asynchronous Communication
The send is a non-blocking command. The issuing process is allowed to
continue when the message is stored in a local buffer and then both
the transmission of the message and the sender process continues
simultaneously. The receive operation works both in blocking and
non-blocking modes.
• The message address is given in pairs (Internet
address and local port)
• The port is an integer number. It has exactly one
receiver but can have multiple senders.
• Any process can use multiple ports to receive
message
• Servers show their port numbers so that any client
can use it.
• The server should see that a port number for a
particular service does not change
 Sockets
• Sockets are used in both UDP (connectionless)
and TCP (connection oriented)message
communication.
• The message is transmitted from a socket of one
process to
a socket in another process
• Socket address (IP, Port number)