0
20kviews
Explain group communication in message passing.
2
267views

• A group is a collection of processes that act together in some system or user specified way.

• The key property that all groups have that when a message is sent to the group; itself all the members of the group receive it.

• It is a form of one to many communication.

• One – to - many

a. Group management

c. Message delivery to receiving process

d. Buffered and unbuffered multicast

e. Flexible reliability in multicast communication

f. Atomic multicast

g. Group communication primitives

• Single sender and multiple receiver is also known as multicast communication

• Broadcast is a special case of multicast communication.

a. Group Management

• In case of group communication the communicating processes forms a group.

• Such a group may of either of 2 types.

• Closed group is the one, in which only member can send message, outside process cannot sned message to the group as whole but can send to single member of a group.

• Open group is one in which any process in the system can send the message to group as a whole.

• Message passing provides flexibility and create groups dynamically and to allow process join or leave group dynamically.

• Centralized group server is used for this purpose but suffers from poor reliability and scalability.

• Two level naming scheme is used for group addressing.

• Multicast address is a special n/w address, packet is delivered automatically here to all m/cs listening to address.

• It broadcast address the all m/cs has to aheck if packet is intended for it or else simply discard so broadcast is less efficient.

• If network doesn’t support any addressing among two then one to one communication is used.

• First two methods send single packet but one to one sends many, creating much traffic.

c. Message delivery to receiving process

• User application uses high level group names in program.

• Centralized group server maintains a mapping of high level group names to their low level names, when sender sends message to the group. With high level name, kernel of server m/c asks the group servers low level name and list of process identifiers.

• When packet reaches m/c kernel, that m/c extract list of process IDs and forwards message to those processes belonging to its own m/c.

• If none of ID’s is matching packet is discarded.

d. Buffered and unbuffered multicast

• Send to all semantics:- A copy of message is sent to each process of multicast group and message is buffered until it is accepted by process.

• Bulletin board semantics:- Message to be multicast is addressed to channel instead of each process.

      Channel plays as a bulletin board.


e. Flexible Reliability in Multicast communication.

• In multicast mechanism there is flexibility for user definable reliability.

• Degree of reliability is expressed in 4 forms.

a) O – Reliable: - No response is expected at all.

b) I – Reliable: - Sender expects response from any one of the receiver.

c) mount of n reliable :- Sender expects response from m of n receiver.

d) All reliable : - Sender expects response from all.


f. Atomic Multicast

• All or nothing property all reliable form requires atomic multicast facility.

• Message passing system should support both atomic and non- atomic multicast facility.

• It should provide flexibility to sender to specify whether atomicity is required or not.

• It is difficult to implement atomic multicast if sender or receiver fails.

• Solution to this is fault tolerated atomic multicast protocol.

• In this protocol, each message has message identifier field to distinguish message and one field to indicate data message in atomic multicast message.

g. Group communication primitives

• In one to one and one to many send or has to specify destination address and pointer to data so some send primitives can be used for both.

• But some systems use send group primitives because

1) It simplifies design and implementation

2) It provides greater flexibilities.


Many – to – one

• Single receiver may be selective or non-selective

• Selective receiver specifies unique sender message exchange takes place only if the sender sends the message.

• Non-selective receiver specifies set of sender if any from that sends message then message exchange takes place.

• No determinism issue need to be handled here.

• Rest all factors are same as for one – to – many communication.

Many –to – many

• One to many, many to one, all issues are induced in this.

• Ordered message delivery/ event ordering.

1) Absolute ordering

2) Consistent ordering

3) Casual


1) Absolute Ordering

• It ensures that all message delivered to all receiver in exact in which they are sent.

• Used to implement is to use global timestamps as message id.

• System is assumed to have clock synchronization and when sender message timestamps is taken as id of message and embedded in message.

• Kernel of receiver m/c, saves all incoming message in separate queue.

• A sliding window is used to periodically deliver message from receiver i.e fixed time interval is selected as window size.

• Window size and properly chosen by considering maximum time for message to kernel from one m/c to other in n/w.

 2) Casual Ordering


• For some application weaker semantics acceptable.

• Such semantic is called casual ordering.

• This semantics ensures that is the sending one message is casually related to event of sending another message, two messages are delivered to all receiver in correct order, otherwise these may be delivered in any order.

• Two message sending events are said to be casually related if they are correlated by happened before relation.

• Two message sending events are casually related if there is any possibilities of second one being influenced in a way by first one.

• For 8 implementing casual ordering semantics is the CACAST protocol:

1.  Each member process of group maintaining a vector of n components, where n is the total


no. of members in group.

      a.    Each member is assigned a sequence no. from 0 to n, and the ith component of vector corresponds to member with sequence no. i

2.  To send message, a process increments he value of its own component vector and sends vector as a part of message.

3.  When message arrives at receiver size, it is buffered by runtime system.

a.   Runtime system, test two conditions given below to user process or must be delayed to ensure casual ordering.

b.    The two conditions are:

S [i] = R [i] +1     and         s [i] ≤ R [i] for all j ≠ i.

c. 1st condition ensures that receiver has not missed any message from sender and 2nd condition   ensures that sender has not get received any message that receiver has not get received.

d.    This test is needed to make sure that sender’s message is not casually related to message   missed by receiver.

e.    If message passes these tests runtime system delivers it to user process otherwise message is buffered.