Message Passing in Distributed Systems

 1.1   Introduction

1.2   Desirable Features

1.3   Synchronization

1.4   Buffering

1.5   Multi-Datagram Messages

1.6   Encoding & Decoding of Message Data

1.7   Failure Handling

1.8   Group Communication

1

LO: State inter-process communication between two process



Process: A program in execution



Inter Process Communication (IPC): Communication between two or

more processes



In distributed system (DS) when two computers are communicating

with each other, it means that two processes on two different

computers are communicating with each other. i.e. nothing but IPC

happens in Distributed System

3

•

Two basic methods for information

sharing :

1.

Original Sharing or Shared-Data

Approach

: Information to be shared is

in a common memory area that is

accessible to all processes involved in

IPC

2.

Copy Sharing or Message-Passing

Approach

: 

Information to be shared

is physically copied from sender

process’ address space to all receiver

process’ address space

4

LO: list the features of IPC w.r.t. Distribution Systems



Simplicity



Uniform Semantics



Efficiency



Reliability



Correctness



Flexibility



Security



Portability

6

Simplicity

Simplicity



Should be simple and easy to use



Uniform Semantics



Semantics of remote and local communications should be as

close as possible

7

Efficiency



Avoid cost of establishing and terminating connections between

the same pair of processes for every message exchange between

them



Piggybacking: Acknowledgment of previous messages with the

next message

8

Reliability 

Reliability 

Guaranteed delivery of a message

Guaranteed delivery of a message

Cases

1.

Message loss

: due to node

crash or communication link

failure

2.

Duplicate Messages

: A

reliable IPC protocol is also

capable of detecting and

handling duplicate messages

Solutions



Solution

: Acknowledgement and

retransmission on the basis of

timeouts



Solution

:  generating and

assigning appropriate sequence

numbers to messages

9

Correctness



Feature related to IPC protocols for group communication



Group Communication:

sender to 

send

 a message to a 

group

 of 

receivers

 and a receiver to

receive

 messages from 

several

senders

10

Issues related to 

Correctness 

:

1.

Atomicity

: ensures that every message sent to a group of

receivers will be delivered to either all of them or none of

them

2.

Ordered  Delivery

:  ensures that messages arrive at all

receivers in an order acceptable to the application

3.

Survivability

: guarantees that messages will be delivered

correctly despite partial failures of processes, machines, or

communication links

11

Flexibility



The IPC primitives should be such that the users have the

flexibility to choose and specify the types and levels

of

reliability

 and 

correctness

 requirements of their applications



IPC primitives must also have the flexibility to 

permit

 any kind

of 

control flow 

between the cooperating processes, including

Synchronous and Asynchronous send/receive

12

Security



A good message-passing system must be capable of providing a

secure end-to-end communication



Steps necessary for secure communication



Authentication of receiver(s) 

of a message by sender



Authentication of sender 

of a message by its receiver(s)



Encryption of a message 

before sending it over the network

13

Portability



It should be possible to 

easily construct a new IPC

 facility on

another system by 

re

using the basic design

 of the existing

message-passing system. i.e. The message-passing system

should itself be portable



Applications

written

 by using the primitives of IPC protocols of

message-passing system should be portable.

14

Issues in IPC



Message

: meaningful to receiver(format).



Format

: header, variable size collection, typed  data object

15

Fig.: 

A typical message structure

LO: identify the role synchronization in inter-process communication

Classification

 of Synchronization Semantics



Blocking Semantic Primitive

: Execution of invoker is 

blocked



Non-Blocking Semantic Primitive

: Execution of invoker is 

not

blocked

17

Send  

Primitives



Blocking

 Send Primitive:

After execution of the send

statement,  

sending

 process is

blocked

until

 it receives an

acknowledgment

 from the receiver



Non-Blocking

 Send Primitive:

After execution of the send

statement, the 

sending

 process is

allowed

 to proceed with its

execution

Receive  

Primitives



Blocking

 Receive  Primitive:  after

execution of the receive statement,

the 

receiving

 process is blocked

until it actually receives a message

.



Non-Blocking

 Receive  Primitive:

after execution of the receive

statement, the 

receiving

 process is

allowed

 to proceed with its

execution. i.e. receiving next

message.

18

Issue in a 

blocking

 Receive primitive



The receiving process could get 

blocked forever 

due to :

1.

Process  crash or

2.

Send message lost

due to communication link failure.



Solution

Use a 

timeout value 

that specifies an interval of time 

after

which the 

Receive operation is terminated with

 an 

error status

Issue in a 

non-blocking

 Receive primitive



Non-Blocking: how the receiving process knows that the message

has arrived in the message buffer?

Two methods as below-

1.

Polling

 : to 

periodically

poll

 the kernel 

to check 

if the 

message

 is

already available 

in

 the 

buffer

2.

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 

receiving

 process

20

Synchronous -Asynchronous Communication



Synchronous: both send and receive primitives use blocking semantics



 Otherwise it is asynchronous.

21



In IPC, message passing is done by copying message body

from sending process’ address space to receiving process’

address space



Achieved 

possibly via address space

