Group Communication is a complex topic. If you ask software developers about it, they will say that it's just making two entities communicate and thus, isn't more difficult than deciding upon a protocol and writing the code. But solid group communication is hard to build and there is considerable theory involved. Take example of a serious chat application where the order of messages as well as failure to receive them is to be taken care of.
First of all, in the presence of message lost, you face the Two Generals' Problem, which says that it's impossible to achieve agreement on a message if arbitrary number of messages can be lost. In the presence of message lost, if you send an acknowledgment for guaranteeing message delivery, the acknowledgement itself may get lost and thus you need to acknowledge the acknowledgement. But then this will continue forever. Thus, Two Generals' Problem is not solvable. You can read in detail here.
Next, in order to achieve fault tolerance, you have to consider Byzantine Faults which are based on Byzantine Generals' Problem (why distributed systems people always think of army and generals is beyond me). Byzantine Faults occur when a faulty node says different things to different nodes - it may say that I have received the message successfully to one node and report the opposite to some other node, causing confusion and inconsistency in the system. Unlike the Two Generals' problem, it's solvable but with some upper bounds on the number of faulty nodes and with lots of communication overhead.
So, we ignore fault tolerance for now. Consider, ordering of messages instead. In a serious chat application the ordering can matter a lot. If different members in a conversation get messages in different order, it can cause confusion. TCP/IP provides ordering within packets of a single message (where packets are formed at lower layers of the network protocol) that is sent via a single TCP/IP socket. But what about different sockets (different members in the conversation) or different messages sent on the same socket? There is nothing in TCP/IP which guarantees that when you send "Hello"; close the socket; open it again and then send "Goodbye", they will be received in the same order. So, what's the solution? Number the messages yourself! And on the receiving end, hold messages if they are received earlier than their predecessors.
Then comes the issue of Group Membership. Does your rock-solid chat application allow a member to join in between a conversation? If yes, what happens when somebody has sent a message but it hasn't been received by all yet, and a new member joins the group. Should he be delivered the message or should it be held back? If you deliver the message to him as well, some of the members (who received the message before the new member joined) will think that he didn't get that message, while others will think the opposite. More confusion and inconsistency.
Some of you might think that considering all these issues is an overkill for a chat application. What about a distributed group of servers trying to synchronize their end-of-day activity?
As I said in the beginning, there is more to group communication than we casually think of. Ensemble is a library written in Objective Caml that handles most of the theoretical issues involved with Group Communication. It provides simple to use api for Java, C, C# and ML. It's highly modular and reconfigurable. Do check out the features it provides if you are interested in group communication. You can get an idea of the research involved with this library by looking at the list of publications.
First of all, in the presence of message lost, you face the Two Generals' Problem, which says that it's impossible to achieve agreement on a message if arbitrary number of messages can be lost. In the presence of message lost, if you send an acknowledgment for guaranteeing message delivery, the acknowledgement itself may get lost and thus you need to acknowledge the acknowledgement. But then this will continue forever. Thus, Two Generals' Problem is not solvable. You can read in detail here.
Next, in order to achieve fault tolerance, you have to consider Byzantine Faults which are based on Byzantine Generals' Problem (why distributed systems people always think of army and generals is beyond me). Byzantine Faults occur when a faulty node says different things to different nodes - it may say that I have received the message successfully to one node and report the opposite to some other node, causing confusion and inconsistency in the system. Unlike the Two Generals' problem, it's solvable but with some upper bounds on the number of faulty nodes and with lots of communication overhead.
So, we ignore fault tolerance for now. Consider, ordering of messages instead. In a serious chat application the ordering can matter a lot. If different members in a conversation get messages in different order, it can cause confusion. TCP/IP provides ordering within packets of a single message (where packets are formed at lower layers of the network protocol) that is sent via a single TCP/IP socket. But what about different sockets (different members in the conversation) or different messages sent on the same socket? There is nothing in TCP/IP which guarantees that when you send "Hello"; close the socket; open it again and then send "Goodbye", they will be received in the same order. So, what's the solution? Number the messages yourself! And on the receiving end, hold messages if they are received earlier than their predecessors.
Then comes the issue of Group Membership. Does your rock-solid chat application allow a member to join in between a conversation? If yes, what happens when somebody has sent a message but it hasn't been received by all yet, and a new member joins the group. Should he be delivered the message or should it be held back? If you deliver the message to him as well, some of the members (who received the message before the new member joined) will think that he didn't get that message, while others will think the opposite. More confusion and inconsistency.
Some of you might think that considering all these issues is an overkill for a chat application. What about a distributed group of servers trying to synchronize their end-of-day activity?
As I said in the beginning, there is more to group communication than we casually think of. Ensemble is a library written in Objective Caml that handles most of the theoretical issues involved with Group Communication. It provides simple to use api for Java, C, C# and ML. It's highly modular and reconfigurable. Do check out the features it provides if you are interested in group communication. You can get an idea of the research involved with this library by looking at the list of publications.
No comments:
Post a Comment