David G. Durand Computer Science Department Boston University 111 Cummington Street Boston, MA 02215 Email: dgd at cs.brown.edu Telephone: (401)-781-5137
This paper describes the Palimpsest data model, which describes flexible merging and tracking of individual changes to shared hypertext or multimedia documents. Palimpsest is designed to represent and manage the sorts of versioning problems that will inevitably occur in distributed collaborative manipulation of shared data. In fact, in a cooperative editing environment the problems that Palimpsest addresses must be handled, regardless of whether revision maintenance is a primary feature of the user interface. By basing the fundamental structures of Palimpsest on the individual changes (or deltas) made to the shared data at a fine grain, a wide variety of revision management strategies can be represented, while the scope of possible conflicts is reduced to the smallest possible portion of the document.
Keywords: version control, computer-supported cooperative work, collaborative editing, hypertext systems, concurrency.ntroduction
The topic of version maintenance has been a traditional part of hypertext system design since the field's inception (see [6, 15]). In the traditional view, versioning is presented as a desirable or essential convenience for a hypertext author (see [22, 23]). Indeed it is this justification for version control that Halasz questioned in [10]. However, some of the most important arguments that will be presented for the Palimpsest (note 1) data model described here are not based on user version control capabilities, but on ensuring correctness and consistency in the distributed editing of collaborative, constructive hypertexts (see [11]).
This work takes a foundational approach to the problem of managing versions to facilitate collaboration. Palimpsest provides a clearly defined groundwork for describing and then directly tackling the problems of asynchronous editing of data structures and merging the results of such editing operations. As such, it defines a base-level architecture on which applications will be built. In order to ensure that the fundamental problems are dealt with in full detail, no a priori decisions have been made about restrictions on the operating environment have been made. In particular, it was not a requirement that Palimpsest accommodate version-unaware applications unless that was possible without sacrificing functionality. Instead the goal was to find a simple, consistent, and maximally flexible way to represent the complexities of asynchronous editing.
Palimpsest can represent many application data structures, including links. For instance, Palimpsest can describe linear data files, structured hypertexts, tables, fixed format records, and also allows the description of a wide range of version control strategies for such structures, including:
Palimpsest provides all this without requiring a priori assumptions about synchronization, access, or update policies. In fact, a major goal of Palimpsest is to remain policy independent, so that many issues of locking, access, and control that are major differentiating factors between the ap- proaches of these systems are simply not restricted by Palimpsest. Thus the revision histories that Palimpsest can represent are a superset of the serializable or branching schedules enforced by traditional techniques. This allows the implementation and specification of a wide range of conflict resolution strategies. The final conflict resolution strategy in a collaborative editing situation is to report a conflict to the author and allow her to decide the correct resolution and it is this final recourse that allows Palimpsest to be so flexible in its temporal representation; a program need not have sole repsonsibility for creating a consistent version from conficting instructions.
The basic scenario underlying Palimpsest is the following: two authors are working on the same hypertext document. Each works on a separate computer, which is intermittently in contact with the other author's computer(note 2). We want to allow either author to change any aspects of the document, without being forced to wait for communication to be established, while still allowing the resulting changes to be integrated and harmonized at a later point. Given current advances in structured document representation, multimedia and hypertext, such documents may contain intricate data (sound, structured text, graphics, video) as well as complex cross-reference structures.
This scenario highlights the needs and realities of collaborative computing. Platforms for collaborative editing may include:
A fast local network is ideal for cooperative editing, and allows the use of traditional synchronization techniques without creating bottlenecks. This will remain possible given any continuously available communications access (though even WAN connections are far from perfect in this respect). When communications are intermittent, such strategies are insufficient; inconsistencies in the collaborators' views of the shared data are bound to occur [8].
Hence the Palimpsest model describes shared data structures, accessed by an arbitrary number of processes making changes and incurring arbitrary delays before seeing the changes made by other processes. Each process has a different view of the shared data structure. In order to merge and compare views, Palimpsest must track the identity of each data item as it changes. Tracking the identities of items makes merging or comparing divergent versions trivial by eliminating the need for complex heuristics, and is especially useful in the support of hypertext linking: even though data are always open to the possibility of change, links can be kept up to date because anchors have invariant identifiers.
Palimpsest's tracking of individual changes also integrates such thorny problems as collaborative undo (see [17]), the consistency of shared documents (see [4, 9, 14, 21]), and user-level tracking of collaborative changes (as provided in collaborative editing environments such as Prep [16]).
Consider a variation of the scenario above: tracking revisions to a string. A string corresponds to a Palimpsest sequence and is just one of the sorts of structured data that Palimpsest can handle.
Let us start with a sentence "The dog worried at the bone.", and two authors simultaneously making changes:
Alice inserts the string "ate", creating the string "The dog ate worried at the bone". Then she deletes the string "worried at" and produces the string: "The dog ate the bone.". Finally she decides on brevity, and deletes the entire end of the sentence to produce the result "The dog ate.".
Simultaneously, Bill is making other changes: first he inserts the word "big" before the word bone and creates the sentence: "The dog worried at the big bone.". Then he adds the words "and glove" at the end to produce "The dog worried at the big bone and glove.".
Now we want to merge the separate sets of changes. The Palimpsest model allows the definition of a wide variety of delta types, each corresponding to an application transaction. In this example we have three simple types:
A state of the document is defined by a set of deltas (see Figure 1). Note that deltas are not sequentially ordered like editing instructions, but can be interpreted without reference to an explicit time sequence. While deltas in this example correspond to very simple changes, a delta may, in the general case, contain several operations corresponding to a complex application transaction.
The flexibility of combination permitted by the representation makes it easy to create a merged version: "The dog ate the big bone and glove." even though the individual changes of which that version is constructed were separately developed without any coordination between the two editors other than the initial sharing of a common starting point.
Unfortunately, many changes are considerably more complicated, because they are best described in terms of the replacement or movement of data rather than in terms of simple insertions and deletions. Copying, for example, presents real problems: at least two distinct notions of copying are possible and useful. Copied data may or may not be affected by changes made to the original source of the data. One form of copy corresponds to an insertion of data along with an indication that it was originally found elsewhere in a document, while the other definition might be more accurately described as an assertion that two parts of a document should always be identical. Palimpsest's system of delta-types allows both policies to be specified exactly by creating deltas with particular effects, without Palimpsest itself mandating such policy decisions.
Given the constraints described above, four foundational principles have been chosen.
Palimpsest can broken into two levels. The datatype level is a set of primitive types and type constructors which represent application data types. For instance, a Palimpsest model of a simple word processing file is concerned with representing the various states of a sequence of characters as portions of it are moved, copied, inserted and deleted. At the datatype level the file is a sequence of characters. The datatype level describes the structure of states of application data independent of the operations that have formed that data.
The representation level of Palimpsest describes constructs at the datatype level as a set of deltas, each recording some aspect of the data's history. This is where data is created and updated,, while the datatype level is an application's view of data states obtained by a Palimpsest interpreta- tion. While an application will naturally have to deal with the repre- sentation level to the degree that it allows the interpretation and manipulation of change-histories, these details may not be a primary part of a user's view of the data.
Palimpsest divides the notion of consistency into three levels to allow change conflict detection and resolution. The fundamental notion of consistency is minimal consistency. A set of deltas is minimally consistent if its members refer only to deltas within the set. This is an easy condition to satisfy: deltas created starting from a minimally consistent set and referring to deltas within that set can be added to it to produce a larger minimally consistent set. In other words, given a consistent set of deltas, a process can make new deltas and preserve minimal consistency without worrying about other processes. Minimal consistency is required by Palimpsest; the semantics of missing information (nonexistent deltas) is not be defined.
However, some minimally consistent Palimpsest states represent situations that violate desired properties of the datatype level. When such constraints fail, that represents a situation where some deltas represent conflicting updates, and some action must be taken to resolve the conflict. Palimpsest consistency is a level of consistency which ensures that a set of deltas can be unambiguously interpreted to provide a datatype level view. Non-Palimpsest consistent states occur only when separate processes are involved. For instance while the union of two minimally consistent sets will always be minimally consistent, Palimpsest consistency is not necessarily preserved in such a case. One of the strengths of the Palimpsest model is its ability to represent such non-consistent states, and pinpoint exact loci of conflict for corrective action.
The term application consistency is reserved for any other restrictions that an application might need to impose on Palimpsest consistent structures. Application consistency must be checked and enforced by the application itself.
Palimpsest provides type constructors for types such as sequences, sets, and tables, as well as a set of primitive types. Primitive types can cover a wide range of objects: for textual data they might be character codes chosen from a specific character set; for graphic data, pixel color values; and for spreadsheets, numeric or string cell values.
The smallest actions represented in Palimpsest are basic changes. These are bundled into deltas, which are the form of Palimpsest transactions. Each delta encodes several simultaneous basic changes. A single delta, for instance, might record simultaneous insertions into several different sequences.
Deltas also contain data blocks, each representing a portion of some data object in the system. A data block may contain constant data of any primitive type, or created by a composition of Palimpsest type constructors and basic types. A data block might contain a single piece of basic data, a sequence of sets of basic data items, or a set of references. All or part of a data block's content may be obtained by copying from elsewhere, in which case the copied data is referred to as imported data. Imported data can be designated by an address, or by a range. An address is a specification of a particular Palimpsest data object, while a range is a sub-sequence or sub-table specified by boundary points.
The principle behind the representation of constructed types in Palimpsest is that datatype level object is originally created by some delta that provides one of its data blocks. Additional changes to that block may be made by other deltas. So sets copied into a set create a larger set (the union) and sequences imported into a sequence create a longer sequence with the new elements interpolated at the point of insertion.
Since basic changes must refer to the data in data blocks, all data need to have addresses which are unique within the delta; some items (such as the contents of sequences) need addresses with special properties(note 3). Deltas themselves have globally unique identifiers(note 4), so a pair consisting of the unique identifier of a delta and the internal address of a data item constitutes the address of that data item.
There are 3 fundamental actions described by basic changes:
Palimpsest must further differentiate some of these operations, in order to work in all cases without ambiguity.
The copy operation causes data to be copied from one location to another location (either internal or external to the containing delta). A copy refers to two locations, a source and a destination; the copied data appears in both locations. Sources must always refer to one or more actual elements of a structure, while destinations can refer to a location at which data can be inserted, or to data that should be replaced by the copied data. Any changes applied to a source will also be reflected in the destination.
Deletion occurs in two forms: deletion and removal. Deletion actually eliminates data. In any set of deltas that includes a basic change that deletes data, that data will not appear to the application anywhere. By contrast, removal eliminates data from a particular location, but does not prevent that data from being the source of a copy operation, which will cause that data to be included at the destination. Removal is used in representing data movement generally; in Palimpsest movement is analyzed as the removal of data and its reinsertion at a new location.
The contents of data blocks that are provided by a delta are available to the application. The data items provided by set of deltas are the application data contents of that set.
These basic changes, along with data declarations, provide the fundamental components of deltas.
While not directly specified by Palimpsest, some appropriate base data types (characters, integers, video frames, etc.) are needed for applications. Palimpsest provides primitives to structure and represent the organization of the base data types, whatever they may be. Palimpsest does not represent internal changes in base types.(note 5)
The exact representation of base data depends on the application, but from the point of view of Palimpsest, it is simply a unitary, structure-free unit. A delta providing only base data represents an item of a particular type: only its contents and its address are available. Base data is generally a part of more complex deltas, which record relationships and configurations of primitive data items and other data structures.
It is convenient to have a special null data item, e. A sequence whose content is just e is an empty sequence. It is used in representing the creation of empty structures, and can also be used to interpolate extra addresses between data items in sequences.
These allow the representation of application-level graph structures, by providing a generalized pointer type capable of referring to Palimpsest data, and can be used in implementing hypertext links, indexes, or other organizational structures. A Palimpsest reference is visible to an applica- tion, and must be interpreted by an application. The only editing operation that can be performed on a reference is to update it to refer to a different location. The representation of references is the same as that of the Palimpsest address used in basic changes.
Delta-references allow Palimpsest to describe version and change data for application purposes. The interpretation of delta references is an applica- tion specific matter. For instance, a set of deltas might have significance as defining the August 12th version of a document. Palimpsest could store this set of deltas and provide their ids to the application, which would then be able to refer to that particular version, or to record the creation of a new version that differs by the addition or removal of particular deltas.
Since the data content of a Palimpsest structure is defined by a set of deltas, the provision of delta-references allows the representation of version-histories to be a done via Palimpsest itself. The representation of a delta-reference is simply the unique identifier of a delta. Like a reference, a delta reference can only have its value updated.
A set is the simplest Palimpsest type constructor and represents an unordered group of objects. The fundamental changes that can happen to a set are the addition of an element to the set, the deletion of an element from a set, or the replacement of an element in the set by some other element. Sets can be used for any unordered collection of data items, but have particular application in the representation of versions as sets of delta-references.
If a set within a delta is the target of a copy, the contents of the sources will be added to the set. By Palimpsest convention, items or sets of items must copy to the delta that provided the original set: the inverted trees representing sets have only one level.
A sequence represents a totally ordered set of items. Operations that can be performed on a sequence are the insertion of a new element, the deletion of an old element, the movement of an element to a new position in the sequence, or the replacement of an element in the sequence. Because of the nature of sequences, there are three useful ways to refer to locations in them:
The basic changes that can apply to sequences are replacement of an element or sub-sequence by a new element or sub-sequence, insertion of a new element or subsequence at a particular point, or the deletion of an element or sub-sequence.
Tables are n-dimensional tabular structures defined by n aggregates (sequences or sets) specifying its dimensions. Operations that can be performed on tables are: the addition or rearrangement of rows, associating an object with a table position, or replacing a table position's contents. Currently, Palimpsest tables must have a fixed rank, though their dimensions are subject to change.
The aggregates that define the coordinate space of a table are its axes. An individual cell address is a tuple of elements, one from each axis of the tables. In a two-dimensional table, for instance, the elements of the two axes are representatives of their entire rows or columns.
The contents of cells are separately copied to address(es) within the table. Palimpsest allows the association of the same object with several table positions, much as a sequence of characters may contain the same letters in different positions. This representational feature of Palimpsest is needed to represent fairly common sorts of tabular matter that contain straddle heads, or unusually shaped cells (L-shaped cells are surprisingly common in tabular matter).
The basic model for Palimpsest implementations is a communicating group of peer servers. Each server will have a local database of deltas, and it will communicate with other Palimpsest servers, exchanging deltas reflecting user activities. While nothing in the Palimpsest model prevents the use of client- server style architecture (say between a microcomputer front-end and a de- partmental data server), the model does not require one, since no central synchronization is necessary.
The Palimpsest representation itself is not optimized for database access, so a typical implementation will have a fast local database, which will store the accumulated deltas in a form to allow rapid retrieval of desired versions as needed. This local database may be optimized for a particular set of deltas used in the application. Deltas themselves form the units of Palimpsest update protocols.
A relatively simple architecture suffices for a Palimpsest node. It maintains 3 data structures:
Whenever a local node can establish communication with a remote node, it asks for new deltas created since the last time communication was established. The remote node answers this query by referencing its own chronological log. The local node then sends all new deltas it has obtained since its last communication with the remote node. This extremely simple protocol implements an epidemic algorithm for propagating deltas among Palimpsest nodes (see [5, 8]).(note 6)
A chronological log of deltas has other advantages, ror example, in recovering from potential failures of the optimized database, or allowing space-efficient but slow access to unused deltas purged from the fast database.
Here we give a few examples(note 7) of how Palimpsest definitions represent both the structure of data to be manipulated by a program and the sorts of manipulations that the data can undergo.
Deltatype text-node is {
Data contents: Sequence Of
Characters;
Provide(contents);
}
Deltatype copy is {
Range x : Sequence of Characters;
Address y : Sequence of Characters;
Copy(x, y);
}
Deltatype move is {
Range x : Sequence of Characters,
y : Sequence of Characters;
Copy(x, y);
Remove(x);
}
Deltatype insert is {
Data insertion-contents :
Sequence of Characters;
Address where : Sequence of
Characters;
copy(insertion-contents, where);
}
Deltatype deletion is {
Range x : Sequence of Characters;
Delete(x);
}
Deltatype link is {
Data link_contents = Sequence of {
Data from : Reference;
Data to : Reference;
Data explainer :
Sequence of Characters;
}
} |
| Figure 3: Description of a Text Node with links |
Figure 3 shows a Palimpsest description for an application that provides simple linear text nodes, with links between arbitrary segments of the constituent nodes. The syntax of this description is intended to be sug- gestive of a range of issues and features not fully elaborated in this paper for reasons of space. Each delta declares a number of data items and named data addresses, followed by a list of the basic actions performed by this delta. The operations defined here are the insertion of new text, the deletion of text, the movement of text from one location to another, and the creation of links. If the source of moved text is changed, then the text at the destination will include all changes made to the original text.
Notice that a link can be included in any version that includes its endpoints. However, once created a link may not be changed, since we have defined no deltas to represent such changes. A new link with the desired properties may of course be added at any time. Nor can an application using this definition use Palimpsest to maintain its revision information; it must explicitly decide which deltas constitute a version of a document. This means that the application can directly manipulate any minimally consistent docu- ment, but that it must accept the responsibility of dealing with the full generality of Palimpsest.
A simple version-control facility can be added to the above definitions by defining some new delta types. A version delta records the creation of a new version, which is just a set of delta-ids, each representing one of the constituent changes composing that version. An add-change delta is also needed to add a new delta to a version. These definitions are shown in Figure 4.
In the simple versioning structure given here, any number of document versions can be created, and new deltas can be added to each version. Because the versions are represented as Palimpsest objects an application does not have to worry about all individual deltas. Instead, Palimpsest can be di- rected to adjust the datatype level view to include only data corresponding to deltas of a particular version. The contents of the version object will select the relevant deltas from a larger pool describing several versions.
Many operations on versions are now easy. For instance, finding the differences between two versions is done by taking the symmetric difference of the delta sets describing them. Merging two versions means creating a new version whose contents are the union of the two original sets. Acquiring a new version from another node simply means adding the deltas defining that version to the application's pool of deltas.
Deltatype version is {
Data version-contents is Sequence of
{
Data version-changes
: Set of Delta-references;
Data version-name
: Sequence of Characters;
}
provide(version-changes);
}
Deltatype add-change is {
Address the-version
: version.version-contents
Data new-deltas : Set of Delta-
references;
copy(new-deltas, the-version);
} |
| Figure 4: Simple versioning |
Palimpsest provides a solution to the problems of cooperative work in computing environments where constant communication between collaborators cannot be assured. Its fundamental emphasis makes editing actions the central objects of concern, and then makes those actions as recombinable as possible. This enables a uniform approach to a variety of difficult problems in distributed editing system design. This form of solution is possible for hypertext systems precisely because the normal notions of consistency and synchronization familiar from database theory and operating system design enforce far stronger conditions than a document processing system requires. Since transactions in cooperative editing are carried out by people rather than programs, conflict resolution can be handled by the users of a system, if necessary, without essential difficulty.
Some form of version control is necessary for correctness in a distributed editing environment, if that environment is not synchronized by continuous updates. Even when on-line communication is available and dependable, Palimpsest allows the use of optimistic concurrency control rather than locking. This can allow higher efficiency when users' actions conflict infrequently, since they need not wait for confirmation before making changes. In a database system, of course, optimistic concurrency still has to be able to abort a transaction. In Palimpsest, a conflicting transaction will usually prompt a notification of an inconsistency that needs correction.
The general idea of basing configuration or version control around changes to data rather than states of data has been suggested previously in the software engineering literature (see [12, 13]), but Palimpsest presents many significant differences from this work. Software engineering is concerned with versions of simple text files, while Palimpsest provides the ability to extend the same level of control to much more intricate structures than line- oriented program files. Software engineering systems also have to deal with complex inter-program constraints in order to ensure that a final software system will be correct; such issues are of less importance in the Palimpsest framework as there is no hope of automating the authoring process itself.
The implementation and testing of a generic Palimpsest database needs to be completed, and the performance measured. A variety of update protocols and policies need to be evaluated, and an examination of what level of Palimpsest functionality needs to be directly available to the user needs to be undertaken. The change-oriented approach adopted by Palimpsest provides a clear integrated framework for implementing collaborative editing systems under the constraints of realistic present-day communication environments.
[1] Campbell, B. and J. M. Goodman. "HAM: A General-Purpose Hypertext Abstract Machine" Hypertext '87. 21-32, 1987.
[2] Cohen, E. S., D. A. Soni, R. Gluecker, W. M. Hasling, R. W. Schwanke and M. E. Wagner. "Version Management in Gypsy" ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments. 1988.
[3] Coulouris, G. F. and J. Dollimore. Distributed Systems: Concepts and Design. 1988 Addison-Wesley.
[4] Delisle, N. M. and M. D. Schwartz. "Contexts -- A Partitioning Concept for Hypertext" TOIS. 5(3): 168-186, 1987.
[5] Demers, A., D. Greene, C. Hause, W. Irish, J. Larson, S. Schenker, H. Sturgis, D. Swineheart and D. Terry. "Epidemic Algorithms for Replicated Database Maintenance" ACM Operating Systems Review. : January, 1988.
[6] Engelbart, D. C. "Authorship Provisions in Augment" IEEE 1984 COMPCON Proceedings. 465-472, 1984.
[7] Engelbart, D. C., R. W. Watson and J. C. Norton. "The Augmented Knowledge Workshop" National Computer Conference. 9-21, 1973.
[8] Greif, I. and S. Sarin. "Data sharing in group work" ACM Transactions on Office Information Systems. 5(2): 187-211, 1987.
[9] Haake, J. M. and B. Wilson. "Supporting Collaborative Writing of Documents in Sepia" CSCW '92: Proceedings of the ACM Conference on Computer Supported Cooperative Work. 1992.
[10] Halasz, F. "Seven Issues revisited" Hypertext '91 Proceedings -- plenary address. 1991.
[11] Joyce, M. "Siren Shapes: Exploratory and Constructive Hypertext" Academic Computing. (3): pp. 10-14, 1988.
[12] Kruskal, V. "Managing Multi-Version Programs with an Editor" IBM J. Res. Develop. 28(1): 74-81, 1984.
[13] Lie, A., R. Conradi, T. Didriksen and E.-A. Karlsson. "Change Oriented Versioning" ESEC (European Software engineering Conference). Lecture Notes in Computer Science. 387: 191-202, 1989.
[14] Narayanaswami, K. and N. Goldman. ""Lazy" Consistency: A Basis for Cooperative Software Development" CSCW '92: Proceedings of the ACM Conference on Computer Supported Cooperative Work. 51-58, 1992.
[15] Nelson, T. H. Literary Machines. 1987 Theodor H. Nelson. Fredricksburg.
[16] Neuwirth, C. M., R. Chandhok, D. S. Kaufer, P. Erion, J. Morris and D. Miller. "Flexible Diff-ing in a Collaborative Writing System" CSCW '92: Proceedings of the ACM Conference on Computer Supported Cooperative Work. 51- 58, 1992.
[17] Prakash, A. and M. J. Knister. "Undoing Actions in Collaborative Work" CSCW '92: Proceedings of the ACM Conference on Computer Supported Cooperative Work. 273-280, 1992.
[18] Rochkind, M. J. "The Source Code Control System" 1(4): 364-370, 1975.
[19] Streitz, N., J. Haake, A. Lemke, W. Schuler, H. ShŸtt and M. ThŸring. "SEPIA: A Cooperative Hypermedia Authoring Environment" Proceedings of the ACM Conference on Hypertext. 11-22, 1992.
[20] Tichy, W. F. "RCS -- A System for Version Control" 15(7): 637-654, 1985.
[21] Walpole, J., G. S. Blair, J. Malik and J. R. Nicol. "A Unifying Model for Consistent Distributed Software Development Environments" ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments. 1988.
[22] Weber, A. Publishing Tools Need Both: State-Oriented and Task-Oriented Version Support. Gesselschaft fŸr Mathematik un Datenverarbeitung MBH: Artbeitspapiere der GMD 526. 1991.
[23] Weber, A. Versioning Issues in Hypermedia Publishing Environments. Gesselschaft fŸr Mathematik un Datenverarbeitung MBH: Artbeitspapiere der GMD 542. 1991.
[24] Weber, A. "CoVer: A Contextual Version Server for Hypertext Applications" Proceedings of the ACM Conference on Hypertext. 43-52, 1992.
Note 1
The name Palimpsest is appropriate for a versioning model, since a
palimpsest is a parchment which has been erased and rewritten. I would
like to acknowledge Steven DeRose, Abdesalam Heddaya, and Mark Bernstein
for many helpful comments on this paper and Palimpsest itself.
Note 2
We cannot assume that a connection can be established on demand, though
we will assume that information eventually gets through.
Note 3
Such as being totally ordered, as in the case of sequences. Palimpsest
has opted to provide a primitive array construct (the sequence) when in
fact the same results could have been achieved by the use of references and
additional application semantics (representing seqences as application
level linked lists). This was deemed undesirable because of the frequent
and important applications of sequences in data and document processing
systems.
Note 4
Standard mechanisms exist for creating such identifiers in a distributed
environment [3]. The costs of collision in Palimpsest are also small -- a
delta ID collision can be treated as any other Palimpsest inconsistency,
and then resolved.
Note 5
The choice of base types is extremely important. A Palimpsest model of
film or video editing where the base type was a clip would not be able to
express many kinds of editing, since only rearrangements of the basic clips
could be represented. On the other hand, if a frame were the basic unit,
all normal film editing functions could be represented. In order to
represent special effects or film compositing, where portions of frames
need to be explicitly represented and manipulated, the basic data item
would have to be much smaller (like a pixel), in order for complete
modeling of the relevant changes.
Of course, even with single frames as base data, non-Palimpsest editing of an individual frame could create a new frame to replace an old one, but any internal relationships between the two frames would not be represented.
Note 6
At Boston University, we have begun implementing a generic Palimpsest
based back end using the software architecture described in this section.
Note 7
There may be several sorts of deltas, and several sorts of base data, and
it is clear that we may in general want to impose various type restrictions
on constructed structures: For instance, we might wish not to have keyword
values with video clips in them. In examples, types will be written for
clarity, but this aspect of the model is still evolving.