The Artima Developer Community
Sponsored Link

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  >>

Advertisement

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:

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

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

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  >>


Sponsored Links



Google
  Web Artima.com   
Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us