Understanding Message Passing in Distributed Systems
Explore the key concepts of message passing in distributed systems, covering inter-process communication, desirable features like simplicity, efficiency, and reliability, different methods for information sharing, and the importance of synchronization and buffering. Dive into the intricacies of encoding and decoding message data, handling failures, and group communication in distributed environments.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Chapter 2: Message Passing (5) 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
1.1 Introduction LO: State inter-process communication between two process
1.1 Introduction 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
1.1 Introduction Contd. 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 Shared common memory area P1 P1 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 P1 P1 4
1.2 Desirable Features LO: list the features of IPC w.r.t. Distribution Systems
1.2 Desirable Features Simplicity Uniform Semantics Efficiency Reliability Correctness Flexibility Security Portability 6
1.2 Desirable Features Contd. Simplicity Should be simple and easy to use Uniform Semantics Semantics of remote and local communications should be as close as possible 7
1.2 Desirable Features Contd. 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
1.2 Desirable Features Contd. Reliability 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
1.2 Desirable Features Contd. 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
1.2 Desirable Features Contd. 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
1.2 Desirable Features Contd. 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
1.2 Desirable Features Contd. 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
1.2 Desirable Features Contd. Portability It should be possible to easily construct a new IPC facility on another system by reusing 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
A typical message structure Issues in IPC Message: meaningful to receiver(format). Format: header, variable size collection, typed data object Structural Info. Addresses Sequence number Or Message ID Actual data Or pointer to the data Nos. of bytes / elements Type Process address Process address Variable size Payload Fixed Size - HEADER Fig.: A typical message structure 15
1.3 Synchronization LO: identify the role synchronization in inter-process communication
1.3 Synchronization Classification of Synchronization Semantics Blocking Semantic Primitive: Execution of invoker is blocked Non-Blocking Semantic Primitive: Execution of invoker is not blocked 17
1.3 Synchronization Contd. Send Primitives 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. 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 18
1.3 Synchronization Contd. 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 19
1.3 Synchronization Contd. 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
1.3 Synchronization Contd. Synchronous -Asynchronous Communication Synchronous: both send and receive primitives use blocking semantics Otherwise it is asynchronous. SenderReceiver Receive (msg) Send (msg) Exe.n Resumed Execution Resumed Send (ack) Executing State Blocked State Fig.: Synchronous mode with blocking type semantics 21
1.4 Buffering In IPC, message passing is done by copying message body from sending process address space to receiving process address space Achieved possibly via address spaces of the kernels of the sending and receiving computers 23
1.4 Buffering Contd. 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
1.4 Buffering Contd. Single-Message Buffer Single message buffer capacity at receiver Used for synchronous communication Fig.: Msg transfer in Synchronous send with single-msg buffering strategy (Two copy operations are needed) 25
1.4 Buffering Contd. Finite-Bound (or Multiple-Message) Buffer Buffer with finite used Buffer overflow may occur Unsuccessful communication Flow controlled communication Fig. Finite-Bound (or Multiple-Message) Buffer 26
1.4 Buffering Contd. 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
1.5 Multi-Datagram Messages 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 *
1.5 Multi-Datagram Messages Contd. 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) *
1.5 Multi-Datagram Messages Contd. 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. *
1.5 Multi-Datagram Messages Contd. 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 *
1.6 Encoding & Decoding of Data 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. *
1.6 Encoding & Decoding of Data 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] *
Process Addressing Addressing or naming of the processes involved in an interaction message-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
Methods to Identify a Process (naming) Case: Identify a process is by a combination of machine_id and local_id. Limitation: It 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
1.7 Failure Handling a) Loss of Request message b) Loss of Response Message c) Unsuccessful execution of request *
1.7 Failure Handling Contd. Client Server Request Blocked State Executing State Acknowledgment Response Acknowledgment Fig.: Four-Message Reliable IPC Protocol *
1.7 Failure Handling Contd. Client Server Request Blocked State Executing State Response Acknowledgment Fig.: Three-Message Reliable IPC Protocol *
1.7 Failure Handling Contd. Client Server Request Blocked State Executing State Response Fig.: Two-Message IPC Protocol *
Fault tolerant communication
Idempotency An idempotent operation produces the same results without any side effects no matter how many times it is performed with the same arguments.
Exactly once semantics An example of exactly-once semantics using request identifiers and reply cache
Lost and Out-of- Sequence Packet in Multidatagram 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.
1.8 Group Communication 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 *
1.8 Group Communication Contd. 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 *
