1 of 51

DISTRIBUTED COMPUTING

Sunita Mahajan, Principal, Institute of Computer Science, MET League of Colleges, Mumbai

Seema Shah, Principal, Vidyalankar Institute of Technology, Mumbai University

2 of 51

Chapter - 3�Interprocess Communication

3 of 51

Topics

Message Passing
Case Study: IPC in MACH
Group communication
Case Study: CBCAST protocol in ISIS

4 of 51

Message Passing �

5 of 51

Message Passing vs Shared Memory

6 of 51

Advantages of Message Passing Systems

Hardware match:- fit well to parallel computers
Functionality :- express parallel algorithms
Performance :- effective use of CPUs, management of memory

drawback: responsibility of programmer to

resolving data dependencies,

avoiding Deadlock and Race conditions

7 of 51

Desirable Features of Message Passing Systems

Uniform semantics :- send & receive operations for local and remote processes
Efficiency : reduce cost of setup for multiple message transfer
Reliability : DS is prone to node crash and failure so it Handling lost, duplication, acknowledgement, retransmission
Correctness: require group communication Atomicity( send to all or none of them) message should delivered correctly
Flexibility : sync/async message transfer (flow control) between S,R
Portability : new IPC on another system
Security : end to end comm.. Authenticate users-allows Encryption of msg prior to send it on network

8 of 51

Message passing process

9 of 51

IPC message format

10 of 51

IPC Message

11 of 51

Issues need to be considered in IPC protocol design?

What are the sender and receiver IDs
How many receivers are involved in the comm.
In which mode for comm: sync/async
If node(crash/link failure):what abt recovery tech
If (async comm):

what happen if receiver is not ready to receive msg

If (queue of messages) at receiver

How they ordered?

12 of 51

IPC synchronization

Ensure message is received in the buffer:

Polling
Interrupt

Message communication techniques

Synchronous communication
Asynchronous communication

13 of 51

IPC: Synchronous communication

14 of 51

IPC: Asynchronous communication

15 of 51

IPC primitives

16 of 51

Message buffering strategies

17 of 51

Null buffering

18 of 51

Null buffering with blocked receiver

19 of 51

Null buffering with non blocked receiver

20 of 51

Message buffering: single buffer

21 of 51

Message buffering: multiple message buffer

Receiver overflow handled using:

Unsuccessful communication indication
Flow control mechanism

22 of 51

Multidatagram messaging

Concept of MTU
Message sequencing and reassembly
Message contents
Message representation: tagged, untagged

23 of 51

Message data transmission

24 of 51

Process addressing techniques

Explicit addressing :send (process_id, message) and receive (process_id, message)
Implicit addressing:send_any (service_id, message) and receive_any (service_id, message)

Two level addressing : machine_id@local_id (receiver machine name)
Three level addressing: machine_id@local_id@machine_id. (Node where the process was created @ generated by the first machine@ last known location of the machine)

25 of 51

Link-based Process Addressing

26 of 51

Failure handling mechanism

IPC problems due to system failures

27 of 51

IPC Protocols

4-message reliable IPC protocol
3-message reliable IPC protocol
2-message reliable IPC protocol

28 of 51

IPC 4 message protocol

29 of 51

IPC 3 message protocol

30 of 51

IPC 2 message protocol

31 of 51

IPC Failure

32 of 51

Case Study: IPC in MACH

33 of 51

Case Study: IPC in MACH

MACH IPC Components

Ports
Messages

Message format
NetMsgServer

34 of 51

MACH message format

35 of 51

Group communication

36 of 51

Group Communication

Unicast –one to one communication
Many-to-one group communication
One-to-many or multicast group communication

37 of 51

Unicast group communication

38 of 51

Many to one communication

39 of 51

Broadcast communication

Multi cast communication

40 of 51

Types of Groups

Closed group
Open group
Peer group
Hierarchical group

41 of 51

Group management

Centralized approach
Distributed approach

42 of 51

Group addressing Message delivery

High level and low level naming scheme
For large LANs/ MANs: send message to individual group members

Send to all semantics
Bulletin board semantics

43 of 51

Reliability mechanism

Classified based on number of receivers from which sender expects a response

44 of 51

Message ordering

45 of 51

Message ordering: Absolute Ordering

46 of 51

Message ordering: Consistent ordering

47 of 51

Message ordering: Causal ordering

48 of 51

Case Study: CBCAST protocol in ISIS

49 of 51

CBCAST protocol

S: vector of the sending process attached to the message
R : vector of the receiving process
i: sequence number of the sender process
Runtime system tests following conditions

S[i] = R [i] + 1
S[j] <= R[j] for j <> i

50 of 51

CBCAST protocol in ISIS

51 of 51

Summary

Message Passing
Case Study: IPC in MACH
Group communication
Case Study: CBCAST protocol in ISIS