Instruct: Given a question, retrieve relevant documents that can help answer the question.
Query: When was virtual synchrony invented?
The main author is Ken Birman, a Professor of Computer Science at Cornell University, and it is the fourth in a series of Cornell-developed software libraries for reliable multicast. The first was the Isis Toolkit, developed in 1985 and ultimately used in the New York Stock Exchange, the French Air Traffic Control System, the US Navy AEGIS and other settings.[1]
The flexibility associated with these limited forms of event reordering and optimistic early delivery permit virtual synchrony platforms to achieve extremely high data rates while still preserving very strong fault-tolerance and consistency guarantees.
The term "virtual synchrony" refers to the fact that applications see the shared data evolve in what seems to be a synchronous manner. This form of synchronization is "virtual" because the actual situation is more complex than seems to be the case from a programmer's perspective. Like a compiler that sometimes reorders the execution of instructions for higher performance, or an operating system that sometimes stores random access memory on disk, virtual synchrony sometimes reorders events in ways that improve performance, and yet won't be noticeable to applications.
Other such systems include the "Horus system", the Transis system, the Totem system, an IBM system called Phoenix, a distributed security key management system called Rampart, the "Ensemble system", the Quicksilver system, "The OpenAIS project", its derivative the Corosync Cluster Engine and a number of products (including the IBM and Microsoft ones mentioned earlier). At the time of this writing, virtual synchrony toolkits that programmers can use to implement new virtually synchronous applications include the Spread Toolkit, JGroups, the C-Ensemble system, Appia, Quicksilver, and the Corosync Cluster Engine.
But the other sense in which virtual synchrony is a weaker model relates to exactly what happens when some process crashes. Suppose that process p sends a multicast to a group G, and then p and some member of the group, say q, both crash. No process that remains operational has a copy of the multicast. What should the platform do?
Distributed Systems: Principles and Paradigms (2nd Edition). Andrew S. Tanenbaum, Maarten van Steen (2002). "Textbook, covers a broad spectrum of distributed computing concepts, including virtual synchrony."
Virtual synchrony is useful for more than just replicating data, although replication is probably the most common use. Other mechanisms that can be constructed "over" a virtual synchrony platform include:
Among the three models, virtual synchrony achieves the highest levels of performance, but this comes at a cost: to gain higher performance the programmer must relax ordering and employ optimistic early delivery features that expose the service to some risk of inconsistency. Virtual synchrony implementations employ a primitive called "flush" to force the service back into a consistent state before interactions with external clients or storage systems. The effect is to offer a very strong model, but only if the various features are employed correctly.
The trend towards cloud computing has increased interest in consistent state replication. Cloud computing systems are large virtualized data centers, operated by internet search or commerce firms such as IBM, Microsoft, Google and Amazon. Inside a cloud computing platform one finds services such as lock management systems (Google's is called Chubby, and Yahoo! uses one called Zookeeper), and these are implemented using virtual synchrony or closely related models. Other services that might be implemented using virtual synchrony include the cluster management tools that relaunch failed applications when nodes in a cluster crash, event notification tools that inform applications when significant events occur, and logging tools that help an application save its state for replay during recovery.
Each process group has a name, visible within the network. A single application program can become a member of many groups at the same time. In effect, a process group becomes an abstraction for sharing data, coordinating actions, and monitoring other processes. In the most widely used software libraries implementing the model, virtual synchrony is typically employed within individual objects, which are then incorporated into object oriented code in languages like Java or C#. The objects themselves act as a unit of replication with virtual synchrony properties.
The Vsync software library is a BSD-licensed open source library written in C# for the .NET platform, providing a wide variety of primitives for fault-tolerant distributed computing, including: state machine replication, virtual synchrony process groups, atomic broadcast with several levels of ordering and durability, a distributed lock manager, persistent replicated data, a distributed key-value store (also called a Distributed Hash Table or DHT), and scalable aggregation. The system implements the virtual synchrony execution model, and includes an implementation of Leslie Lamport's Paxos Protocol.
Ken Birman developed the virtual synchrony model in a series of papers published between 1985 and 1987. The primary reference to this work is "Exploiting Virtual Synchrony in Distributed Systems", which describes the Isis Toolkit, a system that was used to build the New York and Swiss Stock Exchanges, French Air Traffic Control System, US Navy AEGIS Warship, and other applications.
In the 1985–1987, the virtual synchrony model was proposed and emerged as a widely adopted standard (it was used in the Isis Toolkit, Horus, Transis, Ensemble, Totem, Spread, C-Ensemble, Phoenix and Quicksilver systems, and is the basis for the CORBA fault-tolerant computing standard). Virtual synchrony permits a multi-primary approach in which a group of processes cooperates to parallelize some aspects of request processing. The scheme can only be used for some forms of in-memory data, but can provide linear speedups in the size of the group.
To give another example, by delivering messages optimistically, virtual synchrony systems can outperform the Paxos that is normally required for implementation of state machine replication: Paxos normally requires a 2-phase protocol, whereas optimistic virtual synchrony protocols can deliver messages immediately upon their arrival. However, this could result in a violation of the safety property of the state machine replication model. To prevent such problems, the programmer who uses this feature is required to invoke a primitive called "flush", which delays the caller until any optimistically delivered messages have reached all of the group members. Provided that the programmer understands this behavior and is careful to call flush before interacting with external clients or persistent storage, higher performance can be achieved without loss of safety.
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.
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).
Notice that the guarantee just described embodies what may seem to be a contradiction. We know that timeout cannot be used to detect failures accurately. Yet virtual synchrony lets the user treat failure notifications (view changes) as trustworthy, infallible events. The key insight is that virtual synchrony is implemented by a software system that creates an abstraction within which the user's code is executed. Thus, failure detection by the platform (using timeouts) triggers an internal agreement protocol (within the platform). Only when this protocol terminates is a fault event delivered to the application. The application is spared from needing to implement the agreement mechanism, and sees a simple and seemingly accurate fault notification event.
Reliable Distributed Systems: Technologies, Web Services and Applications. K.P. Birman. Springer Verlag (1997). "Textbook, covers a broad spectrum of distributed computing concepts, including virtual synchrony."
Virtual synchrony replication is used mostly when applications are replicating information that evolves extremely rapidly. As discussed further below, the kinds of applications that would need this model include multiuser role-playing games, air traffic control systems, stock exchanges, and telecommunication switches. Of course, there are other ways to solve the same problems. For example, most of today's online multiuser role-playing games give users a sense that they are sharing replicated data, but in fact the data lives in a server on a data center, and any information passes through the data centers. Those games probably wouldn't use models like virtual synchrony, at present. However, as they push towards higher and higher data rates, taking the server out of the critical performance path becomes important, and with this step, models such as virtual synchrony are potentially valuable.
Virtual synchrony is distinguished from classical state machine replication because the model includes features whereby a programmer can request early (optimistic) delivery of messages, or relaxed forms of ordering. When used appropriately, these features can enable substantial speedup. However, the programmer needs to be sure that the relaxation of guarantees will not compromise correctness.
Using the virtual synchrony model, it is relatively easy to maintain fault-tolerant replicated data in a consistent state. One can then build higher level abstractions over the basic replication mechanisms. For example, many virtual synchrony libraries also support tools for building distributed key-value stores, replicating external files or databases, locking or otherwise coordinating the actions of group members, etc.
Virtual synchrony was first supported by the Cornell University and was called the "Isis Toolkit". Cornell's most current version, Vsync was released in 2013 under the name Isis2 (the name was changed from Isis2 to Vsync in 2015 in the wake of a terrorist attack in Paris by an extremist organization called ISIS), with periodic updates and revisions since that time. The most current stable release is V2.2.2020; it was released on November 14, 2015; the V2.2.2048 release is currently available in Beta form. Vsync aims at the massive data centers that support cloud computing.
Virtual synchrony is usually presented to programmers through a simple distributed programming library that supports at least three basic interfaces. First, a process (an executing program) can "join" a "process group". Each group has a name (a bit like a file name, although these names are interpreted within a network, not relative to a disk), and each has a list of members. The join primitive returns some form of handle on the group. The process can then register a "handler" for incoming events, and can send "multicasts" to the group.
Distributed computer systems often need a way to replicate data for sharing between programs running on multiple machines, connected by a network. Virtual synchrony is one of three major technologies for solving this problem. The key idea is to create a form of distributed state machine associated with the replicated data item. Called a "process group", these state machines share copies of the data, and updates are delivered as "events" that occur in the same order at all the copies. If a process fails or crashes, this is reported to the other processes in the group; if a process joins, this is similarly reported, and a state transfer is used to initialize the joining member. An application with lots of data items to replicate might do so by using a single group for the whole set, or it could create different groups for different items, with the former approach used when the items are replicated at the identical places, and the latter being used when the replication patterns differ.
Virtual synchrony is an interprocess message passing (sometimes called ordered, reliable multicast) technology. Virtual synchrony systems allow programs running in a network to organize themselves into "process groups", and to send messages to groups (as opposed to sending them to specific processes). Each message is delivered to all the group members, in the identical order, and this is true even when two messages are transmitted simultaneously by different senders. Application design and implementation is greatly simplified by this property: every group member sees the same events (group membership changes and incoming messages) in the same order.
Experience with virtual synchrony shows that for most applications, the weak but fast form of delivery is just fine. For rare cases where stronger guarantees are needed, the application programmer can request that a slower delivery be performed, paying an infrequent higher price, but only when necessary. The resulting performance will be much higher than if the slower, more conservative delivery property was used for every message.