Information Sharing in Distributed Virtual Environments

This work provides details of mechanisms for sharing information among virtual environments in which the world model is replicated. Replicating the world model over multiple processes can lead to problems with consistency and lag. These problems can be alleviated by using the appropriate method of information sharing. We present a classification of types of sharing, a description of the types of consistency they provide, and explain and give examples of when each is useful. Using the classifications and algorithms of information sharing presented here, a distributed virtual environment builder can match an information sharing mechanism with their consistency and performance needs.

Virtual environments (VEs) give users the illusion that they are in a computer generated world. Distributed virtual environments (DVEs) allow VEs to run on multiple processes. For DVEs to operate, information must be shared among processes. Information can be shared in different ways – depending on the way in which and the extent to which the information must be coupled among processes.

Sometimes it is applicable to keep information closely coupled among processes. Consider, for example, two doctors working together in a distributed operating room simulation. One doctor will oversee and help with the diagnoses. The other will operate. They will be working together on a single patient. The two doctors will need timely communication and diagnosis information so that the overseeing doctor (the one remote from the patient) can accurately asses the patient’s condition during the operation. This will allow them to engage in useful discussion about the conditions and treatments of the subject. What is meant here by timely is a best-effort to process the communication as quickly as possible, regardless of the strain it puts on the system.

At other times, information can be shared in a less strict manner. Consider again the operating theater mentioned above. Assume that there are virtual spectators lining the outer perimeter of the room. The virtual spectators – distributed users immersed in the same virtual environment – are able to move around the perimeter, but are not allowed to speak or interact in any way. It is interesting for the virtual spectators to know where the others are so that they might spot a group huddled together and go to see the attractive view. However, it is not necessary that they receive detailed information of each other’s movements. Coarse, approximate, or sparse details of each other’s movements are sufficient. The information about positions of the spectators can be shared in a less strict manner than the information shared among the doctors.

Close coupling, in general, is more expensive. Therefore, when loose coupling is sufficient, it should be used in order to free CPU cycles and relive network congestion. Computational time and network bandwidth are consumed by each message sent and received by each process. Loose coupling allows less frequent messaging and therefore reduces the strain on these two resources.

Coupling can be subcategorized based on its ordering rules and level of enforcement. Two of the most commonly useful ordering categories are atomic ordering and causal ordering (described in more detail below). This work provides definitions of seven different sharing types based on the ordering and level of enforcement, descriptions of each, and examples of when each sharing type is useful.

BrickNet [BrickNet] by Singh et al. at the National University of Singapore provides support for CVEs. Both BrickNet and this work use a single interpreted language to provide support for sharing objects in and building of CVEs (BrickNet uses StarShip; this work -- Java).

One of the primary differences between the two is that BrickNet does not have the different types of sharing offered in this work. BrickNet provides true atomic sharing, but not causal and it does not support effective sharing. These additional types of sharing could be supported at the application level in BrickNet.

COTERIE [COTERIE] by MacIntyre and Feiner is a framework on which to build CVEs. It allows serial sharing at the object level. That is, all sharing done among processes is atomic, and entire objects are shared (not parts of objects). All processes see all per-object shared information pass through the same series of events. It would be possible to implement all of the types of sharing described in this paper at the application level in the COTERIE system, but they are not provided out of the box.

As is described later in the Testbed Description, the sharing in this work is done on the sub-object level. This work's sharing granularity can be emulated by COTERIE by grouping objects together. Each grouped object would correspond to a shared element in this work. With this, the application could share parts of an object.

GROVE [GROVE] by Ellis et al. at MCC, Austin, is not a VE system per se, but it is important because it deals with some of the same issues as this work. GROVE is real-time GroupWare for group document editing. Both deal with information sharing in ad hoc, distributed, real-time, interactive environments. Due to the nature of distributed document editing, GROVE only needs to support atomic ordering of messages. It does not need to support multiple ordering types. GROVE, like this work, supports effective ordering. That is, in both GROVE and this work, action is taken as messages arrive at a process, regardless of arrival order. As out-of-order messages arrive, action is taken to transform the current state into the would-be state -- the state consistent with the in-order arrival of the messages.

