This paper describes a system for dynamically reconfiguring the sharing of information among processes in a distributed virtual environment (DVE). In a DVE, processes must propagate changes made locally to other processes. Network latency in the transmission of messages relating to these changes can lead to problems with consistency and lag. No single sharing method -- rules for pre-delivery ordering and post-delivery transformation -- will be appropriate since network performance will vary over time. This work helps alleviate some of these problems by allowing dynamic configuration of the sharing rules and strength used for a given process based on network performance and user preference. The solution pits local response against the accuracy of the local view of global activity.

There are many exciting facets and difficult challenges related to the immerging technology known as virtual environments (VEs). Many of the challenges are driven by the desire to improve user experience. Ideally, the system should be able to display to the user everything that the user is able to or desires to perceive. This is a challenge for even the fastest machines with the most sophisticated peripherals.

In distributed virtual environments (DVEs) more challenges are presented. Of the most significant of these challenges is keeping distributed information - data relating to the world, user, and application - consistent in the face of varying network latency. Varying latency makes it impossible for a DVE designer to set up a single information-sharing mechanism and guarantee that it will provide an acceptable user experience.

Though it is not possible to overcome the problem of latency completely, since, in the extreme case, messages will not arrive at a given process before its application terminates, it is possible at least to partially overcome the challenge of adjusting to varying network latency. Many systems (e.g. [9]) use physical prediction to deal with unacceptable latency. Some systems use methods of reducing network traffic in order to avoid overburdening the network (e.g. [8], [9], [10]). Other systems use different policies for message delivery based on message type (e.g. [10]). This work provides a dynamic and general approach to using different policies based on network performance and user preference. We allow information-altering events to be ordered using various rules (Atomic and Causal Ordering, which are described below, have been implemented) and allow information to be shared using either True Ordering - apply rules as messages arrive - or Effective Ordering - reorder and transform events when messages arrive out of order.

This work also allows the application to switch between these sharing types based on network performance and user preference. Being able to switch dynamically among multiple types of sharing alleviates some of the problems with varying network performance by allowing better local response when network performance degrades and more accurate local response to global events if network performance improves.

Consider, for example, a DVE where two doctors are working together to treat a patient. One is in the operating room with the patient. The other is offsite in a VR chamber. The point of the collaboration is to allow an on-site doctor to utilize the expertise of an off-site specialist without forcing the specialist to travel to the site (thus increasing the probability that the specialist will be involved).

An operation is a very delicate situation. Therefore, we want all of the information to be shared instantly and identically between the two doctors in order to give them the illusion that they are in the operating theater together. Unfortunately, this may not be possible. Our best attempt at this instant identical information sharing is True Causal Atomic Sharing. If we were to enforce this, our strictest sharing type, all of the time, the performance of the application would suffer as the network performance worsened. This is because, with True Causal Atomic Ordering, messages from each process must be ordered globally before they are delivered to the processes, causing application lag in proportion to network latency. To put it simply, with this type of sharing, the communication's round trip time (most likely to a central server) would slow down the effects of local actions (such as movement) because of the act-after-response nature of True Atomic Sharing.

To alleviate some of the disconcerting variation in application performance, we allow the application to define sharing rules among which they should switch based on network latency and user preference.

So, in the DVE operating theater example, it would be beneficial if the information was shared strictly while network was performing well, and reduce the strength of the sharing if the network was performing poorly.

It is important to note that, in our system, information sharing is defined per object-attribute. Consider again the DVE operating theater example. One of the most important attributes in the shared operating theater would be the operating doctor's hands. His hands' position, orientation, and (grouping the shape of the hand into one attribute) contortion should each be shared in a very strict manner - striving to ensure that information about them is shared as accurately as possible. Other object-attributes in the scene, such as the position and orientation of the tray on which the instruments are placed, are not as important to the operation. This attribute could be shared in a less strict manner without any ill effect on either doctor's experience.

This work builds on the framework presented in [3] and uses the sharing taxonomy presented in [1].

There are a variety of methods by which a DVE can share information. This section classifies sharing based on rules implemented and sharing strengths obeyed. The two rules implemented in the system are Causal and Atomic Ordering. The two sharing strengths implemented are True and Effective Sharing

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. Most of the experiments were done with virtual spheres in which only the position was changeable (see screendump and description in Implementation).

