Survival of the Fittest Jini Services, Part II
Use Transactions to Coordinate the Reliable Interaction of Jini Services
by Frank Sommers
First Published in JavaWorld, July 2001

<<  Page 2 of 8  >>

# The Problem of Four Generals

The story of the four generals, inspired by Leslie Lamport's "Byzantine Generals," illustrates the kind of guarantees distributed transactions must promise, and the way participants in it might communicate. In this example, the generals and their armies are metaphors for distributed services, and carrying out their battle plan is analogous to a distributed computation. This scenario is known as the coordinated attack problem.

The generals, each commanding an army, plot to capture a medieval fortress. Alone, no one army can force the besieged defenders to surrender. Together, however, they are more than a match for the city's defenses. Therefore, to win, the generals agree to fight only given the following battle conditions:

• They must all attack at the same time. If any one army calls off the attack, the others must immediately retreat.
• None of the armies may violate its own internal rules during the battle.
• The attack must be a surprise. All preparations must be kept secret and made in isolation from all but the generals' most trusted confidants.
• Victory must be permanent; for instance, the armies must be ready to occupy the city after the battle.

The four conditions for the generals' battle plan are the ACID guarantees:

• A stands for atomicity: Either all the armies attack, or none of them do. One or two armies attacking would cause the battle to be lost, and is not permissible.
• C means consistency: The armies must maintain their internal rules for order (consistency).
• I stands for isolation: All the preparations for the attack must be hidden from those not involved in its planning. If the attack is called off, no one outside the generals' close circle should sense that any activity has taken place.
• Finally, D implies durability: The results of the battle must survive the fight itself.

Next, the generals need a way to coordinate their activities. They settle on the following communication protocol:

• Prior to the battle, each army makes the necessary preparations. When each is ready, its commanding general lets the others know that he is prepared to move forward.
• Once each general is sure that all the others are prepared, he sends another message to the effect that his troops are now committed to battle (in effect, are marching against the fortress).

This protocol consists of two phases: The first indicates preparedness; the second, a fully committed state. It is often called the two-phase commit protocol -- or 2PC protocol, for short. Jini services participating in a distributed computation must use a similar mechanism to coordinate a transaction's completion, or commitment.

The only remaining concern for the generals is how to exchange messages. To indicate preparedness, each general must send a message to the others. Between the 4 generals, 12 messages are exchanged for the protocol's first phase. For N generals, N * (N-1) messages must be sent for each stage. This is bad news: If additional armies were involved in the attack, many more messages would be needed. For 10 generals, this arrangement would require an unmanageable 90 messages. Should any message get lost, the battle could not begin, since the generals could not be sure that the conditions were right for attack.

Instead of sending messengers directly to each other, the generals could decide to set up a central command post. Each general would send a messenger only to this command post to obtain the status of the other armies. With this arrangement, only two messages from each army are passed for each protocol stage: one delivering a general's message, and the other coming from the command post with an order to either proceed with or abort the plan. With this in place, only 8 messages are needed to indicate battle preparedness by our 4 generals. If 10 generals must coordinate their movements, then introducing the central post reduces the required messages from 90 to only 20. This command post is called the transaction manager, or coordinator, for the 2PC protocol.

 Figure 1. Communication messages for the two-phase commit protocol

<<  Page 2 of 8  >>