Hadzilacos and Toueg [HT] provide some useful insight from the world of parallel computing. They provide us with reliable broadcasts, causal sharing, and atomic sharing (defined below). [HT] does not, however, give us the concept of effective sharing. Effective sharing can add quicker response time to information-altering messages by allowing out-of-order actions to be taken as messages arrive. The post-arrival transformations reconcile the state of the information once a set of messages has arrived.

MASSIVE [MASSIVE] by Greenhalgh and Benford at Nottingham, tries to tackle the problem of producing collaboration in virtual environments (VEs). It is an application that has a strong emphasis on spatial mediation and multiple concurrent meetings. MASSIVE could further reduce the load on its network and CPUs by choosing the appropriate type of sharing for particular information.

NPSNET [NPSNET] by Macedonia, Zyda, Brutzman, and Barham at the Naval Postgraduate School proposes an architecture for supporting very large scale distributed simulations. The architecture uses spatial, temporal, and functional relationships to partition the dissemination of information in the DVE. It uses the DIS protocol, and therefore uses unreliable (UDP) messaging. NPSNET could increase reliability and retain its real-time performance by using the effective sharing presented here (the effective sharing types are described below).

SPLINE [SPLINE] by Richard C. Waters & David B. Anderson et al. at Mitsubishi Electronic Research Lab tackles the problem of supporting interoperable collaboration in VEs. It is considered "middleware" because it separates the network and operating system considerations from the application design. It provides fully replicated worlds. This work provides an alternative to complete replication. It allows an application designer to choose the type of sharing appropriate for individual pieces of information. By relaxing the restrictions on sharing information among processes, one can reduce network traffic and allow quicker response to requests.

Below is a taxonomy of sharing types. The types of information sharing considered here refer to messages that, when acted upon, change the state of an object at the acting process. The experiments were done with virtual spheres in which only the position was changeable (see screendumps and description in Testbed Description).

The following terms will be used to describe the different information sharing types. Except for ECO and ETO all of the terms are from [HT].

Validity: If a correct process broadcasts a message m, then it eventually delivers m.

Agreement: If a correct delivers a message m, then eventually all correct processes will deliver m.

Integrity: For any message m, every correct process delivers m at most once, and only if m was previously broadcast by sender (m).

Reliable Broadcast(RB): Validity + Agreement +Integrity

Causal Order(CO): If the broadcast of a message m causally precedes the broadcast of a message m’, then no correct process delivers m’ unless it has previously delivered m.

Total Order(TO): If correct processes p and q both deliver messages m and m’, then p delivers m before m’ iff q delivers m before m’.

Effective Causal Order(ECO): Assume all processes start in the same state. If a correct process p and q both deliver a set of messages M (in any order), each process will, after acting on all of those events (events received via messages in any order and no events "beyond" those events are received), be in a state as if they traveled through the events in the "accepted causal order". Where, "accepted causal order" is the order the events would arrive in if the events were fully causal. Fully causal = Casual Broadcast = Reliable Broadcast and Causal Order.

Effective Total Order (ECO): Assume that all processes start in the same state. If a correct process p and q bother deliver a set of messages M (in any order), each process will, after acting on all of those events (events received via messages in any order and no events "beyond" those events are received), be in a state as if they had acted on the events in the acceptable total order. Where acceptable total order is the order that the events would have arrived in is the events were fully causal. Fully causal = Causal Broadcast = Reliable Broadcast and Causal Order.

There are a number of rules relating to the ordering types that we have observed. First, if a series of events obeys Total Order, then it also obeys Effective Total Order:

(TO^RB) -> (ETO^RB) -> (RB).

The same holds true for Causal Order and Effective Causal Order:

(CO^RB) -> (ECO^RB) -> (RB).

Second, in a combination of Causal Ordering and Total Ordering, if one of the two is effectively ordered and the other is not, it is equivalent to Total Ordering with Causal Ordering:

(CO^ETO) = (ECO^TO) = (CO^TO).

From the Reliable Broadcasts and the different ordering types considered, we have identified seven different sharing types. These seven are defined and described below.
 