One of the major contributions this work provides is defining a framework of sharing types with which the application designer can clearly specify the type of information sharing should be used given certain user preferences and system performance. The classification consists of the seven types of information sharing which are derived from the ability to use either Effective or True strength sharing for either, both, or neither of Causal and Atomic Sharing. There is a full discussion of this taxonomy in [1].

The following terms will be used to describe the different information sharing types. All terms are from [2] except those related to effective ordering and sharing. [2] uses the term Total Order where we use the term Atomic Order.

We are assuming that the system is fault-tolerant and that all messages that are sent to a process will eventually arrive there.

Delivery: of a message: a process acts on a message after it has arrived.

Correct process: a process that receives all messages that are sent to it, and for whom, all of the messages that it sends are received by all intended correct processes.

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

Agreement: If a correct process 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).

True Sharing: all rules are followed exactly. That is, messages are ordered before they are delivered.

Effective Sharing: messages are delivered upon arrival, regardless of ordering rule in effect. When the message is delivered, the state of the effected variable is transformed so that its (the variable's) state will be the same as if all of the messages that have been delivered were first ordered according to the rule in effect (i.e. Causal or Atomic).

Reliable Broadcast (RB): Validity + Agreement +Integrity

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

Atomic Order (AO): 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 the messages had been Causally Ordered.

Effective Atomic Order (EAO): 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 the messages had been Atomically Ordered.

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

(AO^RB) -> (EAO^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 Atomic Ordering, if one of the two is Effectively ordered and the other is not, it is equivalent to Atomic Ordering with Causal Ordering:

(CO^EAO) = (ECO^AO) = (CO^AO).

The above discussion is summarized 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	AO^  RB	Messages are delivered in the same order on all processes.
Atomic Causal Sharing	AO^  CO^  RB	Messages are delivered in the same Casual 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	EAO^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 Atomically Ordered).
Effective Atomic Causal Sharing	EAO^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 Atomically Ordered).

For more detailed descriptions of the sharing types, see [1].

As was discussed in the introduction, it may not be desirable to use the same sharing rules and / or sharing strength for a given object attribute during the entire life of a process in a DVE. Varying network performance and user preference might dictate that different sharing rules and strengths should be used.

For example, consider the position of the specialist in the shared DVE operating theater. Consider also a virtual probe available to both of the doctors that will allow a doctor to look at previously scanned CT images superimposed on the patient. It is important, but not vital, that the doctor performing the operation knows the position of the specialist: where he is standing and what he is seeing with the shared probe. It provides the doctor performing the operation with additional information about the specialist's perspective. During times of excellent network performance, we could use True Atomic Sharing to communicate this information between the two doctors. During times of poor network performance, we would not want to limit the movement of the probe, so we would reduce the strength of the sharing to Effective Atomic Sharing. This would allow free movement and good local response for probe movement, but would reduce fidelity in global response (the effect of which would be minimal unless the doctors were simultaneously trying to move the probe).

