Virtual Synchrony - A Time-Space Illustration of The Virtual Synchrony Concept

A Time-Space Illustration of The Virtual Synchrony Concept

• Figure 1 (True synchrony)

• Figure 2 (Relaxed timing)

• Figure 3 (Virtual synchrony)

The three executions shown above illustrate the type of event reordering used in virtual synchrony systems. Each shows a set of processes (named p, q, etc.) executing as time elapses, from left to right. They interact by exchanging messages, which are shown as arrows from process to process. Notice that the three figures are quite similar but differ in seemingly small ways: in the first figure, the message-passing arrows are vertical, as if the sending of a message was an instantaneous event. In the second figure, the sending of a message takes "time", and we see this because the arrows are now slanted forward. In the third figure, some of the message sending arrows cross one another.

We will start by looking closely at figure 1 (you may wish to enlarge it so that you can see the arrows clearly). Consider the sequence of events that occur as time elapses, from left to right.

At the start, p creates a process group and is its only member. Then q joins and with p's help, initializes itself. The heavy arrow denotes the creation of a checkpoint by p, which is copied to q, and then loaded by q. Perhaps this group lists air traffic control state for some sector over Paris. Now t, a non-member, asks the group some question. It sends a message, and the group members cooperate to respond (perhaps they each search half of an ATC database -- after all, each knows that the group has two members and each knows its own rank, so parallel computing becomes easy! Next we see some update messages -- multicasts -- exchanged by p and q. Process r joins the group, but q either crashes or fails. Notice that each event is seen in the identical order by all the members. This makes it easy to track the evolving group state. Some would call this a state machine execution.

What makes a virtually synchronous system virtual rather than real is that the synchronous event ordering is actually an illusion. If the timing in the system isn't perfectly synchronized, messages may be delivered with some delays (Figure 2). Now, the delays in question may not be significant to human perception. But how can the application know what order to process the events in? We can't use true clock time for this: even with GPS clocks, synchronization won't be better than a few milliseconds.

In a worst case scenario, events genuinely happen out of order (Figure 3). The point this figure is intended to make is that sometimes, a system can deliver events out of order -- and yet the application might not notice. We'll discuss cases in which this occurs momentarily. By deviating from the synchronous order, virtual synchrony systems gain speed and improve fault-tolerance (they are less likely to experience correlated crashes where some message causes all the members to crash simultaneously).

In virtual synchrony systems, the application programmer signals to the platform what form of ordering is really needed. For example, the programmer might indicate that multicast m updates different data than multicast n. Virtual synchrony software systems make it easy to do this sort of thing, although we won't delve into the details here. Basically, the programmer says "you can deliver messages m and n in any order you like, because my application won't notice". When permitted to do so, the communication system can now save time by not delaying messages under conditions where providing identical delivery order for n and m would have introduced extra cost and thereby slowed down the data rate.

When could we get away with this sort of thing? The answer usually depends on the application. But one good example arises if a group is maintaining data about some collection of objects that tend to be accessed independently. For example, perhaps the group represents the rooms in a multi-user role-playing game. Users are only in one room at a time, hence multicasts that update data in different rooms can be delivered in different orders. If a user sees one such multicast (e.g. that user happens to be in Sarah's Ice Cream shop when the a message is delivered that causes the telephone to ring), they won't see the other one (because it affected the state of some other room). Returning to our air traffic control example, different groups might represent different sectors of the sky, at which point the same kinds of options arise. A programmer designing such an application will often have simple ways to realize that this is the case, and can then signal this through an appropriate system-call.

Why bother? The key question relates to the speed of the application: a communication system gains performance as its ordering obligations are relaxed. Thus, virtual synchrony is motivated by a performance objective. The system seeks to be as fast as an unreliable UDP multicast and yet to have strong fault-tolerance and ordering guarantees, similar to those of Paxos.