Name	Properties	Description
Reliable Sharing	RB	Nothing is guaranteed except that all messages are delivered at all sites.
Causal Sharing	CO^ RB	Messages are delivered in causally equivalent orders on all processes.
Atomic Sharing	TO^ RB	Messages are delivered in the same order on all processes.
Atomic Causal Sharing	TO^ CO^ RB	Messages are delivered in fully ordered, causally sound order on all processes.
Effective Causal Sharing	ECO^RB	The messages may not be delivered in the same order on all processes, but after all messages arrive, all of the processes will be in causally equivalent states.
Effective Atomic Sharing	ETO^RB	The messages may not be delivered in the same order on all processes, but after all messages arrive, all of the processes will be in the same state (as if they had been totally ordered).
Effective Atomic Causal Sharing	ETO^ECO^RB	The messages may not be delivered in the same order on all processes, but after all messages arrive, all of the processes will be in the same state (as if they had been causally and totally ordered).

 

Reliable sharing means, as the name implies, that all messages arrive and are acted upon on all appropriate processes. The appropriate processes are those correct [HT] processes that contain a copy of the object to which the message refers.

All of the types of sharing presented in this paper assume reliable broadcasts. Reliable sharing also assumes reliable broadcasts and uses a first-arrived, first-acted-upon scheme for ordering – it acts on messages as they arrive. Therefore, it makes no guarantees with respect to the ordering of the messages.

This type of sharing is used when it does not make a difference in what order the messages are processed. This will often be useful when information will not change often or when information is guided by social protocol. An example which is a combination of the two of these is in a replicated virtual environment – a simulation of a pool hall – people are rarely going to move the racking triangle that is provided at each table and when they do, social protocol will dictate which user should – in eight-ball, the loser of the previous game will grab the triangle. Since there is little contention on the movement of the rack, the position can be communicated using reliable sharing.

An advantage of this type of sharing is that there is less overhead (since there is no post-arrival ordering) and no acknowledgment is needed from the server (to order the messages). So, response and action are immediate on the message-originator’s side.

In general, this type of sharing is useful when:

• All messages must arrive at all processes but no guarantee of arrival order is needed.

Causal sharing refers to sharing that is both reliable and keeps causal order (above). In other words, causal sharing provides the DVE with the guarantee that all messages will arrive at all appropriate processes, and once there, will be ordered with respect to their causal relationship.

This type of sharing is used when messages should be ordered in terms of their cause-effect relationship and can allow multiple effects for a single cause. One situation in which this will be useful when the cause-effect relationship is augmented by social protocol. For example, using the pool hall simulation again as an example, the cause-effect relationship of shooting at the pool balls is causal in two ways and guided by social protocol in one. First of all, the collisions of the pool balls is guided by a cause-effect relationship. The cue ball hits one that hits another and so on. The act of shooting at the cue balls is guided by both a cause-effect relationship and by a social protocol. After one player has shot, the next will shoot, so there should not be any concern about having one event (player one shooting) cause multiple events (only one player is scheduled to shoot next). The desired atomic-ization of the potential events is handled by social protocol.

The advantage to this type of sharing is that messages are guaranteed to retain their cause-effect ordering on all appropriate processes. Causal ordering can be used to guarantee that all processes see things happen in equivalent event orders.

In general, this type of sharing is useful when:

• Events need to be kept in equivalent orders on all appropriate processes.
• Concurrent events are allowed.
• In the case that there is a concurrent event, the need not be a guarantee which event arrives at an appropriate process.

Atomic sharing refers to sharing that is both reliable and keeps all events in total order on each appropriate process. In other words, atomic sharing guarantees that all messages will arrive at all appropriate processes in there designated serial order. The designated serial order is often assigned by a central server based on the order the messages arrived at the server.

This type of sharing is used when one wants to guarantee that all messages arrive at all appropriate processes in the same order, but do not necessarily care about what order the messages arrive. This will often be useful when there is no cause-effect relationship among the potential actions, but there is a need for all messages to be delivered at all processes in the same order. For example, while in the pool hall, we play a carnival game: shooting a water gun to blow up a balloon – the first to pop their balloon wins. While there is a causal relationship between shooting the water and expanding the balloon, there is no causal relationship among the shooters in the game. To find a winner, though, there must be some inter-balloon ordering. The popping of the balloons must be atomically ordered so that a winner can be determined.

The advantage of this type of sharing is that it provides a consistent ordering among all of the appropriate processes. Neither reliable nor causal sharing will guarantee that ordering on all appropriate processes is the same.

