Group Communication

Contents:

What is group communication
Communication modes
Quiz

Root

What is Group Communication

Transis provides group communication services, i.e. omission free multicast among process groups. A process group is identified by a name (a string), selected by the user. A process can send a message to a group, and be certain that all members of the group receive it (unless they crash or a network partition occurs).

When a process connects to Transis, a singleton group consisting of itself only is automatically formed, messages for this process are sent to this group.

Transis maintains the membership (list of connected processes) for each group. The membership in process groups is dynamic: Processes may join and leave groups. A process may leave a group due to a user's request or a process crash. Furthermore, a group may partition due to a network partition. Process may join the group, and previously disconnected partitions may re-merge. Changes in group membership are reported to all group members through special configuration change messages. Membership changes are delivered in the same order to all the members who deliver them. Here's an example of using group commuication in real life. The Trans City Blue-Socks baseball team fired their coach and chose coach Bat-man to be new one. The key to good coaching is good communication with the players and management, therefore coach Bat-man decided to use Transis for all communication outside practice hours.

What groups does he use to simplify team communication?

One obvious group is the whole team, where practice hours could be announced, and every member is guaranteed to receive the information. Do you think coach Bat-Man should be a part of this group too? It is not obligatory because he can still send messages to the group without being a member. The advantage of joining the group is that he can hear all the members' reactions to his messages (don't want the players gossiping behind his back), and even more important - if any team member suddenly leaves the team (due to injury, moving to another team, etc.) he is informed through the membership service as soon as Transis recognizes it! On the other hand, the group manager will probably not want to join this group because most of the information that circulates in the group is useless to him.

Another group contains coach Bat-man and the management. Other groups could be the out-fielders group and the basemen group which practice differently as two disjoint groups. One can conduct private talks with individual players by sending messages to each one's singleton group.

Contents

Communication Modes

Transis provides several modes of multicast communication, in which different ordering properties are supported. These include:

Causal mode: This communication mode guarantees that the message order preserves the happens-before relation (after Lamport). It means that single source messages are always delivered in the order in whichthey were sent, and that a response to a message is never delivered before the message that caused it.

In a more formal way causal order is the transistive closure of: let M, M' be messages.

1. if there exists a process Q that received M, and afterwards sent M' then M -> M' (M causes the sending of M').
2. if there exists a process Q that sent M, and afterwards sent M' then M -> M' (M causes the sending of M').

Let us go back to the Blue-Socks baseball team. Coach Bat-Man decides to practice at 10 o'clock, but then the pitcher asks to postpone the practice in half an hour. If these messages are sent using causal mode then everyone knows the practice will take place at 10:30, since the pitcher's message causally follows coach Bat-Man's message.

Still total order is not achieved - two messages sent without causal relation between them could be delivered in different orders to the group members. For example, if Coach Bat-Man decides to practice at 10 o'clock, and the pitcher takes a shower and shouts that there are no more hot water, then these messages can be delivered in any order to the team players.

Agreed mode: This is a total order communication mode. It guarantees that all messages are delivered in the same order to all group members. The total order created preserves causality, but agreed messages may be delayed longer than causal messages.

Safe mode: This communication mode delivers a message only after its reception is acknowledged by the low levels of the system (i.e. by the communication module in each Transis daemon) at all the destination (group's) machines. It causes the greatest delay in delivering messages.

Safe mode guarantees the following:

1. If safe message M is delieverd in a configuration that includes process P then P will deliver M unless it crashes.
2. All messages are ordered relative to a safe message.

The second guarantee means that if safe message M was multicast and delivered in a certain configuration, then any message - no matter in which communication mode it was multicast - is delivered by all processes either before M, or after M. Safe mode is therefore stronger than agreed mode since agreed mode guarantees the relative order of agreed messages only. The order on safe messages is the same as the order on agreed messages.

Contents

Quiz

Each question presents a different application that uses Transis. Name the simplest and least expensive group structure and the communication mode for each application.

Questions

1. A checkers game between two players may be run over Transis. The first player to arrive is the white, the second player to arrive is the black, and the next to arrive watch the game. The white player starts.

   Answer

2. The game Doom is played between several players. The players try to kill each other, and the winner is the player who survives last.

   Answer

3. A distributed color map is held by servers. Clients can query the color of a cretain slot in the map and update it (a client can only act through one server). The color maps held by different servers must stay consistent with each other. There are no process crashes or network partitions.
   

   Answer

4. A distributed jigsaw-puzzle is played over the network. All players try to built together the same copy of the puzzle. When the game starts there is one piece on the board. Any piece should be connected to the pieces that currently exist on the board. Only the correct piece matches its place. The target is to finish the jigsaw-puzzle as soon as possible.

   Answer

5. The same application as in 4. Only this time new players can join the game in the middle, and they should receive the current board.

   Answer

Answers

1. Answer: The group consists of the players and the crowd. The advantage of having one group instead of singleton groups is that the membership mechanism informs every member about changes in the group contents. Since the membership change messages arrive to all members in the same order there is an agreement on who plays the white and the black and who watches. The membership mechanism will also inform each player if the other player is no longer reachable.

   The communication mode is causal, since the crowd wants to view the game step be step, and the steps are causally related.

   return

2. Answer: The group consists of the players. The communication mode is agreed. Causal mode is not enough since it may happen that the two last players to survive shoot each other concurrently and then die. The causal messages notifying their deaths can arrive in any order to any of the players, hence it will not be clear who wins. Agreed mode causes the messages to arrive in the same order to all players, therefore the winner is known to all.

   return

3. Answer: This system requires a client-server communication to allow clients to operate, and a server-server communication to keep consistency among the color maps. Since processes never crash, the communication between clients and servers can be carried on through their singleton groups.
   A client-server communication can be causal.

   The servers should be members of one group, since they must exchange information to keep their maps consistent.

   A server-server communication needs some kind of total order. Causal order will not suffice, since updates are not commutative, and may happen without being causally related. This would allow several legal orderings. If several legal orderings of updates exist in the system, consistency may be invalidated.
   For example, assume there are two servers S1, S2 and two clients C1, C2. C1 communicates with S1, while C2 communicates with S2. C1 and C2 concurrently update the same slot on the map - C1 colors it blue and C2 colors it red. The servers now multicast both update messages using causal mode. Since there is no causal relation between the two updates, server S1 can receive the update message requesting blue color before the message requesting red color, while S2 can receive the update message requesting red color before the message requesting blue color. Therefore the slot held by S1 will be red, while the slot held by S2 will be blue, contradicting consistency.
   

   return

4. Answer: The group consists of all the players. The communication mode is causal: A piece can be put only when it can be connected with another piece on the puzzle. Therefore there is a causal relation between pieces on the board, that all players need to view.

   return

5. Answer: The group structure may stay the same as in 4. The general communication mode is still causal. The new player must receive the current board's contents, and this is done best by sending this message as safe. All causal messages in the network are relatively ordered with respect to this message, therefore the joining player will hold a board that is consistent with the boards held by the other players.

   return

Contents