s 

of

 the 

kernels

 of the

sending and receiving computers

23



Message-Buffering Strategies



Null  Buffer  or  No  Buffering



Message remains in sender process’ address space and the execution of the

send is delayed until the receiver executes the corresponding receive



Message is simply discarded and the timeout mechanism is used to resend the

message after a timeout period

24



Single-Message Buffer



Single message buffer capacity at receiver



Used for synchronous communication

25

F

i

g

.

:

M

s

g

t

r

a

n

s

f

e

r

i

n

S

y

n

c

h

r

o

n

o

u

s

s

e

n

d

w

i

t

h

s

i

n

g

l

e

-

m

s

g

b

u

f

f

e

r

i

n

g

s

t

r

a

t

e

g

y

       (Two copy operations are needed)



Finite-Bound (or Multiple-Message) Buffer



Buffer  with  finite  used



Buffer  overflow  may  occur



Unsuccessful communication



Flow controlled communication

26

Fig. Finite-Bound (or Multiple-Message) Buffer



Unbounded-Capacity Buffer



Asynchronous  Communication



Sender does not wait for the receiver to be ready



Unbounded-capacity message buffer to store all received messages is

needed at receiver end



All the messages sent to the receiver will be delivered

27



Maximum Transfer Unit (MTU) - Maximum size of data that

can be sent at a time at once.



A message whose size is greater than MTU has to be

fragmented into multiples of the MTU



Each fragment is sent in a packet that has some control

information in addition to the message data.



Such packet is known as a datagram

*



Single-Datagram Messages:  Messages smaller than the MTU

can be sent in a single packet



Multi Datagram Messages:  Messages larger than the MTU

have to be fragmented and sent in multiple packets.



Structure of program objects should be preserved while they are

being transmitted from the address space of sender to the

address space of receiver (i.e. receiving data should be

meaningful for receiving process)

*

Difficult to achieve in Homogeneous system since



An 

absolute pointer value loses

 its meaning when transferred

from one process address space to another.



Different program objects occupy 

varying amount of storage

space 

e.g.long integers, short integers, variable-length

character strings, and so on.

*

Solution:



Encoding Of Message Data- On Sender side program 

objects

converted to a stream 

form that is suitable for transmission



Decoding of Message Data – The process of 

reconstruction of

program objects

 from message data on the receiver side

*

Representations for the encoding and decoding in heterogeneous

systems:

1.

Tagged Representation



Each program object along with its value is encoded in the message



Receiving process is simple due to self-describing nature of the

coded data Format



Used in the ASN  (Abstract Syntax Notation) and the Mach

Distributed Operating  System

.

*

2.

Untagged representation



Only program object is encoded in the message



No information on decoding is included in the message



Receiving process must have knowledge of how to decode the

received data



Used in Sun XDR (eXternal Data Representation) and Courier

[Xerox 1981]

*



Addressing or naming

 of the processes involved in an

interaction m

essage-based communication 

.



For greater flexibility in message-passing supports two types of

process-addressing:

1.

Explicit addressing

. The process with which communication is

desired is 

explicitly named as a parameter 

in the communication

primitive used.

2.

Implicit addressing 

or 

functional addressing 

: The process willing

to communicate does not explicitly name a process for

communication. The sender names a server instead of a process



Case

: Identify a process is by a combination of 

machine_id 

and

local_id

.



Limitation: 

I

t does not allow a process to migrate.



Overcome through:

1.

Process can be identified by 3 fields:

1.

machine_id: of node which the created process

2.

local_id: local identifier generated by same node

3.

machine_id: location (node) of the process.

2.

Each process has two identifiers:

1.

a high-level name i.e. machine independent (an ASCII string)

2.

The low-level name i.e. machine dependent

a)

Loss of Request

message

b)

Loss of Response

Message

c)

Unsuccessful

execution of

request

*

*

Fig.: Four-Message Reliable IPC Protocol

*

*

•

An idempotent operation

produces the same results

without any side effects no

matter how many times it is

performed with the same

arguments.

•

An example of

exactly-once

semantics using

request identifiers

and reply cache

•

A simple way to ensure this is to

acknowledge each packet separately

called stop-and-wait 

protocol.

•

To improve communication

performance, a better approach

is to use a single

acknowledgment packet for all

the packets of a multidatagram

message called 

blast protocol.



One-to-One communication



Also known as point-to-point, or unicast communication



Single-sender process sends a message to a single-receiver process



One-to-Many communication



single sender send message to multiple receivers



A special case of multicast communication is broadcast

communication

*

*



Many-to-One communication



Multiple senders send messages to a single receiver



Many-to-Many-communication



Multiple senders send messages to multiple receivers



It is implicit combination of one-to-many and many-to-one



In addition, an important issue related to many-to-many

communication scheme is that of ordered message delivery



Ordered message delivery ensures that all messages are delivered to

all receivers in an order acceptable to the application



Three types of Ordering the message



Absolute Ordering



Consistent Ordering



Causal Ordering

*

In case of one-to-many communication receiver processes of a

message form a group. groups are of two types – closed and open.