The primary disadvantage of this type of sharing is that atomic ordering is expensive. It requires that all events be centralized. In most implementations, this means that no process can act on an event until after it has passed through a central server. In other words, a process must request permission to act on an object instead of acting on the object and then informing the central server.

In general, this type of sharing is useful when:

• Events need to be processed in the same order on all appropriate processes, but no guarantee on that shared arrival order is needed.

Atomic causal sharing, the strictest sharing discussed in this paper, refers to sharing that is reliable, keeps all events in total order, and keeps all events in causal order. In other words, atomic causal sharing guarantees that all messages will arrive in the same order on all processes and that the order will be dictated by the cause-effect relationship of the events.

This type of sharing is used when one wants to guarantee that all messages arrive at all appropriate processes in the same order and guarantee that all messages retain their causal order upon arrival. This will often be used when there is a cause-effect relationship among potential interactions and there is a need for all messages to be delivered to all appropriate processes in the same order. For example, consider the pool hall simulation again. Suppose that you are in the final game of an important tournament and, as a result, you want a guarantee that you and your opponent witness all of the same events on the table. Suppose also, that in order to alleviate some of the burden of the complicated physical calculation, the balls are distributed three to a process (on separate computers). To correctly order movement events, the messages from these different processes will have to be both causally ordered – so that the interaction among the balls will appear correctly on all appropriate processes – and atomically ordered – since in tight, multi-ball interactions, it is important to ensure that the users see the collisions in the same correct order.

The advantages of this type of sharing are a culmination of those for both causal and atomic orderings. It provides the system with a guarantee both that the events will occur in the same order on all processes and that the order in which they arrive will be governed by their causal relationship.

The disadvantage of this type of sharing is its overhead. The atomic ordering necessitates centralization of all request and enforcement of request-before-execution for the actions. The causal ordering adds additional overhead by enforcing a causally ordered delivery of the messages.

In general, this type of sharing is useful when:

• Events need to be processed in the same order on all appropriate processes, and the messages need to be causally ordered.

One of the biggest problems with causal and total ordering is that they add lag to messages in a system where there is already significant network lag. To get around this problem, we have developed a set of effective sharing types where the lag of post-arrival ordering is avoided. Messages are acted upon as they arrive and the effects are later transformed to the correct state, much like [GROVE].

Consider, for example, the act of painting a ball with the color of the ball being causally shared. The user on one process paints the ball red(1), the next green (2), and the third paints it blue(3). The ball will be blue. Now consider the situation in which, on a forth processes, the messages to paint the ball red(1) arrives and then the message to paint the ball blue(3) but the message to paint the ball green(2) does not arrive until after considerable lag. After receiving the message to paint the ball red(1), the process will paint the ball red. After receiving the message to paint the ball blue(3), the process will wait. It is not until after the process received the message to paint the ball green(2) that it can paint the ball green and then its final color – blue.

Using effective sharing, the forth process would have painted the ball blue upon arrival of the message (3), and ignored the message that came later (2). This can reduce lag in the system by allowing the system to act on messages that are further along in the message sequence.

Not all events, though, are appropriate for effective ordering. The application designer must look ahead to the actions that will be communicated for the object and, from this, decide what type of sharing can be applied. Consider again the example of painting the ball. If the correct order of the messages was, red (1), green (2), and translucent blue (3), the correct final color would be blue-green (a result of the translucent blue being painted on top of the green). Assume again that on the fourth process the messages arrived in the order red(1), translucent blue(3), and, after considerable lag, green(2). The messages can not be applied in the order they arrive, since that would change the final outcome (the final color of the ball would be purple (blue-red) – not the correct final color, blue-green).

The application designer must be able to distinguish what types of messages can be effectively ordered. In the experiments, we have used two types of messages for effective sharing: commuting (A@B=B@A) and superseding actions (A@B=B). There is also the trivial case of ignoring (A@B=A), which we did no tests with, since it can be simulated by not allowing any action to be taken on the state of an object.

To effectively order commuting actions (TO or CO), we act on the messages as they arrive. The final result is the same as if they had arrived (and been acted upon) in order. Figure 1 has a visual example of a commuting operation: the addition of vectors. The order in which three vectors are added together does not effect the final position. All commuting operations have this property. They can be applied in any order and still have the same outcome.

 