In the above example, if only one of the two processes (controlling the doctors' DVEs) decide to change the sharing strength, then it is easy to handle the messages that arrive out of context - messages sent with a different type of information sharing in mind. It is simple to handle this case, because, even if different sharing strengths are intended, all of the ordering information will be sent with each message.

In our implementation, messages obeying Effective Atomic Sharing and True Atomic Sharing have the same ordering information sent in the message: their age in the atomic timeline. The same is true for all True / Effective pairs. Whether a message is intended as Effective or True strength, the same information must be sent so that the message can either be pre-delivery ordered (True Sharing) or post-delivery transformed (Effective Sharing).

The situation gets more complicated when messages arrive that were intended to follow different ordering rules. If a message has additional information, that information can be discarded. For example, if one process was using Effective Causal Sharing for the probe's position, and a probe-position message arrive with True Atomic Causal Sharing information attached to it, the process can simply ignore the additional information associated with the message's Atomic Order.

However, if a message arrives that was not intended to be shared in a way that is enforced at the process, then the missing ordering information must be obtained via other means. Consider this example: a probe-position message that is intended as True Causal (only contains Causal Ordering information) arrives at a process that is enforcing Atomic Causal Sharing for the probe's position. The process will need to somehow gain Atomic Ordering information of the probe's position.

As a general solution, we considered the possibility of sending ordering information for every ordering rule with every message. The problem with this is that, with Atomic Ordering, messages need to be globally ordered. In our implementation, we chose a central server to accomplish this atomic-ization. Therefore, in order to send Atomic Ordering information with all messages, we would need to send every message through the central server. Sending every message through this server would unnecessarily hinder scalability.

An additional constraint we have placed on the system is that all processes using the same sharing rules and strengths must produce the missing ordering information identically. For example, consider 4 processes sharing the position of the probe - the performing doctor and three specialists (roughly depicted in Figure 3). Suppose that two of the processes are enforcing True Atomic Causal Sharing for the position (Figure 3 A, B), while the other two are enforcing Effective Causal Sharing (Figure 3 C, D). When a True Atomic Causal Sharing message is passed to a process enforcing Effective Casual Sharing, the Atomic Ordering information can be ignored and the Causal Sharing information is included and can be used. When an Effective Causal Sharing message arrives at the processes enforcing True Atomic Causal Sharing, the processes must produce Atomic Ordering information, and, moreover, the two processes must produce identical Atomic Ordering for the message. For example, consider a probe-position message m that only contains Causal Ordering information. When probe-position message m arrives at True Atomic Causal Sharing processes A and B, they must produce the same Atomic Ordering information for the message. That is, processes A and B must place the message in the same place in the Atomic Order. Though they are both inventing an order for the message, they must decide on the same place in the timeline of atomic messages for it.

Since it would unnecessarily hinder scalability, we produce missing Atomic Ordering information only as needed. When a message lacking necessary Atomic Ordering information arrives at a process that requires it, the message is forwarded to the central server to receive an Atomic Order (see Figure 3). The central server ensures that the same Atomic Order is returned every time it is requested for a given message. See Implementation for details on how this is done.

In order to obtain unintended Causal Ordering information we take the approach mentioned previously. We send Causal Ordering information - the events age in the causal timeline - with every message for every object attribute. This adds a word to the size of messages that would not have otherwise included the Causal Ordering information, but there is no way to guarantee that other processes are not expecting Causal Ordering information for that object attribute. It would be possible to determine an age for a given message once it arrives at a process (assigning it arbitrarily), but we would not be able to guarantee that a single message would be assigned the same causal age at all processes enforcing Causal Ordering without significant communication. Sending the Causal Ordering information with each message is a better solution.

It is important to note that our assignments of missing ordering information are somewhat arbitrary. With Causal Ordering, all processes are keeping track of the current age in the causal time-line (assuming that the current age is one plus whatever the highest age to have arrived), but they are not obeying Causal Ordering in their pre-ordering or post-transformation of messages. Therefore, the Causal Order that such a process appends to a message does not reflect an accurate causal ordering of events at that process for the object attribute in question. Instead it represents a good guess at the event's (message's) Causal Order with respect to the events which have taken place for that object attribute.

The same is true for Atomic Ordering. The central server will assign an Atomic Order to messages that are lacking it, but it will not be able to determine where in this order it would have been if the sending process had requested its Atomic Order when the message was first sent.

The reason that we have this problem with implying ordering information is that the different processors are passing through different series of states. We are placing a global ordering on events that happen in individual time frames. In truth, there is no correct ordering for some messages since processes can put themselves in a combined state (all object attributes) through which no other process will pass. We are not attempting to rectify this situation, we are simply trying to best represent the transformations through which processes should pass given their actions and the actions of the processes with whom they communicate.

This work was an extension of the framework developed at UNC-CH under DARPA research grant N66001-96-C-8507 and is described in more detail in [3]. The architecture was built using Java 1.0.2 on the Windows 95 platform. The rendering is done using DimensionX's Liquid Reality [4] (this will be replaced with Java3D once it is available) - see Figure 1.

Figure 1. A sceendump of the system during a sharing test.

The basic premise of that work was providing an architecture which allows: 1) seamless interoperability of all worlds built or encapsulated using its API, 2) objects to move among worlds without loosing functionality, 3) worlds -- which are 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. [1] extends this work by providing a taxonomy of sharing types with which application designers can override the default sharing types for any desired object attributes. This work extends that work by tackling the issue of switching between desired sharing types based on network performance and user preference.