A closed group

 is one in which only the members of the group

can send a message to the group.

An 

outside process cannot send a message to the group as a

whole

, although it may 

send a message to an individual

member of the group



An open group 

is one in which 

any process in the system can

send a message to the group as a whole

.



Two-level 

naming scheme is normally used for group

addressing:

1.

The high-level group name is an ASCII string that is independent of

the location of the processes in the group.

2.

On the other hand, the low-level group name depends to a large

extent on the underlying hardware.



On some networks it is possible to create a special network

address to which multiple machines can listen. Such a network

address is called a multicast address.

Multicasting is 

alwasy 

asynchronous communication 

due to :



It is 

unrealistic 

to 

expect 

a 

sending 

process to 

wait until all the

receiving processes 

that 

belong 

to the multicast 

group 

are ready

to receive the multicast message.



The 

sending 

process 

may 

not be aware 

of all the receiving

processes that belong to the multicast group.

Unbuffered multicast



If the receiving process is 

not in a ready 

state to receive,

message get 

lost

.



Therefore, the message is 

received only 

by those processes of

the multicast group that are 

ready to receive 

it.

Buffered multicast



The message is buffered for the receiving process, so each

process of the multicast group will eventually receive the

message.

Ahamad and Berstain [1985] described the following two types of

semantics for one-to-many communications:



Send-to-all semantics



Bulletin-board semantics



Send-to-all semantics

. A copy of the message is sent to each

process of the multicast group and message is buffered until it

is accepted by the process.

Ahamad and Berstain [1985] described the following two types of semantics for

one-to-many communications:



Send-to-all semantics



Bulletin-board semantics



Bulletin-board semantics:

 A message to be multicast is addressed to a

channel instead of being sent to every individual process of the multicast

group. From a logical point of view, the channel plays the role of a bulletin

board. A receive process copies the message from the channel instead of

removing it when it makes a receive request on the channel.

Bulletin-board semantics is more flexible than send-to-all

semantics because it takes care of the following two factors that

are ignored by send-to-all semantics:



The 

relevance 

of message to a particular receiver may 

depend

on the 

receiver’s 

state

.



Messages not accepted within a certain time, after transmission

may no longer be 

useful

; their value may 

depend on the

sender’s 

state

.

Different applications require different 

degrees of reliability



The 

0-reliability.

 No response is expected by the sender from any of

the receivers.



The 

1-reliability. 

The sender expects a response from any of the

receivers.



The 

m-out-of-n-reliable

. The multicast group consists of n receivers

and the sender expects a response from m (1<m<n) of the receivers.



All-reliable

. The sender expects a response message from all the

receivers of the multicast group.

Atomic multicast (reliable multicast) has an 

all-or-nothing

property. i.e. , when a message is sent to a group by atomic

multicast, it is either received by 

all the surviving (correct)

processes that 

are members of the group or else it is not received

by any of them.



In this case, the kernel of the sending machine sends the

message to all members of the group and waits for an

acknowledgment from each member.

The above approach is 

not sufficient 

when 

considering 

possible

failures 

of the sender’s machine or a receiver’s machine.

Each message has a 

message identifier field to distinguish

 it from all

other messages.



The 

kernel of the sending 

machine sends the message to all members

of the group and 

uses timeout-based re-transmissions 

as in the

previous method



A process that 

receives checks for identifier field

, if its automic then

the receiver 

also performs an atomic multicast

 of the same message,

sending it to the same multicast group

This method ensures that 

eventually 

all the surviving processes of the

multicast group will 

receive the message 

even if the 

sender machine

fails

The single receiver may be



Selective Receiver 

specifies a unique sender

; a message

exchange takes place only if that sender sends a message.



Nonselective receiver 

specifies a 

set of senders

, and 

if any one

sender in

the set 

sends a message to this receiver, a message

exchange takes place

An important issue related to the many-to-one communication

scheme is nondeterminism i.e.

It is not known in advance which member (or members) of the

group will have its information available first



An important issue related to many-to-many communication scheme is that of

ordered message delivery.



Ordered message delivery ensures

, that all messages are delivered to all receivers

in an order acceptable to the application

Absolute Ordering

Consistent Ordering (Total Ordering)

Causal Ordering

•

The absolute ordering semantics

ensures that all messages are

delivered to all receiver processes

in the exact order in which they

were sent.

•

One method to implement this

semantics is to use global

timestamps as message identifiers.

Assuming all machines clocks are

syn.

Absolute-ordering semantics requires

globally synchronized clocks, which

are not easy to implement.

Absolute ordering of messages

•

Most systems support consistent-

ordering semantics (total order

semantics

•

This semantics ensures that all

messages are delivered to all

receiver processes in the same

order.

However, this order may be different

from the order in which messages

were sent.

- For some applications consistent-

ordering not or weaker acceptable.

- An application can have better

performance if the message-passing

system used supports a weaker ordering

semantics that is acceptable to the

application.

- If two message-sending events are not

causally related, the two messages may be

delivered to the receivers in any order.

- Two message-sending events are said to

be causally related if they are correlated

by the happened-before relatio.