Another approach to effective ordering can also be taken. If there is an undo for the operation, then the process can act on messages as they arrive, even if they are out of order. Later, when a message that precedes one that as already been acted on arrives, all actions are undone back to the point where the newly arrived message fits. Then all of the messages are acted on again in the revised order.

We wanted to avoid the visually disrupting effects of undo and redoing events. Therefore, we did not take this approach.

Effective causal sharing refers to sharing that will, after a set of messages has arrived at all appropriate processes, leave all appropriate processes in a state as if the messages had arrived in causal order.

This type of sharing is used when the effects of causal ordering are desired, but the overhead and added lag of causally ordering the messages is not desired. Consider again the example in Causal Sharing where players taking turns shooting at the cue ball. This type of causal sharing acts on messages as they arrived and after all messages arrived, each process would be in a state as if the messages had been processed in true causal order. From a user in the DVE’s point of view, the difference is that the reaction time to events will, in general, be quicker (since messages are acted on as they arrive), and different processes might pass through a different series of states.

Since messages are acted upon as they arrive, when this type of sharing is used with commuting messages, each process must keep track of which messages it has acted upon, so that it will not act on two causally equivalent events. The lack of post-arrival ordering reduces lag at the processes, but the computational overhead is almost as much as the overhead of causally ordering messages as they arrive. (Computation = O(n) for both, effective causal sharing also adds O(1) memory usage).

When using a superseding operation, effective causal sharing allows processes to act on messages beyond the next causal messages (this assumes that the exact causal order can be determined with something like Lamport Clocks). The process can always ignore all messages that are causal predecessors to the last one acted upon. This effectively jumps the state of the process past causal events that arrive after their predecessors.

In general, this type of sharing is useful when:

• Causal ordering is needed for commuting actions, but there is no need for processes to follow the correct details of causality during congested message arrival. After a complete set of messages has arrived, the process will be in the correct state.
• Causal ordering is needed for superceding actions, but processes need not pass through all of the states leading to the final causal state.

Effective atomic sharing will leave each process in a state as if the messages had been executed in total order (atomic order), regardless of the order of arrival and delivery of the messages.

This type of sharing is useful when one desires the effects of atomic sharing but not the overhead and added lag of atomically ordering the messages. Consider for example, the water gun carnival game in Atomic Sharing – shooting a water gun to blow up a balloon. The expansion and therefore the popping of the balloons must be atomically ordered so that a winner can be determined. If there were a large number of balloons, each controlled by a different process, atomic ordering, and therefor centralization of the expansion events, would induce considerable lag. Relaxing the ordering to effective total ordering would allow quicker reaction to local events (since local messages would no longer be serialized before being acted upon), and still allow the processes to determine which balloon popped first (since all appropriate processes will eventually receive all messages and therefore receive a message which corresponds to the winning balloon). This could cause confusion among the players since it is possible that a player will see his balloon pop before all of the others, yet he will determine that he is not the winner.

With effective atomic sharing of commuting operations, processes can act on messages as they arrive. In the case of the balloon example, this means that different processes will effect expansions on the balloons in different orders, but will in the end, all have the same state for all of the balloons. In general, this type of sharing with a commuting action will allow the different processes to pass through different series of events, but each will end up in the same final state.

When using a superceding operation, effective atomic sharing allows processes to act on messages out of atomic order and ignore any messages that should precede it but arrive later (as was the case for Effective Causal Sharing). In the case of the balloon example, this means that different processes might see the set of balloons is collectively different states during the game, but will at the end, all have the same collective state for the set of the balloons. Using this type of sharing with a superceding action will allow the different processes to pass through different series of events, but each will end up in the same final state.

In general, this type of sharing is useful when:

• Atomic ordering is needed for commuting actions, and processes are allowed to pass through different event sequences undrstanding that all processes will be in the correct state after a complete set of messages have arrived.
• Atomic ordering is needed for superceding actions, but processes can skip states leading to the final state.

Effective atomic causal sharing refers to sharing that will, after a set of messages has arrived at all appropriate processes, leave the processes in a state as if the messages had arrived in total order and causal order (atomic causal sharing).