The architecture presented in [3] is implemented in Java and is based on a single generic object that has four components. All objects (as considered in this work) share a common structure. Objects have sensors, from which they get information about the CVE and from other objects. They have an appearance that they display to the outside world. Each object has a set of actions that it uses to act on the world and other objects. Objects also have a state in which it stores self-important characteristics.

This is similar to the idea of Model, View, Controller. The Model is the object's state and the object's actions. The View is the object's appearance. The Controller is the object's sensors. See Figure 2.

Upon receipt of causal messages, a process will check to see if it has already delivered a message with that causal age for that object attribute since it is possible to have multiple messages with the same causal age (a single event can cause different events on different processes). If it has already delivered a message with that age, the message is discarded. If a process is using True Sharing for the arrived message's object attribute, then the process will determine if it should deliver the message immediately (if the messages age is one higher than the last delivered message) or postpone delivery and store it for later delivery (if the message is more than one higher than the last delivered message). After a message is delivered, the process checks the queue of messages to see if the next one in timeline has already arrived.

If a process is using Effective Sharing for the arrived message's object attribute, then the process will act on the message immediately and transform it with respect to the messages that have already been delivered. If the message is further along in the object attribute's timeline than any previously delivered message, than no transformation needs to be done. If it precedes any of the previously delivered messages, then it must be transformed with respect to all messages that have higher causal ages. For more details on post-delivery transformations see [1].

Atomic sharing is specified in the central server. As messages arrive at the central server, they are assigned the next higher age in the atomic timeline. Therefore, the messages are ordered according to their arrival time at the central server.

If a process is using True Sharing and Atomic Ordering for the object attribute then the process will determine if it should deliver the message immediately (if it is the next message) or postpone delivery and store it for later delivery (if the message is further along in the sequence). After a message is delivered, the process checks the queue of messages to see if the next one in the timeline has already arrived.

One of the other major implementation issues is determining the ordering information when it is lacking from a message. Causal Ordering information is included with every message, so the only information that needs to be reproduced is that of Atomic Ordering. To get the Atomic Ordering information, we have taken the approach of forwarding the message to the central server in order to obtain a value for the message's Atomic Order (See Figure 3).

It is true that it is likely that a message will receive different Atomic Order if a message is forwarded to the central server than if a message had been sent directly from the originating process to the central server. This is a consequence we are willing to accept in order to avoid reassigning Atomic Orders to any message that might have been delivered between the time the message was first sent (Figure 3 - t0) and when it is finally sent to the central server (Figure 3 - t1).

We are experimenting with two methods of obtaining missing Atomic Ordering information to a message. One is to forward the message with the Atomic Order to all processes which are interested in the atomic order of that object attribute (see Figure 3). With this method, we need to keep track of which processes are interested in the object attribute's Atomic Order. With this we also need to keep around a database of which messages have already been ordered, so that they will not be given a different Atomic Order if the message is sent from a different processor (Figure 3 - t2). Messages are easy to identify using the process's ID (assigned by the central server) and the message's causal age. Together, these pieces of data are unique for each message. This data is dropped from the DB once the message has arrived from every interested process or after a timeout period (we have this timeout period set at 1 hour - approximately 1000x the maximum observed message latency). We have a feeling that during heavy testing, that this method might become memory and CPU consuming.

The other method we are considering for determining Atomic Ordering is similar to the last discussed, but only returns the Atomic Order to the process sending message. As subsequent interested process queries the message's Atomic Order, the central server will look into its DB in order to determine if it has already given an order to the requested message. If it has, it will reply with that ordering information. If it has not, it will reply with a new order. Once again the signature of a message will be its process ID and the causal age of the message.

On the channels and for the central server, timing information is determined for every nth message (n= 10 currently). This spacing works because we send messages regularly in our current simulation, but we should augment this by sending timing messages at regular intervals, in order to keep timing information constant even during times of sparse network traffic.

