Dynamic pointers and threads

Alan Dix


Download early version of full paper (PDF, 200K).

Full reference:

A. J. Dix (1995).
Dynamic pointers and threads.
Collaborative Computing, 1(3): pp. 191-216..

for related work see http://www.hcibook.com/alan/topics/dynamic/


The design of effective collaborative applications on mobile platforms has many problems. Wireless networks are fast enough that one aspires to true interactive applications, but too slow for much real-time feedback. This is exacerbated by the variability due to interference and broken connections. Mobile computing using wireless communications thus sits in a grey area between different styles of interaction. This paper examines these problems using concepts developed to understand general user interaction and computer-supported cooperative work. In particular, it will focus on the conflict between feedback for each user, awareness and feedthrough of the effect of each users actions to others, and the consistency of shared information during periods of disconnection.

Keywords collborative editing, distributed updates, document synchronisation, group undo, HCI, CSCW

Introduction section

The notion of location is central to virtually all manipulation. For a single-user system there is typically one key point of reference, often reified in the shape of an insertion point or mouse pointer, but even then there may be subsidiary locations, such as marked blocks or hyper-text links. For group working the issue becomes more problematic, with different users having different views of shared objects, and operating at different locations.

This paper concerns dynamic pointers - a mechanism for the description and implementation of various forms of location information, and threads - light-weight versions expressing the divergence due to the distributed nature of much group working. For the purpose of this paper, threads will be seen as the subsidiary concept, although one could discuss threads in their own right.

The domain which will be addressed is group editing/update, but drawn widely to encompasses virtually all manipulation of shared information.

The remainder of this section will give a brief introduction to dynamic pointers and threads. Then in the next two sections we shall consider dynamic pointers in more detail. First a rationale as to why pointers are not just one small detail in system design, but, instead, one of the key issues. After that we will consider a model for dynamic pointers - an semi-formal description of a formal model described in more detail elsewhere [Dix:1991]. Thus far, the material will be largely a review of previous work on dynamic pointers targeted at single-user interaction.

Sections 4 to 6 will discuss the application of dynamic pointers to various forms of group editing. First of all we will consider synchronous editing, how dynamic pointers can describe the appropriate behaviour of multiple insertion points, and has also been used to analyse the various options for group undo support. Then Section 5 will show how Ellis and Gibbs' algorithm for distributed synchronous group editing can be seen as a special case of dynamic pointers. In the course of this discussion, we will also introduce the concept of threads. Finally in Section 6, we will see how dynamic pointers and threads apply to more widely distributed asynchronous editing.

During the discussion we will see that dynamic pointers are pervasive in existing systems, but largely implicitly. In the last part of this paper (Section 7), we will see that dynamic pointers are not only a way of talking about implementations, but are an effective implementation device.

Dynamic pointers

Dynamic pointers were originally developed several years ago to deal with issues of location (cursors etc.) in single-user systems [Dix 1991]. What then are they doing in a journal dedicated to CSCW and group working? Well, the context in which dynamic pointers were developed was single-users with multiple views. It is not surprising then that they are readily applicable to various problems in groupware. In particular, we shall see that Ellis and Gibbs' algorithm for distributed synchronous group editing can be regarded as a 'special case' of dynamic pointers.

Dynamic pointers describe the update behaviour of various forms of location information such as text insertion points, selections, other block markers and various forms of hyper-text anchor point. Most important, we are able to discuss the behaviour of multiple pointers into the same object. This is clearly useful if we are to deal with several users' insertion points while engaged in group editing (see Figure 1).

In addition, many interfaces can be seen as composed of several layers, with the actual application objects at the deepest level and various levels of viewing and presentation between it and the user. For a multi-user interface, users may well be accessing the same shared objects, but be doing so via very different views. Dynamic pointers also help us to express the relationship between interface layers, and thus make it easier to distinguish those user actions which are truly shared from those which concern the individual user's interface.

Dynamic pointers serve several roles.

We will see examples of each of these uses throughout this paper. Dynamic pointers will be used to describe the desired behaviour of synchronous group editing (as in Figure 1). They will then be used to discuss Ellis and Gibbs' algorithm for distributed synchronous group editing, that is, in a specification role. Finally, at the end of the paper, we will see how dynamic pointers are an effective implementation mechanism, and in particular, make for truly extensible group widgets.

Most of the examples in this paper will concern linear text. Dynamic pointers apply equally to non-linear structures, such as trees or hyper-text. However, sequential text turns out to be the most difficult case.


As soon as we have several users working at a distance on the same objects there are potential conflicts due to several users attempting to update the same object at the same time. At very least some users' views may be out-of-date. the traditional approach to this problem is to prevent it occurring, by locking and mutual exclusion. However, in many cooperative working situations this is not suitable. Threads are a way of describing the resulting divergence of users' views of an object and ways of attempting reconciliation.

Threads can be thought of as light-weight versions and are named by analogy with the 'threads' or light-weight processes, found in several operating systems and programming environments. The light-weightness can be extreme - in local network applications, the divergence between different users' versions may only last for a few seconds.

Threads are closely connected with dynamic pointers, as the latter form a mechanism to facilitate the reconciliation of differing versions. Like dynamic pointers their use can be notional - as they describe the interface phenomena and algorithms, or practical - as an explicit feature of the implementation.


http://www.hcibook.com/alan/papers/dynamic-pntrs-95/ Alan Dix 2/1/2002