This type of sharing is used when the effects of atomic causal sharing are desired, but the overhead and added lag of atomically and causally ordering the messages is not desired. Consider, for example, the pool tournament in Atomic Causal Sharing. The competitors will want to retain their atomic causal ordering, but a spectator might want a less strict ordering of events on the table in order to reduce overhead of watching the game. The results of the game will be the same, but the spectator, due to the act-on-arrival nature of effective atomic casual sharing, might see the different details of individual collisions than the participants (who are enforcing true atomic causal sharing).

With effective atomic causal sharing of commuting operations, the processes can act on messages as they arrive. Like effective causal sharing and effective atomic sharing, this type of sharing with a commuting action will allow the different processes to pass through different series of events, but each will end up in the same final state.

When using a superceding operation, effective atomic causal sharing allows processes to act on messages out of atomic order (as was the case for Effective Causal Sharing and Effective Atomic Sharing). Like these other two types of effective sharing, this allows different processes to pass through different series of events, but ensures that each will end up in the same final state.

In general, this type of sharing is useful when:

• Atomic causal ordering is needed for commuting actions, but there is no need for processes to follow the correct details of atomic and causal ordering during congested message arrival. After a complete set of messages has arrived, all appropriate processed will be in the correct state.
• Atomic causal ordering is needed for superceding actions, but processes need not pass through all of the states leading to the final state.

We arrived at the taxonomy presented in this paper in part as a result of experimentation with a proof-of-concept system (hereafter referred to as "the system" or "this system"). It allowed us to experiment with various information-sharing types in a virtual environment with a partially distributed or partially replicated world model.

The system and its capabilities are described more fully in [MM]. In short it is a set of Java classes which provide "a basis with which one can build interoperable objects and worlds for collaborative virtual environments. The concentration of the work is providing an architecture which allows: 1) seamless interoperability of all worlds built or encapsulated using this method, 2) objects to move among worlds without losing functionality, 3) worlds -- which are simply objects in this architecture -- to be encapsulated in and move among other worlds, 4) any combination of object-object, object-world, and world-world learning." [MM] It also provides various types of sharing: reliable, causal, atomic, effective atomic, effective causal, and it can be easily extended to provide causal atomic and effective causal atomic.

The world we built on top of the Java classes was a multi-user (multi-process) walk/fly through of the area around Sitterson Hall on the UNC-CH campus. The sharing experiments were accomplished by manipulation of virtual spheres placed in the malls and courtyards of virtual campus. Only the positions of the spheres were modifiable and it (the position) was the only information shared among the processes in the VE.

The types of sharing studied in the system included those with both true ordering – each process follows the rules of the ordering upon the arrival of each message – and effective ordering – each process makes a best attempt at following the ordering upon the arrival of each message, ending in a state consistent with the true ordering. Any operation in a distributed VE can be truly ordered. It is possible to effectively order any operation as long as the operation can be undone and redone later. We avoided the visually disrupting side effects of undoing operations by using a transformation approach to effective ordering where a best guess of the current state of the process was made based on the messages that had arrived. Not all operations can be effectively ordered in this way, though. Therefore, we only allowed effective ordering of superceding and commuting operations. In our case these operations were manipulations of the position of the sphere. It is possible that there are other general categories of operations that could be used for effective causal and serial ordering, but we have not as yet determined them (see future work).

This works has two primary contributions. First, it describes and classifies event sharing methods for distributed VEs that allow combinations of reliable, causal, and atomic ordering. It also provides a description of when it is possible to avoid the ordering overhead associated with these types of orderings. Second, it provides a description and example of each of the seven event-sharing types. It also gives a description of an implementation of this type of overhead-avoiding event sharing.

There is considerable work yet to be done in the area of information sharing in DVEs. We plan to extend this work by determining a general set of rules for operations that can be effectively ordered. We are going to provide a set of rules for adding an ordering type to allow developers to go beyond simple causal and atomic ordering. We are going to develop an interview that will identify the strictest and least strict sharing needed by an event set. We are going to extend the proof of concept system so that the event sharing types can be changed dynamically. Once that is done, we will conduct experiments with the system using parameters such as user input and network performance, to intelligently modify the sharing type being used for various events.

I would like to thank Dr. Stotts and Dr. Dewan and the other faculty, staff and students at the University of North Carolina. I would also like to thank DARPA, who funded this project under grant number: N66001-96-C-8507.