The last implementation detail that we will discuss is how an application designer specifies sharing types and how the system switches among them. The application designer overrides a function that takes as its parameter the current latency in milliseconds. The function returns a triple containing the sharing strength, whether Atomic Ordering is used (a Boolean), and whether Causal Ordering is used. A default is provided that will returns either True Atomic Causal Order if the latency is less than one half of a second or Effective Atomic Causal Order otherwise (we have inhibited communication in our system so that latency of 1 second or more is common). Time is captured using a native method (implemented in C++), since no fine-grained timing functions are available in Java 1.0.2.

We are in the process of adding to the architecture the ability to allowing user-preference to be used as a metric in deciding sharing types. We are going to make it higher level than per object-attribute since it is a difficult problem to allow a user to specify preferences per object attribute without unduly cluttering the menu which they would use to make the change. We are going to allow the user to specify per-object (including the world object) whether the application should be more optimistic - pretend that latency is better than it is - or pessimistic - assume that latency is worse that it is. Preferences will be propagated to contained objects.

At this stage, not all of the testing is done. We will conduct a small user study, and we expect to find that dynamic information improves usability of DVEs when network performance varies. We expect to find that this is the case because, when using dynamic sharing, the user will not experience poor local response for messages even in times of heavy latency.

We also expect to find that it is difficult for users to know when sharing types have changed. We expect to find that this is the case because conflicts due to changing sharing types are rare in DVEs (and therefore the users can not see effects of the altered sharing types), and varying network performance, the effects of which are now somewhat avoided, hindered the users' experience without the use of our dynamic system.

In order to study better the effects of dynamically changing sharing types, we are working on applications, built on our architecture, that will cause conflicts when sharing types change. That is, we are constructing application that will, when Atomic Order and Causal Order are not obeyed, cause poor user experience.

BrickNet [5], by Singh et al. at the National University of Singapore, provides support for CVEs. The framework on which BrickNet is built is similar to the framework on which this work is built. Both provide support for sharing objects in and building of CVEs.

One of the primary differences between the two is that BrickNet does not have different types of sharing (this work provides several sharing types). As a result, they could not support dynamic configuration of sharing types. BrickNet provides True Atomic sharing but does not support Causal Ordering, and it does not support Effective Sharing. These additional types of sharing and dynamic configuration could be supported at the application level in BrickNet.

COTERIE [6], by MacIntyre and Feiner, is a framework on which to build CVEs. It allows Atomic Sharing at the object level. That is, all sharing done among processes is atomic, and entire objects are shared (not individual attributes of objects, as in this work). In COTERIE, all processes see all per-object-shared information pass through the same series of events. It should be possible to implement our object attribute sharing granularity, sharing types, and dynamic configuration at the application level in the COTERIE system, but they are not provided.

GROVE [7], 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. It deals 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 can be taken as messages arrive at a process, regardless of differences in desired and actual 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 [2] provide some useful insight from the world of parallel computing. They provide us with reliable broadcasts, Causal Sharing, and Atomic Sharing. They do 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 [8], 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 dynamically choosing the appropriate type of sharing for object attributes.

NPSNET [9] 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 our dynamic configuration of sharing types and reliable messaging.

SPLINE [10], 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 full replication of the parts of the worlds in which a process is interested. This work provides an alternative to this 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.

This paper describes two things:

• a taxonomy of sharing types which allow an application designer to specify more succinctly the types of sharing that are appropriate for a given piece of information
• and a way to switch among sharing types based on network performance and user preference.

We present this taxonomy and these ideas of dynamic configuration as both a reference implementation and a starting point from which application and architecture designers can determine their information sharing needs. That which is presented here is by no means complete. There are many additional rules that could be implemented in a system. For example, a bully algorithm for an object's position could be implemented in order to resolve conflicts when multiple users move the same object - the dominant process would have its change committed.

With additional rules, it might become apparent that there are additional sharing strengths. We use Effective and True strength sharing, but it is possible that there are other sharing strengths that would be useful (though, at the time of this paper, we have not come up with any others).

The strengths are visible to the end-users only in so much as they effect the order in which the messages are processed (users might see a different series of events depending on what sharing strength is enforced). If additional sharing strengths were to be implemented, they would also only effect the end-users by changing the series of events they see.

Some of the things we are envisioning for the future of this project are adjusting sharing based on Area of Interest, studying additional ordering rules and sharing strengths, and studying the dynamics of translating sharing patterns among composed systems.

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