# Chapter Three: Pseudo-time and Possibilities In this chapter and the next, I describe a semantic interface for shared objects and the operations on them. The emphasis in these chapters is on the behavior of the interfaces, rather than on their implementation. For this reason, I will take an abstract view of the nodes, objects and computations in the system, such that the view represents fairly accurately what the "applications programmer" might imagine the system to look like. Briefly let me outline what will happen. The key ideas of the thesis are presented in this chapter. Two key abstractions, pseudo-time, a way of relating and synchronizing the order of actions at multiple nodes, and possibilities, groupings of actions that must be done all at once or not at all, provide the tools by which a programmer can manage the effects described in the previous chapter. Objects that have indefinite scope and extent provide the mechanism for information sharing. Basic concurrency control, defining the interactions between independently executing computations accessing the same objects, is done locally at each object, resulting in defining the semantics of an individual object in terms of an object history. To achieve more global control of the interactions between computations, particularly exemplified by the notion of a transaction, pseudo-time is used to relate individual object histories to obtain a system history. The system history defines the notion of a consistent state of the system. Programs can then ensure that they observe consistent inputs and generate consistent outputs by the use of a pseudo-temporal environment, a dynamic naming environment that functions to "stop the action" seen by the program, even though the system is not necessarily stopped. As noted in the previous chapter, a key problem m distributed decentralized systems is dealing with the uncertainty resulting from an attempt to perform a remote action. The basic approach developed here to solve this problem is to make the changes involved in a remotely requested action in two steps. The first step tentatively performs the computation, such that no other independent computation can observe it. The changes made to each object are grouped into a set called a possibility. If the first step goes to completion without a hitch, the computation ts confirmed by an act that converts the possibility into a "reality." If not, the possibility safely times out, eliminating the tentative changes from the system. Creation of composite actions out of independently designed actions whose implementation details may be inaccessible to the programmer requires discipline in synchronizing the component actions and in managing failures, both on the part of the programmer doing the composition and on the part of the programmers who designed the actions being combined. By using the same pseudo-temporal environment and possibility with all the actions being combined, easy combination of parallel actions can be achieved. To allow the construction of such composite actions in such a way that they are not dependent upon the correct behavior of their user, the possibility concept is extended to include the notion of a dependent possibility. ## 3.1 Objects Objects are the means by which information is shared within the system between independently executing computations. An object is a named repository for information. Objects possess a state that can be observed and modified by the execution of programs that refer to the object as an operand. Objects are abstract, in the sense that while an individual object may in fact be represented in terms of a group of lower level objects, the representation is invisible to its users. The essence of objecthood is possession of a name. In this thesis, I am concerned with objects used to store information for a long time (e.g., longer than the time between system crashes, or longer than the life of an individual console session) and that may be accessed by an unknown set of users (programs, people). The objects may be catalogued in a file system, such that the names used by the user programs will be character data, rather than pointers. The scope and extent of such names are not even deducible from within the system. Even if the objects are named only by unique identifiers (pointers), due to the decentralization of the system there may be no way to determine what references to an object exist. In a centralized system, by tagging unique identifiers stored within objects, mechanisms for finding all references to an object are possible (e.g. to garbage collect objects no longer referred to). In a system whose design was centralized (top-down by one person), all potential interactions are constrained at design time. Neither of these ways to limit interactions between computations will always be possible in a decentralized system whose design evolves in a decentralized way. The lack of constraints on scope and extent make the job of proper synchronization difficult, because the set of independent, asynchronous computations that could interact with an object may not be easily discovered. The semantics of objects are defined locally to their implementation. In the abstract, the state of an object reflects the history of operations applied to it. The implementation of the operations in terms of the underlying representation of the object's state is solely managed by a program called a type manager that is common to all of the objects of a particular type. Hiding the implementation of objects within its type manager allows the implementation of objects to be modified and controlled locally, without the need for users of the objects to be aware of changes. CLU[Liskov78] and ALPHARD[Wulf74] provide this kind of implementation hiding, as do ACTORS[Hewitt76]. ACTORS in addition provide local control of synchronization between independently initiated operations on the same object[Hewitt77]. In this thesis, the basic synchronization of independent computations also is provided local to the type managers of individual objects. However, the abstractions defined in this chapter allow construction of synchronization behaviors that involve multiple objects, whereas Actors can handle multiple object constraints only by the construction of intermediate objects to mediate accesses to objects requiring synchronization[Atkinson78]. In the rest of the thesis, CLU syntax[Liskov78] is used to represent programs and objects. The objects of this thesis, however, are different from CLU objects in an important sense. They are shared by multiple users and are used to store information for a long time. NAMOS also allows arbitrary parallelism, while the current definition and implementation of CLU does not. CLU is used because the standard languages, such as Algol 60, PL/I, FORTRAN, etc. do not provide facilities for the construction of abstract types and operations, but we are very interested in exploring the interactions between abstraction mechanisms used to build modular systems and parallel execution and long-term storage of objects. Because the CLU type abstraction mechanism is used to describe types of objects that are stored for long-term, shared use, we will have no syntax for describing the short-term, unshared types that CLU's object abstraction mechanism provides. This lack of syntax is not troublesome for the purposes of the thesis because we shall have little neerl .to refer to such types in examples, but a real system should provide both mechanisms. Message sending is implicit in the programs we use in examples. Executing some part of a program may require the sending of a message from the site currently executing the program to another node -- the mechanism by which this message is generated is not important. The programs themselves are written as sequences of steps with the exception being the two constructs, either and all, which execute a group of statements with no predefined order of execution, in parallel. The all construct is equivalent to a parbegin block, in that all statements must finish for the execution of the block to finish. The either construct finishes whenever at least one statement of the either finishes. The all construct is primarily useful for expressing that a group of statements need not be evaluated in any particular order, while the either construct is useful for expressing computations where not all of the branches are required to finish (timeouts are particularly important examples of either). Sequencing among expressions to be evaluated on different nodes may be implemented by a request and positive acknowledgment mechanism, such that calling a procedure on a different node involves sending the request and then waiting for a response signifying completion and providing results, if any, at the calling node. If an error occurs, interfering with either the request, the invoked procedure, or the response, then no response will get to the calling node. Such an error can be detected by a timeout. When concurrent execution is introduced into a programming language (such as CLU), there are two possible ways of thinking about procedures (or operations of a data type). Since procedures in a von Neumann architecture are executed as a sequence of steps, we could view procedures as executing over a period of time, and unless otherwise prevented, all of the primitive operations ultimately composing the execution sequences of two concurrent procedure executions could execute in any arbitrary order. In this thesis, an alternative view is taken, viewing procedures as abstract "atomic" operations, whose internal steps are not interleaved with the execution of any procedure. The implementation of such procedures is one of the primary tasks of NAMOS. Either the traditional view of procedures or the alternative view taken by NAMOS degenerates into the same semantics, given a single execution point. What is missing in the NAMOS view is the ability to construct "sequencing control abstractions", such as a procedure that at intervals of 10 seconds increments its (by reference) parameter. Our thesis is that such sequencing control abstractions are best handled by a separate linguistic construct (perhaps called a subroutine?), leaving the procedure construct to build abstract operations. Manipulation of objects is done by operations, requested by transmitting a message to a node capable of executing the type manager to which the operation belongs. A natural way to build objects that captures the physical decentralization of the nodes is to define the idea of an object home. The object home is a node that contains the type manager for the particular type and the mapping from the object's name to the component objects that make up its state. Implementing an object on a single node ensures that all operations that deal with the object go to a single place to do so, so that one can queue the requests in some order. There are, however, other implementations of objects that do not require that all accesses to an object go through a common system. First of all, if an operation on an object does not change its state, but merely returns some function of its state, there is no inherent need to go to the home if a valid copy of the state of the object is obtainable at another node. Thus, copies of the object can be distributed by a kind of read-only encachement of the state of the object. The home is then needed only to make sure that operations that change the state of the object all go through the same place. There must be a means by which the consistency of an encached copy with the state of the object at its home can be guaranteed, however. Second, there is no absolute need for a fixed home location. Consider, for example, an object whose purpose is to behave like an integer set, for which there are only two operations -- append, which adds an integer to the set, and member, which tests to see if an element is in the set. The append operation need only send a message to any one of several sites that maintain subsets of the total set object, whose union represents the entire set. The member object sends messages to all of the sites containing subsets of the set, requesting each node to test to see if the integer is a member. If any node responds yes, then the member operation returns true, while no responses from all nodes indicates that the member operation should return false. Other distributed implementations of objects exist. Johnson and Thomas[Johnson75] have suggested a strategy by which cells that contain scalar values can be implemented in a distributed fashion. In chapter five, a distributed implementation of a special kind of "object" called a commit record, used to implement the possibility abstraction, is described. ## 3.2 Object Histories Common to the implementation of objects with fixed homes and the various ways of distributing implementations of objects is a fundamental requirement. Since an object has state, the results of one operation depend on the parameters to some set of other operations that are applied to the object. Normally, this dependency is derived from the time-ordering of operations applied to the object. In general, the effect of an operation may depend on all operations executed before the operation finishes execution. The fundamental requirement is that the implementation must execute the operations applied to the object in some order. With an implementation that defines a home node to be where all changes are made, ensuring that operations are applied in an order is trivial. However, consider an implementation of an integer cell that has two copies, each of which must be multiplied or added to independently. Then if site A tries to multiply the cell by 2, while site B attempts to add 4 to the cell, the messages to the two copies may arrive in opposite orders, giving different results. In this case, operations were applied to the cell object in no order (of course, the actions applied to the copies were ordered, but that doesn't necessarily lead to an ordering of the operations as a whole). If one were to try to read the value of the cell, one might get either answer, depending on the node that the read is attempted at. Thus a major function of any implementation of objects is to assign an ordering to the operations applied to each object. Perhaps the simplest way to assign an ordering is to use the order of arrival of requests at a home node as the order in which requests are processed on the object. As noted in the previous chapter, the arrival ordering of messages may be very hard to control in order to achieve any form of synchronization among objects with different homes. The possibility of unpredictable delay leads to lack of control of when requests will be executed, while the request uncertainty principle leads to the inability to stop a request once it has been requested. Traditional approaches to synchronization of operations on objects attempt to control the arrival ordering in order to achieve synchronization. The only control that is usually possible is to delay computations originating requests, so that there is only one request outstanding to an object at any one time, and only after that request is known to have been processed can another request be originated. Use of locks or semaphores provide the mechanism for deciding when a computation should be delayed because a request is already outstanding. This approach is quite indirect -- in order to perform an atomic action on a group of variables, one must ensure that any other computation that might want to access those variables is stopped. It is not necessary that the arrival ordering be the ordering used to process operations on an object. A strategy that gives the originator of requests more direct control of the order in which operations are performed would simplify the task of constructing programs that need to synchronize operations. To develop such a strategy, it is necessary to re-examine the concept of updating an object that has state. Traditionally, updates have been thought of as modifying objects. Another possibility, almost unexplored, is to think of an object as a sequence of the states it has assumed and will assume as the result of all updates. The updates, then, simply create a new element of the group, but do not involve any notion of modifying any one of the states. Similarly, reading an object specifies some element of the group. With this transformation of the v1ew of objects, synchronization mechanisms become ways to bind the references that occur at different times in a computation to particular elements of the group of states of an object. Thus the synchronization problem is transformed into a naming problem. This viewpoint (which I find extremely fruitful) has led rather directly to the approach for synchronization in distributed systems presented here, and seems to be a rather nice way to think about synchronization in the design of programs. To capture the notion of synchronization as naming, some concepts must be developed. An object can be thought of as a sequence of versions, the states that the object has assumed and will assume as the result of the computations that are applied to it. We will call this sequence the object history. It is a completely static picture of the object's behavior. Since the entire object history is not known until the system has finished execution, this is clearly a logical concept, rather than something that has a counterpart in the real system. Nonetheless, for the next few pages, we will suspend our practical judgement somewhat, and imagine that a program does execute in an environment where all the histories of all shared objects are known. Accessing an object requires a complete specification of which version is to be accessed (either read or created). The way to think about this is that objects have two part names consisting of an identification of the object itself combined with information that uniquely selects a version in the object history. There are two issues that must be considered in designing these two part names. First, how are they used in programs? The ways that programs can generate and use names influences very strongly the utility of this approach to synchronization. Second, what is the structure of the mapping from version selectors to versions within an object history? As we shall see, by carefully choosing this structure we can make it easy to define a notion of system global state that is not defined in terms of a snapshot of the distributed system at an instant of time. Since the entire history of the object is known, the idea of updating an object in this static view is somewhat strange. Each version of an object is the result of an update. Executing an update may be best thought of as checking to make sure that the update was preordained to occur by the "god" that set up the system history. Eventually we will modify our view so that the static history is only partially known, so we can view updates as filling in gaps in the already known part of the static history. ## 3.3 Kinds of references The model of the memory that holds shared objects is a mappmg from completely specified names, called version references, to versions. A version reference is a kind of value supported by the system. It is a two-part name composed of an object reference and a selector called a pseudo-time (for reasons to be explained later). The mapping from a version reference v=(o,p) to the proper version V is done in two stages. o is used to select an object history out of the memory. p selects a particular version from that object history. An object history is just a function from pseudo-times to versions. Conceptually, then, the shared memory of the system can be thought of as a hierarchy with two layers of selection, as in figure 4. Fig. 4. The entire structure of the memory represents the system's history for all time. The middle layer of nodes represent object histories. The leaf nodes represent versions of objects. The labels on the arcs represent object references (o 1, o2, and o3) and pseudo-times (pl, P2· and PJ). Object references, pseudo-times, and version references are all types of data values that can be used by programs. Object references correspond to the pointer or reference data type. Pseudo-times don't have an explicit counterpart in any programming language that I know of, but their function, that of selecting a particular state of an object to act upon, is normally provided by the execution ordering of programs (they are analogous to array selectors, but have a different purpose). A version reference corresponds to a single access through a pointer or reference -- again, not a concept explicitly available to the programmer in existing languages. Unlike pointers m ordinary languages, object references by themselves cannot be used for access to objects. Instead, a version reference is required to write or read a value in the memory. An object reference can, however, be combined with a pseudo-time to obtain a version reference. As we discuss later in the chapter, it is most convenient if the pseudo-time combined with an object is provided by an implicit mechanism we call a pseudo-temporal environment. Here we describe the operations that manipulate version references and object references using explicitly specified pseudo-times. Converting a program from the implicit use of pseudo-times to the explicit form shown here is done by a proc~ss of "desugaring" the syntax, replacing references to objects with code sequences that choose the pseudo-times to be used and then call on the appropriate functions to create version references that refer to the proper versions. The functions about to be defined can thus be thought of as "hidden under the covers" from the programmer's point of view. The only ways to use object references are as parameters to the following functions. In describing the implementation of these and succeeding functions, parameters are labeled by names indicating their type, so that or, orl, or2, etc. are object references, vr, vrl, vr2, etc. are version references, pt, ptl, pt2, etc. are pseudo-times, boolean is a boolean value, and value is some value of any type (integer, object reference, array of stacks, etc.). The result or results appear to the left of an assignment operation, and any error signals that can be generated appear in a list after the word "signals". The semantics of each operation is described in a few sentences following its parameter specifications. vr := version_ref$freeze (or, pt) This is a function that generates a version reference from an object reference and a pseudo-time. boolean := ob ject_ref$eq ( orl, or2) This is function that tells if two object references refer to the same object (in the sense of LISP's eq function or CLU's equal function). We can think of a version reference as referring to a particular value. There are three operations specific to version references. Explaining them is somewhat tricky, because of our static view of memory. Obviously in a real programming language that can be executed, we must make sure that a version actually exists before we can return its value. In this description, however, we take the omniscient viewpoint that the entire system history is laid out before us. Later in this chapter the actual behavior of these operations will become much more clear. version_ref$define( vr, value) signals(nonexistent_state, redefinition) This operation creates the version specified by the version reference. It is used in the desugaring of an update operation on an object. The second parameter is a value that will be the value of the version referred to by the version reference, if no error is signalled. The nonexistent_state error indicates that an attempt to assign a version that never will exist (no version of the object exists for that pseudo-time). The redefinition error indicates that there was already a valid version associated with the specified version reference. The version_ref$define operation can be applied at most once to a version reference. value := version_ref$lookup(vr) signals(nonexistent_state) This operation gets the version associated with a particular version reference. It is used in the desugaring of an operation that reads the value of an object. The nonexistent_state error indicates that the version reference specifies a state that will never have existed. or, pt := version_ref$decompose(vr) This operation is just the inverse of version_ref$freeze. In terms of the static system history, there are two ways in which we can think about the execution of version_ref$define. Since the system history is determined for all time, we can think of the version_ref$define operation as succeeding only when the version specified is the same as the one selected. Thus a failure of a version_ref$define operation implies that the version specified is already defined to be some other value created at an earlier pseudo-time. Conversely, each value change associated with an object requires that an execution of version_ref$define must have happened. Pseudo-times are ordered by a relation ~. The formula a~b is read "a precedes b". This relation is a total ordering, and in particular a~a (the relation is reflexive). We also a complementary relation, -+, "strictly precedes", such that (a~b)=--.(b-+a). We require that an object must exist (never signal nonexistent_state) for all pseudo-times between an initial pseudo-time of creation and some final pseudo-time of deletion. Thus for any object there is a time of creation tcreate• and a time of deletion tdelete· The nonexistent_state error is signalled if and only if the pseudo-time component, t, of the argument to version_ref$define or version_ref$lookup does not satisfy (tcreate~t~tdelete). The creation and deletion of objects is carried out by operations that specify the create and delete pseudo-times. or := object_ref$create(pt) This operation creates an object reference whose tcreate is specified by the parameter. object_ref$delete(or, pt) signals(bad_delete) This operation deletes the object specified by the first parameter, by setting the deletion pseudo-time to the second parameter. The signal bad_delete indicates the delete operation was not performed because the specified pseudo-time was inconsistent with the history of the object. This could be because the pseudo-time preceded the creation pseudo-time or because a version corresponding to that pseudo-time exists, or because the delete pseudo-time has already been set to another value. As in the version_ref$define operation, only one such operation may ever be applied to the particular object reference. More than one pseudo-time may refer to the same version. Essentially, if we think about all of the version_ref$define operations that correctly terminate when applied to a particular object, they can be totally ordered by the pseudo-time contained in their version reference parameters. Call the set of such pseudo-times U, the update history of the object. We can then say that if we have two lookups on the same object at different pseudo-times p1 and P2 that give different values, then there must be a p3EU such that (p3 -+ Pl)/\(PJ ~ P2). In simpler words, versions only change as the result of version_ref$define. Thus, for all pseudo-time.c; hetween the creation and deletion of an object, the object has a defined value. The definition of the value at any particular pseudo-time, t, is the result of a version_ref$define operation whose version reference contains a pseudo-time that precedes t. The concept of describing the state transitions of a system by considering the sequence of states assumed by a variable was introduced by Van Horn in his Ph.D. thesis[VanHorn66] in order to compare the various possible execution sequences of concmrent programs in proofs. NAMOS incorporates the history idea into the set of mechanisms actually used by programs, rather than being reserved for use in proofs about programs. ## 3.4 Pseudo-time and consistency Pseudo-time provides a very convenient way to define a consistent system state. \Ve say that a consistent state of the whole system is the set of all object versions referred to by version references containing a particular pseudo-time t. This leads to a different view of our memory model shown in figure 5. Here, the difference is that the first selection is on pseudo-time rather than on object. The pseudo-times can thus be thought of as state references, selecting consistent system states, from which object references can select the proper version of each object. Since pseudo-times are objects that are used by programs, they give a tool for programming that allows explicit recognition of consistent states within the program. In contrast, traditional synchronization mechanisms, such as semaphores, locking, monitors, send-receive, etc. do not give a tool for representing or naming consistent states -- one can deduce the states assumed by the system by timing relationships among the execution of steps of programs. A particular virtue of the model is that it requires that programs always generate version references to refer to objects. Thus programs that refer to shared objects must always be written with synchronization in mind. This has a positive effect, in that it may result in software that is less likely to fail when used in situations where unanticipated concurrency arises. A typical example of such a failure would be the use of text files implemented as segments in Multics. Such files can be concurrently accessed by several processes, for example by a text editor and a printer being used to print the file. If the user editing does not know of the concurrent use of the file by the printer, it is possible that what gets printed may see the file while it is being modified. In a system based on NAMOS, we could queue a specific version of the file to be printed, so that future versions would not be printed, or alternatively, as we shall see shortly, the editor could arrange that the sequence of changes to the file are not observable by other processes by ensuring that the changes are made in pseudo-times that cannot be referred to outside the editor. ## 3.5 Programs and Pseudo-time Since computations must always specify the pseudo-time in which shared objects are accessed, it is important that this specification not add a significant burden to the programmer's understanding of the program. One of the main arguments against the use of semaphores as a synchronization mechanism is that the use of semaphores (or other explicit locking techniques) just add to the complexity of specifying the algorithm the complexity of understanding the relationships between the data being accessed and the semaphores that must be set to prevent inconsistent results, along with the complexity of ensuring that deadlock does not occur and that an adequate degree of parallelism is achieved. We want to make sure that by explicitly including synchronization mechanisms in the language we don't add an enormous burden of complexity in the process. What locking normally is used for is to insure that during the execution of some steps of a program, a particular object only changes state as the result of the actions specified in those steps. Thus for those steps, the program need not concern itself with interactions with other concurrent programs that refer to the same object. Locking is also used to hide inconsistency that results during the process of attempting to make some coordinated change to a group of objects. For example, if two objects represent the state of bank balances, a transfer of money requires debiting one account and crediting the other. If these steps are taken separately, then it may be possible that an observer can observe the transient inconsistency that money has been either created or destroyed -- the sum of the balances isn't constant. Giving the program the ability to make references to several objects with the same pseudo-time is the key to obtaining consistency. Pseudo-time is quite unlike real time in this respect. It is quite impossible for a program to guarantee to be able to access several distinct objects that may be implemented quite remotely from each other at the same real time. Thus, for example, it would be possible to write the following program that accesses a consistent state of the system, adding up three objects to obtain their value. objl_vref := value_ref$freeze(objl_ref,ptime) ob j2_ vref := value_refSf reeze( ob j2_ref,ptime) obj3_vref := value_ref$freeze(obj3_ref,ptime) sum := value_ref$lookup(objl_vref) +value_ref$lookup(ob j2_ vref)+value_ref$lookup( ob j3_ vref) The state to be accessed is specified by the value of the variable ptime. The three references to the three objects are named obji_ref for particular i; these are used to generate three value references with corresponding names. One problem with the example program is that it is rather clumsy to have to specify explicitly which pseudo-time is to be used for each access to an object. It would be much nicer to be able to write something like: sum := objl + obj2 + obj3 where the default is that objl, obj2, and obj3 are to be referred to with the same pseudo-time. Convenience thus leads to the development of the idea of a contextual mechanism for specifying the pseudo-times needed to resolve references to objects. The contextual mechanism is a pseudo-temporal environment. The pseudo-temporal environment provides a mechanism whereby a program can ensure that the objects it refers to change only as a result of actions requested as steps in the program. Thus, we can write a rather ordinary sequence of program steps that refer to shared objects, reading and modifying them, and when executed in a particular pseudo-temporal environment, the sequence of steps will have the same effect on the state of the shared objects as they would have on non-shared objects. However, we must be careful not to write any object twice with the same pseudo-time. It is quite convenient to be able to write programs that include multiple modifications to the same object -- at least because of the need for loops. So, for example, we might want to execute the following in a pseudo-temporal environment and gain the advantage of having exclusive control of the objects during the statements. aO := dequeue(queue) enqueue(queue, al) enqueue(queue, a2) a3 := dequeue(queue) % get what is in the queue. % put a 1 in queue % put a2 in queue % take out whatever is in the queue % (perhaps al) It is clear that the intent here is to make four references to the queue object queue. On careful thought, two of the four references are reads followed by writes (dequeue), and two are writes. To execute this properly, we must refer to five distinct states of the queue object, the initial state and the state resulting from each of the four queue modifications. If we want to make this sequence of four steps an atomic operation, so that the states in between the initial and final states are invisible outside the operation, we must prevent any other program from interfering with the queue during the execution of the operation. To say that no other program can interfere with the queue during the execution of the program means that the pseudo-temporal environment must provide a means to reserve a range of pseudo-times for exclusive use of the program, so that no other executing program can access the queue object in that range of pseudo-times. We may imagine a pseudo-temporal environment as the generator of a sequence of pseudo-time values to be used in the execution of those program steps executed within its context. We must insure that in the sequential program above, each version_ref$define applied to a version of the queue object is applied at a different pseudo-time, and that they are ordered in a corresponding order to the order of the statements. In addition, the version_ref$lookup operations must be applied in pseudo-times that fall in the right place in that ordering. In the way pseudo-temporal environments are generated and manipulated, one hopes to capture a modular notion of program construction. When the queue operation above is constructed, compiled, and executed, the programmer or user may not be able to provide any information about how many, if any, version_ref$define operations the enqueue or dequeue operations actually carry out when invoked. Thus, the actual execution will involve executing the enqueue operation's implementation in a subrange of the pseudo-times contained in the program's pseudo-temporal environment. We can think of the structure of the pseudo-times as being hierarchical. The set of all pseudo-times, n, is broken up into subranges that begin and end in pseudo-times that are system-wide consistent states. One of these subranges that corresponds to the execution of a sequential program is further broken up into subranges that begin and end in pseudo-times that correspond to the states in between execution of operations that are separate modules. We can call all of these ranges (at all levels) pseudo-temporal environments. n is the "root" pseudo-temporal environment. Thus we have the following operation that defines pseudo-temporal environments as subranges of other pseudo-temporal environments. In defining this operation, a new ordering relation is introduced. Two pseudo-temporal environments x and y are ordered if and only if all the pseudo-times in the range of x precede all of the pseudo-times in the range of y. This partial ordering is symbolized by the notation .-..; the formula x-y may be read as "x strictly precedes y." This notation is also extended to the case where either x or y is a pseudo-time. pte2 := pte$transaction(pte 1) The pseudo-temporal environment pte2 is a subrange of ptel. It is guaranteed that the result of two separate invocations of pte$transaction on the same pte will be two pte's x and y such that x.-..y or y-x. That is, x and y are non-overlapping subranges. Further, after executing w:=pte$transaction(z), w is a subset of z. pte$transaction can be applied repeatedly, in order to generate subranges of subranges. Pseudo-temporal environments are then used to provide pseudo-times for version references used implicitly in computations. There are two ways to get pseudo-times from a pseudo-temporal environment. If one is needed for a version_ref$lookup operation, there is no need to get one that differs from the one last used for a version_ref$define operation. If one is needed for a version_ref$define operation, it must be strictly later than any one used previously to define a version of the object. We ensure that by saying that the pseudo-time used for a version_ref$define operation is later than the pseudo-time used for the last version_ref$define or version_ref$lookup in the same pseudo-temporal environment. Two operations are thus used to select the next pseudo-time to be used in a program. The first, pte$current is used only for desugaring reads into version_ref$lookup operations, and the second, pte$next is used only for desugaring updates into version_ref$define operations. pseudo-time := pte$current(pte) If X is the set of pseudo-times returned by pte$next(y) operations or contained in pseudo-temporal environments generated by pte$transaction(y) operations executed before a:=pte$current(y) is executed, then for all xEX, x=>a. pseudo-time := pte$next(pte) If X is the set of pseudo-times returned by pte$next(y) operations or contained in pseudo-temporal environments generated by pte$transaction(y) operations executed before a:=pte$next(y), then for all xeX, a-+x. Now we can give a procedure for desugaring a program that executes in a particular pseudo-temporal environment p, in order to convert from implicit use of a pseudo-temporal environment to determine the pseudo-time used for each reference to explicit code that selects a pseudo-time for each reference. \Ve must have a notation to indicate that a particular pseudo-temporal environment is to be used to control the execution of a statement and any operations invoked in that statement. This will be the in statement: in pte do statements end where pte is some pseudo-temporal environment, and statements is a sequence of statements. To execute the in statement means to execute the statements in its body, resolving object references to shared objects through pte. Basically, what we do is to change every object reference used to read a value from x to version_ref$lookup(version_ref$freeze(x,pte$current(pte))), every assignment to a shared object reference x:=y to version_ref$define(version_refSfreeze(x,pte$next(pte)),y), and any invocation of a separate module m(params) to m(params,pte$transaction(pte)). In order to handle separately defined modules, such modules always get an implicit parameter that specifies the pte in which they are to execute. The entire text of a module is implicitly contained in an in statement that specifies the pseudo-temporal environment 1': "E'd as parameter. In this desugaring of programs, it IS important to remember that pseudo-temporal environments and pseudo-times are not shared objects. They are merely objects local to the interpreter of the program (as is the instruction counter, for example). As a brief example, the desugaring of the following program that sets the cell c to the sum of w and b, then calls a module d which divides the cell w by c, example = proc(w,b,c) d = proc(x,y) x:=x/y; end d c:=w+b; d(w,c); end example is (using the dummy variable p to hold pseudo-times and dummies ti to hold pseudo-times to clarify order of evaluation): example = proc(w,b,c,p) d = proc(x,y,q) t4 :=pte$curren t( q); t5:=pte$current(q); t6:=pte$next(q); version_ref$define( version_ref$f reeze{x, t6), version_ref$look up( version_ref$f reeze(x, t4)) I version_ref$look up{ version_ref$f reeze(y, t5))) end d; t 1 :=pte$current(p ); t2 :=pte$current{p ); t 3:=pte$next(p); version_ref$define( version_ref$f reeze( c, t 3), version_ref$look up{ version_ref$f reeze( w, t 1)) + version_ref$look up( version_ref$f reeze(b, t2)) ); d( w ,c,pte$transaction{p) ); end example; When this program is executed, t 1 ::)t2, t2-+t3, tr•q, t 3-+t4::)t5, and t5-+t6. Given these relations among pseudo-times of reference, it is easy to show, given the memory model that the program has the effect of setting w on output to w /(w+b), and c on output to w+b. An important part of showing this is knowing that the only version_ref$define operations that might change w, b, or c are those executed with verswn references derived from the pseudo-temporal environment used in calling example. Since example is a module, by convention it is invoked with a pseudo-temporal environment that is a subrange of its caller's pseudo-temporal environment. The traditional interpretation of procedures would allow any parallel computation to modify the shared cell object w in the example above between any of its references in the program. So in addition to the functional effect the procedure would have were there no parallelism and sharing, there are many other possible behaviors the procedure could have on the state of the objects it refers to when executed. For example, if w is changed between the two statements of the outer procedure, almost any possible value could wind up in w, depending on the change made to w. In the interpretation of the program that is assigned by NAMOS, only the functional behavior, equivalent to dividing w by the sum of w's initial value and b and assigning to c the sum of w's initial value and b, can result from the execution of the example procedure. ## 3.6 Programs with internal parallelism Not all programs are sequential. In fact in a decentralized system, doing remote operations sequentially (i.e. waiting for node A to finish its operation before starting the next operation, which is to be done at node B) may result in unnecessary and unsatisfactory delay -- thus writing parallel programs is encouraged. Although the pseudo-temporal environment concept is primarily intended for handling unanticipated interactions between computations run in parallel because they were designed and requested independently, the concept can also be quite useful in managing the interactions on shared objects resulting from designed-in parallelism. Two ways to create parallel computations are the either compound statement, which creates a set of parallel executions, one for each statement, and terminates whenever one or more of the executions terminate, and the all compound statement, which creates a set of parallel executions of the statements that terminates only when all of the parallel executions terminate. Termination conditions are important once we start discussing the interactions of failure with the synchronization mechanism. In order to capture the essence of parallel execution, we have to extend the pseudo-temporal environment concept somewhat. It would be somewhat difficult to define the order of evaluation of pte$next operations in desugaring a parallel compound statement. By the definition of either and all, all of the actions on shared objects caused by the compound statement should deal with versions later in pseudo-time than those accessed by statements sequentially preceding the compound statement. Similarly, all of the actions following the compound statement must deal with versions later in pseudo-time than any dealt with by actions generated by the compound statement. The individual parallel branches are designed knowing that they are executing in parallel with other computations. They must therefore specify explicitly within themselves how their accesses to shared objects are to be synchronized (it may be the case that no shared objects are accessed, in which case they need not be synchronized at all). This they will accomplish by using pseudo-temporal environments constructed by the pte$transaction operation. But in order to ensure that we don't have to think about how the pseudo-temporal environment is manipulated by concurrent pte$transaction operations, etc., we invent an operation that constructs parallel streams of pseudo-time. ptel, pte2, ... := pte$paraction(pte0) pte$paraction returns multiple values. The values returned are parallel streams of pseudo-time. If we execute a,b,c,d:=pte$paraction(e), the set X=aubucud is a subrange of e that is ordered with respect to all other subranges of e generated by pte$transaction(e) or pte$paraction(e). X is also ordered with respect to pseudo-times generated by pte$next(e) and pte$current(e). Further, to capture the notion of parallel execution, anb=¢ as do the intersections of any other pair of results. Finally, if f:=pteStransaction(a) and g:=pte$transaction(b) are executed, then f and g are non-overlapping: f "'g or g"'f. Thus f gives exclusive access with respect to the other environments. Desugaring a parallel compound statement then just consists of preceding the compound statement with a pte$paraction{p) where p is the current environment, to produce as many results as there are parallel actions. Then each branch of execution is surrounded by an implicit in specifying the result of the pte$paraction corresponding to that branch. We can also use the tool given by pte$paraction to specify the parallelism inherent in independent execution. Each user of the system can be thought of as executing by default in a pseudo-temporal environment that was initially created by an initial single execution of pte$paraction(n). Thus all independently initiated computations execute in fully parallel streams of pseudo-time in which transactions are guaranteed to be ordered with respect to transactions that happen in other streams. 3. 7 But we can't know the entire history! Now is the time to answer the question posed by our static view of system history. Pseudo-times have been shown to provide a nice way to think about the synchronization relationships among computations in the system. However, we have been assuming that any computation can reach out and get hold of or assign to an object version at any time. Clearly, if the execution of the the system is to be physically realizable, versions must be defined before they are used. It is not really very difficult to ensure that a version is defined before it is used. The realization of a version_ref$lookup operation is simply to wait until the version is defined. Because certain versions may not be defined at a particular real-time instant leads us to define the concept of a known history. The known history of an object at any instant of real time consists of the mapping between version references and versions that has been defined so far. Thus the known history of an object at any time is a subset of the object history. More importantly, as real time passes, more and more of the object history is contained in the known history. Thus at two different real times, the known history corresponding to the earlier time is a subset of the known history at a later time. The known history changes as computations are executed in real time by a process called eduction (from the verb educe, meaning "to draw out, to elicit"). The eduction of a known history just consists of creating new versions and extending the range of pseudo-times that an already created version belongs to. There are two ways in which a known history is educed. First, a version_ref$define operation for a version reference not yet defined in the known history may be executed successfully. This results in creating the version associated with th referred to was valid previously extended only to u. Fig. 7. Eduction by lookup of existing version Pseudo-time Both kinds of eduction interact strongly with the failure management mechanism to be discussed shortly. Thus, I have been a little imprecise in the previous paragraph, but the imprecision will be corrected later. Another fact of the real world is that maintaining the known history of an object would require the system to provide an ever increasing amount of memory as time goes on. Thus we would like to allow the system to maintain only a subset of the known history of each object. Consequently, a version_refSiookup or version_ref$define operation corresponding to a region of pseudo-time for which the known history has been decided, but which is not maintained in the system at the time of the operation must be rejected for a new reason, unavailability. This rejection is signalled as the condition forgotten_state by those two operations. In chapter six, we consider further the mechanism for choosing the subset of versions to be maintained. However, the most important requirement is that the "current" version of an object always be maintained (the one whose pseudo-time is the greatest within the known history). ## 3.8 Generating pseudo-times and pseudo-temporal environments Pseudo-times have been shown to provide a relationship among the histories of system objects. In a real system, however, it would also be useful to relate the system history to the history of the system's interactions with the real world. So far, we have not made any assumption at all about the relationship between the rate of increase of pseudo-times in independent, concurrent processes. We have .. shown only that pseudo-time increases or stays the same within a single process, as a result of executing steps of that process. The simplest way to relate the pseudo-times in concurrently executing processes is to create a correspondence between the pseudo-times used and real time. To understand the anomalous behavior that can result from not relating the pseudo-times to real time, imagine a system containing the data bases of a bank, allowing transactions that deposit, withdraw, and transfer money between bank accounts. When people step up to bank terminals, they invoke a transaction, which is executed in a pseudo-temporal environment whose output state is chosen at random. If we then construct a system history in which each transaction is executed, it will be, as I have pointed out, a serial schedule, and thus presumably will give correct results. But imagine the quandary of an individual customer. On Thursday May 25, 1978, he opens an account, depositing fifty dollars in cash ( his transaction is executed in pseudo-times between 3276800 and 3276805). On Friday, he wants to withdraw ten dollars, so he requests a withdrawal (run as a transaction that reads the account at pseudo-time 151970), getting the response "no such account!" The problem is obvious. Pseudo-time must be correlated with real time. First of all, the pseudo-times used for operations must be non-decreasing from the point of view of any user in the system. Further, since users can talk to one another outside the system about their interactions with the system, whenever two users are sure that a pair of interactions with the system were not simultaneous, the pseudo-times used in the interactions to specify output states must be ordered in correspondence with the real-time ordering. Lamport[Lamport78] has already observed this problem. The system must assume that if two interactions with the system are not close together in time, then they must be executed in the order that users will expect. In order to generate values that are ordered in correspondence with real time, one must have at each node a way of creating a pseudo-time value that exceeds all previous values created at that node. The pseudo-time value created must also exceed all values created at other nodes at significantly earlier times. In chapter six, I will discuss how the correlation with real-time is easily achieved by usmg approximately synchronized clocks. ## 3.9 Failures and Recovery In executing any real computation interacting with shared objects. failures must be expected. As noted in chapter two, the failures we are concerned about can all be modeled as failures to complete a requested action or group of actions. Thus, a program being executed may stop due to a crash of its associated processor, a requested operation may be rejected as inconsistent with the definition of the object (popping an empty stack, for example), a communications link needed to request a remote action may fail, preventing the action. Other occurrences that can be modeled as failures to complete a requested action are protection exceptions that result from a change in the requesting program's access rights to an object, rejection of a version_ref$define operation because the object referred to has already been defined for the specified pseudo-time, and rejection of version_ref$lookup or version_ref$define operations due to the forgotten_state signal, resulting from deletion of out-of-date versions. We would like to provide a basic mechanism to handle this kind of failure. None of these failures are preventable, so it is important that the mechanism be de&igned to handle such failures gracefully wherever they occur. Similarly, none of these failures can be expected to happen at "nice" places during the execution of a program. For example, if a program refers to an object several times in succession (as in the queue example), there is no guarantee that just because the first access succeeded, later accesses will also succeed. Further, once such a failure has occurred, it may be impossible for the program to take corrective action by undoing changes it has made -- if the node containing the program fails it certainly won't undo its changes, and if the protection status of an object, or the hardware communications leading to the object have failed, undoing the changes may be very likely impossible. The primary problem of failure management is that meaningful operations on shared objects are constructed out of multiple operations at a lower level. Usually when executing a meaningful operation (such as a transaction), if some one of the component operations fails, the result will be some sort of inconsistency that may not be tolerable, because the level of abstraction at the operation's interface is compromised. For example, if in a bank transfer of funds from one account to another, if one account is incremented while another is decremented, and either the increment or the decrement fails, the bank will either lose track of some money or gain some money. This leads to the need to be able to manage groups of updates that must either be all done together or not be done at all. Because it unlikely that a set of changes can explicitly by undone in response to a failure, we would like the system to behave as if they were never done if in fact a failure occurs. This means that there must be a mechanism for creating tentative changes in the state of objects that cannot be observed outside the computation making the changes, such that within the computation making the changes, those changes will be observable. We can solve the problem again by taking the omniscient viewpoint. 'Vhat a program wants to know when it is about to do an assignment to an object is whether the group of assignments to which it belongs will properly finish, or whether some one of the assignments will fail. If we could send signals backwards in time, there would be no problem, since before the operation was begun, it could query the future about whether the operation will be allowed to complete. Then the operation would simply halt immediately with no effect if it were about to run into some kind of failure. In fact, sending signals backwards in time is not needed. Instead, we use an old magician's trick for predicting the future. A magician produces a sealed envelope for inspection. He claims that written on the piece of paper inside is the name of the playing card you will pick. You carefully make sure that the envelope is sealed, by gluing one of about a hundred or so different postage stamps across the flap. Then the magician holds the envelope while you shuffle the deck and pick your card -- the Joker. You then take the envelope from the magician and unseal it. Inside, the paper says "Joker." Amazing! Not really. Look at the envelope closely. There is an imprint in the paper of the front side that says "joker" as well. Look in the magician's hand. There is a small metal stylus taped to his right index finger. Inspect the paper from the envelope. Sure enough, it is carbonless copy paper that turns dark when pressed with a stylus. The magician's trick becomes clear. He merely waited for you to pick your card, then inscribed the name of the card on the envelope with a stylus, causing the paper inside to contain the name. He may be well schooled at writing m concealment with one finger, a noble accomplishment, but he hasn't predicted the future. The essence of the trick lies in the envelope, because it prevented you from verifying that there was in fact the name of a card written on the paper. Given that you believed that something was written on the paper that you could look at any time you wanted to, you had to conclude that the magician knew in advance the card you would pick. But the magician knew that he could force you not to look at the paper until after you picked the card by placing it in an envelope. We can use a similar trick to implement the kind of "backward" signalling m time that we want. We define a special kind of envelope called a possibility, that is defined to contain a piece of paper that either has an X written on it or nothing written on it. One of these envelopes is associated with each group of updates that is to be performed. We are told that the group of updates will all be executed without failure if there is an X on the piece of paper, but if the paper is blank, then none of the updates is to be executed. In fact, the system holds the envelope. But instead of executing the updates by actually making the assignments, the system makes a note at each object where an update is attempted that says, in effect, "If there is an X on the paper, the value is . Otherwise, the value is ." Actually the paper was created blank, but when we tell the system that all our updates are done, it inscribes an X on the paper, and says, "see what I mean, I knew you would be done." If you ask to see the paper before all the updates are done, the system opens up the envelope and says, "see, you aren't done." Once the system opens the envelope the paper inside cannot be changed, and any further updates are refused by the system, saying, "I'm sorry, I just can't do that update for you." We represent the envelopes by entities within the system called possibilities. A possibility contains a boolean value (corresponding to the mark, or lack of it). This value is explicitly set to true when the associated set of updates complete. In the possibility mechanism, we also include a timeout, after which the possibilities value cannot be set to true. By including a timeout, we allow the system to bound the time that a group of updates may be in progress. Also, since prematurely opening the envelope aborts the group of updates by necessity, the timeout specifies a time before it is probably not a good idea to open the envelope. Looked at in real time, there are three important states of a possibility. Before its value is decided, it is in the wait state, so named because an attempt to test the value will be forced to wait (at most until the timeout is past). If it is successfully set to true, it enters the complete state, so named because the group of changes made under it have been completed. If it is explicitly set to false or if the timeout is passed without it being set to true, it is in the aborted state. The operations defining the possibility entity are as follows. The variable possi stands for some possibility, and time stands for some real time. possi := possibility$create( time) The possibility is created with timeout equal to the parameter, and put in the wait state. boolean := possibilityScomplete(possi) The possibility parameter is put in the complete state, unless it is already in the aborted state. The result is true if the possibility is either already complete, or is set complete. boolean := possibilitySabort(possi) The possibility parameter is put in the aborted state, unless it is already in the complete state. The result is true if the possibility is either already aborted, or has been set aborted. 1 boolean := possibilityStest(possi) The possibility parameter is tested to see if it is complete or aborted. If it is in the wait state, the operation does not return until the possibility is either complete or aborted. The result is true if the possibility parameter is complete, otherwise the result is false. 1. The abort operation is logically unnecessary, since a possibility will eventually enter the abort state after a timeout anyway. However, delay may be significantly reduced for operations that do lookups dependent on testing the possibility if the possibility is aborted as early as possible. As with pseudo-temporal environments, it is eas1er to treat possibilities as implicit parameters to operations, rather than passing explicit parameters everywhere. Consequently, we need a statement that binds the possibility to be used in all· computations initiated by the enclosed statement. For this, we have the were statement. were possibility do statements end The were statement binds the possibility parameters to all operations executed within the body to the specified possibility. All calls on modules are furnished with an extra parameter that is implicitly set by use of this possibility. After completion of operations run under a particular possibility, a program must complete the possibility in order to make the results of the computation available to other computations. The same possibility can be used in several were statements before executing a possibility$complete on it, although such usage seems unlikely to be common practice. We have to modify the version_refSlookup and version_refSdefine operations to explicitly represent the tentative nature of the version_refSdefine operation. Both operations now have an added parameter, a possibility. When the version_ref$define operation is executed, a reference to the possibility is associated with the tentative version being stored. Such tentative versions are called tokens because of their use as place holders in the known history. A related concept, that of a write-once cell called a "token," has been described by Henderson[Henderson75]. 1 One can think of a modifiable object's versions as a grouping together of many of Henderson's tokens that each represent an individual state of the object. A token in NAMOS thus defines a potential state of an object. Once the state of the possibility associated with the token becomes known to be true (complete), the token becomes a version. Since the eventual state of the possibility is unknown, though, any attempt to access the object in a pseudo-time for which the token might eventually represent a valid version must be forced to wait until the state of the possibility is determined. 1. Except where explicitly specified otherwise, the word token m this thesis refers to the tentative versions, not to Henderson's tokens. There is a problem, however, because a computation that creates a token may need to access that value later before the state of the possibility becomes set. Consider our queue example above. Suppose that all of the queue operations are executed in the same possibility. After the first queue operation the queue's state will be represented in terms of one or more tokens. The second queue operation should not be forced to wait until the state of the possibility is determined, because only after the fourth operation is completed will the possibilityScomplete operation be applied. The problem 1s resolved by supplying a possibility parameter to version_refSlookup. If this possibility parameter matches the one under which the token was created, then the token may be returned as the version requested. In this case, the range of validity in pseudo-time is extended just as if the token were a normal version. Thus the following redefinitions apply: value := version_ref$lookup(vr, possi) version_ref$define( vr, value, possi) For any particular object, imagine that we can examme the entire set of version_ref$define operations ever applied to it, such that no error signal was made. Then the subset of version_ref$define operations whose possibilities are (eventually) true is the update history, defining the mapping from version reference to version for all time. However, the results of version_ref$lookup must be defined in terms of the entire set, whether the possibilities are true or not. Add to the subset whose possibilities are true the set of version_refSdefine operations that have possibility parameters that match the possibility parameter to the version_ref$lookup operation, to get a new set. Then the result of the lookup operation is that version assigned by the version_ref$define operation whose pseudo-time is the largest pseudo-time not exceeding the pseudo-time of the lookup. Figure 8 shows how a known history for an object looks, showing tokens and possibilities. Fig. 8. Known History with Tokens and Possibilities Pseudo-time In figure 8, possibilities are shown as circles, where the letter W, C, or A indicates whether the possibility is in the wait complete or aborted state. The value B is thus a token, because it refers to a possibility in the wait state, while the values A and C in the figure are versions. A version_ref$lookup operation whose version refs pseudo-time is between p and s might have one of several results. If the possibility parameter to the version_ref$lookup operation is the same as the possibility associated with token B, then B will be returned, whether or not B ever becomes a version. On the other hand, if the possibility parameter to the version_ref$lookup operation is not the same, then the lookup must wait until the possibility leaves the wait state. Then either B will be returned as the result if the possibility is complete, or A will be returned if the possibility is aborted. ## 3.10 Recoverability Possibilities allow the construction of recorerable computations. The concept of recoverability was named by Gray[Gray77], although the idea has been kicking around m data base circles for a long time apparently[Davies73,Lampson76]. In this work, a useful concept is the reco.-·erable update set. A recoverable update set is a set of changes to objects that is either made entirely, or never made at all, from the point of view of any computation observing the objects changed in the update set. All of the changes made under the control of a particular possibility form a recoverable update set, since any computations viewing the objects will either never see the changes (if the possibility is aborted), or will see all of the changes eventually (if the possibility is completed). If an operation makes all of its changes under the same possibility, it has particularly nice properties. In particular, if the operation finishes, it can be either totally aborted or completed, but there is no halfway state in which it can leave its changes. If the operation does not finish (e.g., because its node crashed), it can be aborted. Such an operation I call a recoverable operation. Not all operations are recoverable, nor should they be. In chapter four, I will discuss uses for operations that are partially recoverable. An atomic transaction has the property that it either happens completely, or not at all, as well as the property that when it executes no other operation can see or change the states of shared objects that it accesses. With the were statement one can construct an atomic transaction. The simple form of an atomic transaction is: in pte$transaction() do possi:=possibility(timeout); were possi do statements end possibility$complete(poss1) end If the statement does not contain any embedded m or were statements, then it will be executed as an atomic transaction. ## 3.11 Modularity and possibilities So far, we have not dealt with the problems of modularity in handling failures. A very common kind of problem that will occur is that a module executing at a remote site may fail in the middle of execution, leaving its changes half made. If the module's implementation is unknown to its users, it would be very unwise to allow the users to be able to complete the possibility that would enable its changes to become visible. A module must thus be able to locally ensure that the updates it makes locally are completed all at once or not at all. Failures of this kind lead to a need for a kind of self-protection at the interfaces to operations. For example, consider that a bank may want to offer an interface to transfer money between bank account objects. To protect itself against losing or gaining money, it would like to make this operation an atomic transaction. Similarly, a user of the bank system (some bank customer) who also makes use of an independently programmed checkbook recording system will want to have an operation built using the two systems that transfers money between his checking and savings account, recording the fact in his checkbook records. Both the bank and the user want to assure recoverability, but the bank cannot completely trust the user to properly abort the bank transaction upon failure. If the failure in the bank transaction is a failure in the middle, leaving only one account changed, the user may choose to complete his possibility anyway, such that the bank transaction is completed even though only one of the accounts has been changed to reflect the transfer. The user, on the other hand, does not wish the bank to proceed with the transaction unless his personal checkbook balance is also updated. Consequently, the agreement of both the user and the bank that the transaction is to be completed is required. Again, the problem IS that we would like to use modules in the construction of still larger modules, while preserving the level of abstraction provided by the lower level module interfaces. The designer of an operation, whether or not the module is to be used as a top-level module or many layers of modules down, would like to assume that the operation is recoverable (it is either completed or is not), in order to assure that the interface has simple semantics. An operation defined by a module has very simple semantics if it is, as a whole, recoverable (it either finishes correctly, or does nothing). However, operations are built out of smaller operations that also should be recoverable. If the smaller operations are designed without knowledge of their use, they cannot assume that their users will assist in ensuring recoverability. On the other hand, the smaller operations cannot make the decision to complete without the consent of the user operations. By adding some power to possibilities, the problem of modularity in usmg possibilities as a failure recovery mechanism can be solved. The idea is to have the user create a possibility that controls the overall completion/aborting of the operation. The bank and the checkbook system each create a possibility specific to its own part of the operation. The bank and checkbook possibilities each depend on the user's possibility in the following way. If the bank's possibility is waiting or aborted either by timeout or abort operation, the user cannot make versions out of tokens created by the transfer operation by completing the user's possibility. If the bank's possibility is complete, then whether the new account changes become versions or not is wholly dependent on the user's possibility. The mechanism added is a kind of possibility called a dependent possibility. Dependent possibilities are created by the possibilitySdependent operation: possi 1 := possibilitySdependent(possi2, timeout) The result of the operation is a possibility that depends on possi2. The result, possil, enters the complete state if and only if the possibility parameter is completed and possibility$complete is applied to the result (normally, possibility$complete is invoked on the resulting dependent possibility before the parameter possibility 1s completed). If the timeout elapses, possibility$abort 1s applied to the result, or the parameter possibility is aborted, then the value of the dependent possibility 1s false. The bank example can then be built by having the bank construct a dependent possibility that depends on the one used to ensure recoverability of the whole action. In general, modules that interact with multiple shared objects will construct dependent possibilities that are used to control the entire group of actions. The introduction of dependent possibilities reqmres a small fix to version_ref$lookup. The problem is easily seen in the queue example. If the queue operations are each executed in dependent possibilities that depend on the possibility that reigns over the whole program, then we have to be careful to define how successive queue operations see the result of previous operations. Once possibility$complete has been applied to the dependent possibility created for the first queue operation, the state of the queue l'hould be made available to a queue operation that is applied within the overall (not yet completed) possibility. Within this other queue operation, a new dependent possibility that depends on the overall possibility is what is passed as parameter to the version_refSlookup operation. The way the problem is handled is by properly defining what it means to have two possibilities match. Call the possibility that a dependent possibility depends on its parent possibility. For a particular token, the possibility that must be matched is found by following the parent chain from the possibility used in creation of the token until the first possibility is found that has not had possibility$complete applied to it. If this possibility, the match possibility of the token, is the same as any possibility in the parent chain of the possibility parameter to version_refSlookup, then the token can be returned as the value. Otherwise, the lookup must wait until possibility$complete is applied to the match possibility, and then the match is reattempted. (Note: if in searching the token's chain of possibilities, an aborted possibility is found, then the token is ignored for the purposes of the lookup, as before). ## 3.12 Known Histories Revisited In figure 9, the pictorial notation for a known history is extended to show dependent possibilities. Dependent possibilities are shown as circles, with a further link to the possibility upon which they depend. The letter inside a dependent possibility is either W (indicating that no complete, abort or timeout has yet occurred to the dependent possibility), C (indicating that a complete has been applied before the timeout), or A (indicating that either a timeout or abort has occurred at the dependent possibility). The actual state of the dependent possibility can be determined by looking at the chain of possibilities upon which it depends. If any possibility in the chain is marked A, the dependent possibility is aborted. Otherwise, if any are still marked W, the state is wait, else the state is complete if all are marked C. In figure 9, version A was created in a dependent possibility, and that possibility was successfully completed. Similarly, version C was created within an independent possibility that \vas completed. Token B is created within a dependent possibility, and so far, both that possibility and its parent are not yet either complete or aborted. Fig. 9. Object Known History Pseudo-time ## 3.13 Summary In this chapter, I have described the user's and application programmer's vtew of the system mechanisms for synchronization, error recovery, and building composite operations. Pseudo-time, object histories, and computations that are recoverable are the basic ideas. These ideas are represented concretely in terms of pseudo-temporal environments, possibilities, and the known history of objects. The notion of an operation and its important special case, the transaction, have been described in terms of these concepts. The construction of modular interfaces has been very important in the design. The concept of a dependent possibility and the hierarchy of pseudo-temporal environments allow the construction of modules whose internal implementation is not visible outside the interface, even should an unanticipated failure occur within the module or should some other operation interacting with shared objects used by the module be executing concurrently. # Chapter Four: Using the Mechanisms In the previous chapter, a number of language features and mechanisms to be used for synchronization of access to data have been described. Although some examples were given there, I have not really shown how these facilities can be used to handle synchronization problems. In this chapter, I will develop some examples that show how the language facilities can be used for various kinds of problems. First, I will discuss the well known problem of controlling database transactions. A simple example of a bank with distributed accounts is implemented with the tools that NAMOS provides, to allow the creation of account transfer transactions and statistics gathering transactions. An important point made by the example is that arbitrary transactions can be constructed and run at any time. Next, I will contrast the solution using my techniques with the solutions possible with locking mechanisms, and the kinds of solutions that are possible by use of synchronizing processes such as Hewitt's serializers. Both of these alternative approaches require both design-time planning to decide the class of transactions that may be run and careful discipline to ensure that the accesses made during transactions are properly synchronized. The next problem discussed is the problem of user mistakes or failure resulting in irrecoverable loss of data. The idea of a consistent state defined by a particular value of pseudo-time allows easy definition of a backup mechanism. The backup mechanism provides the capability of restoring the states of a set of objects from some earlier consistent state of the system. The problem of discovering what set of objects to restore to an earlier state is discussed, but no general mechanism is suggested to solve the general state restoration problem. The problem of conversational transactions is then discussed, and is shown to be one of the problems best solved with a partially recoverable operation. Other problems, such as keeping metering information or "memoizing" (remembering in a cache the result of a hard-to-compute function of a particular set of arguments), are also shown to be cases where total recoverability IS not appropriate, but partial recoverability is very useful. ## 4.1 Transactions Perhaps the most basic and important synchronization problem is the achievement of multi-site transactions. The reason for the importance of such transactions is that they provide a convenient approach to defining the consistency of a database in the face of failures. Further, transactions are easy to design, since the programmer need not worry about the problems of synchronization of his transaction with others that manipulate the same database. A transaction, according to Gray[Gray77), is a program that when run takes a consistent state of the system into a new consistent state. In other words, if a transaction is started with data that is consistent, the changes the transaction makes will leave the data consistent. During the transaction, after only some of the changes have been made, the data in the system may not satisfy any consistency requirements. Thus, running a transaction requires that: 1) The data referred to by a transaction all be from one consistent state. 2) Other computations that wish to see a consistent state be prevented from seeing the intermediate states of the system caused during the transaction. 3) Since a new state is built from a previous state by selectively changing some objects, but leaving most objects the same, the unchanged objects in the state containing the input data must still be the same in the final state constructed by the transaction. Gray's definition of transaction is not complete. It only deals with what I call internal consistency -- consistency among the objects within the system. Another aspect of transactions is that they have a notion of external consistency - consistency between the system as a black box and the history of inputs and outputs of the system. Imagine that upon completion of a transaction, the transaction printed out some date and time to indicate when the transaction was actually executed. It is useful to require that this date and time corresponds to some time between the initiation and completion of the transaction. Then the system will be externally consistent if it behaves as if the transactions executed were actually executed one at a time in the order indicated by their date and time values. ## 4.1.1 Building transactions in NAMOS By convention, NAMOS is to be used such that a particular pseudo-time corresponds to a consistent system state as in Gray's definition above. Also, by convention, the ordering of transactions is by the ordering of the pseudo-temporal environments. Consequently, if some pseudo-time in the range selected by the pseudo-temporal environment were printed out as the date and time of execution, the system will guarantee that the internal state is externally consistent with the ordering of execution implied by the times printed out. Note that requiring that date and time printed out correspond to some time between initiation and termination of the transaction places some constraints upon the way pseudo-times are chosen -- I will come back to this issue in chapter six. The pseudo-times chosen for "top-level" transactions, those initiated interactively by some user, must be reasonably close to real time. As noted in the previous chapter, construction of transactions m this system is relatively simple. Any computation that manipulates shared objects can be executed as a transaction, by a) Executing it in a pseudo-temporal environment constructed by the pte$transaction primitive, and b) Making all of the updates conditional on a possibility that is completed only if no errors occur that prevent the computation from finishing. Condition a) above ensures that the transaction reads consistent data, and that the only changes made to the state of the system during the range of pseudo-time composing the transaction are those that it initiates. Condition b) ensures that no matter what kind of error happens, the transaction never shows to the outside world of other computations any of the intermediate states that it creates as it proceeds to make changes. Now consider an example. Consider a very simplified view of a distributed bank system. 1 The objects of the system will be account balances, and the transactions that I desire to implement are of two kinds. Transfers of money from one account to another are one kind of transaction, and another kind of transaction is a special one used by bank managers called the MIS transaction. An MIS transaction takes some subset of the objects, and computes some statistics, such as means and standard deviations, based on the value of the account balances. Suppose that we design the programs that implement these transactions 111 the obvious way. Let's say that each account balance is stored as an object implemented by the account cluster, 2 which defines abstract operations to credit the account, debit the account, and get the account balance. Each of these operations is implemented by a program that manipulates the representation of accounts; the account representation is not known outside of the account cluster. It is not necessary to understand the implementation of the account cluster that follows; it is included for completeness. 1. NO attempt has been made to incorporate into this example any of the real-world aspects of banks. I\-fore precisely, I do not intend to imply that the simple bank system can be easily extended to incorporate the complexity of "float", the legal requirements applying to bank systems, or the user interface semantics provided by current bank practices. 2. A cluster is the CLU mechanism for creating abstract types by specifying an underlying representation and the operations that are allowed to manipulate the underlying representation to provide the desired semantics for the type. \Vithin a cluster, the reserved symbol rep indicates the type defined by the cluster, the special marker cvt is used to indicate a parameter to an operation whose type is the one defined by the cluster, but which during the operation is manipulated as the underlying type. Only the operations and procedures contained within the cluster have the privilege to observe and manipulate objects of the type via its underlying representation. For further details, see the references on CLU[Liskov77a,Liskov78]. account = cluster is debit, credit, get_balance; rep = record[credits, debits:int]; balance = proc(acct:rep) returns(int); return ( acct.credits-acct.debi ts ); end balance; debit = proc(acct:cvt, amount:int) signals(insufficient_funds); if balance(acct) <= amount then signal insufficient_funds end; acct.debits := acct.debits + amount; return; end debit; credit = proc(acct:cvt, amount:int); acct.credits := acct.credits + amount; end credit; % get_balance can be invoked by the shorthand account.balance get_balance = proc(acct:cvt) returns(int); return(balance(acct)); end get_balance; end account; Then a transfer between two accounts can be written as follows: transfer = proc(acctl, acct2:account, amount:int) signals(insufficient_funds); dp:possi := possibility$dependent(2); % create a dependent possibility were dp do account$credit (acct2, amount); accoun t$debit(acct 1, amount) except when insufficien t_f unds: possi hili ty Sabort( d p ); signal insufficient_funds; end; end possibility$complete(dp); return; end transfer; When the transfer procedure is called it is executed in its own transaction pseudo-temporal environment, and with the caller's possibility. A new dependent possibility is created by the procedure to protect against a failure between the time account$credit is called, and the time account$debit finishes depositing the money transferred. If the transfer is successful, the new possibility is completed, otherwise it is aborted explicitly if there are insufficient funds, or implicitly by timeout on the possibility in the case of any other error or in the case that the computer executing the transfer stops in the middle. Similarly, we can write a statistical transaction as a procedure, which agam by default executes in a consistent unchanging pseudo-temporal environment. Since the statistical transaction is read-only, we need not be concerned with dependent possibilities. For an example, let us consider a procedure that computes the mean and standard deviations of the balances of a set of accounts specified by an array of accounts. summarize = proc(accts: array[account]) returns(real, real); o/o first result is mean balance, second is std. deviation mean, stdev:real; sum:int := 0; sumsq:int := 0; for a in array$elements(accts) do sum := sum + account.balance; sumsq := sumsq + account.balance ** 2; end mean := float(sum) I float(array$size(accts)); stdev := float(sumsq) I float(array$size(accts)) - mean**2; return(mean, stdev); end summarize; As in the transfer transaction, the summarize transaction again executes by convention in an environment that is unchanging. Now let us consider how these various transactions can interact. There are two interesting cases. First, there might be two approximately simultaneous executions of transfers out of the same account (or into the same account, or one transfer in at about the same time as a transfer out). Second, there might be approximately simultaneous executions of a summarize transaction and a transfer affecting one of the accounts summarized. The following lemma is easily seen to be tru.e based on the definitions in the last chapter. Two pseudo-temporal environments, Pa and Pb· are ordered (that is, Pa""Pb or Pb--..Pa), if both Pa and Pb were created via the pte$transaction operation and neither Pa is derived from Pb nor Pb is derived from Pa· A pseudo-temporal environment x is derived from y if x was created by a call on pte$paraction or pte$transaction whose argument was y, or x is derived from some pte z which was derived from y. This lemma ensures that if we have two transactions executing, and one was not invoked on behalf of the other, then the pseudo-temporal environments in which they execute will be ordered. Now let us consider the first case. If we have two transfer transactions executing at the same time, they will be executing in two ordered pseudo-temporal environments. Thus one of the transactions "happens first" in the ordering of system states by pseudo-time (although not necessarily in real time). Suppose transaction A runs in the "earlier" pseudo-temporal environment and B runs in the later one. Then we also know, by the lemma, that the credit and debit transactions executed by A and B are ordered such that A's credit precedes (in pseudo-time) A's debit which precedes B's credit which precedes B's debit. Now consider the interaction in real time on the known histories of the account being debited by both transactions. If A performs its update on the account entirely before B accesses the account, there will be no problem. B will observe that the initial balance of the account is what was left after A finished his debit. However, if A's change to the account follows a successful read by B of the balance of the account, then B will have educed the known history so that the balance of the account cannot be changed in the range of pseudo-time available to A. A's attempt to perform an update will result in an error signal resulting from an attempt to redefine an already known version. This will prevent A from finishing the debit, and thus prevent the possibility from being completed. Consequently, the credit performed by A will be aborted, since the possibility controlling its incorporation into the system history is never completed. The case of a summarize transaction in parallel with a transfer is similar. Either the summarize transaction precedes the transfer in pseudo-time or the transfer precedes the summarize in pseudo-time (by the lemma). If the summarize transaction precedes the transfer in pseudo-time, the interaction in real time is relatively simple. If the summarize executes first in real time, then the known history of all of the accounts it references are educed by extending the range of versions to pseudo-times from the summarize pseudo-temporal environment. Then the transfer further educes the range of its accounts' versions to the pseudo-times used to read the balance of the accounts, and creates new versions. If the summarize does not precede the transfer in real time, then the transfer \vill have first educed the versions of the accounts and done its updates. \Vhen the summarize is done, the pseudo-times used will refer to the versions of the accounts that were "current" prior to the transfer. Two possible results can occur. If the version of the account referred to by summarize has been kept as part of the known history, it can be used for the computation of the balance. Thus, the summarize effectively executes as if the transfer has not happened. If the version referred to has been thrown away (to save storage), then the forgotten_state error is signalled, and the summarize fails. The normal case would be to keep old versions for a sufficient period of time to ensure that it is likely that all transactions that may refer to them have finished. Thus, we can trade off storage (becoming cheaper as technology improves) against the probability of aborting a read only transaction as the result of an update. In passing, I note that in a system that does not retain old versions requires that a very large read-only transaction (one involving many sites and consequently much delay) lock out updates to anything it reads for a relatively long time. In particular, a system based on locking suffers from this problem. The use of naming for ensuring correct synchronization makes it easy to eliminate this from of lockout by retaining sufficient old history of objects likely to be involved in read-only transactions. The naming mechanism provides the method for properly managing the set of versions retained. If a transaction is aborted because of a forgotten_state or redefinition error, it is quite reasonable to restart it in a new pseudo-temporal environment. Restarting transactions is the normal method of recovery for transactions that fail because of these synchronization errors. There are two problems with restarting transactions, however. First of all, there is no guarantee that the restarted transaction will not also be aborted because of a forgotten_state or redefinition. There is thus the possibility that a particular transaction may encounter starvation, never finishing because it is always aborted by new transactions accessing the same objects. Such a possibility is unlikely if the likelihood of two transactions simultaneously accessing the same object is low. Nonetheless, it may happen. Worse than starvation of an individual transaction is dynamic deadlock, where several transactions cause each other to be mutually aborted, and upon each restart, the timing of the transactions causes mutual aborting to recur. In dynamic deadlock, no work ever gets done by the transactions involved in the deadlock. Dynamic deadlock is also possible in NAMOS, although it is unlikely that the deadlock will persist in a distributed system because the exact timing that resulted in a transaction aborting another is unlikely to recur. In chapter six, a mechanism involving token reservations is developed that can be used to reduce the likelihood of starvation and dynamic deadlock where needed, at the cost of requiring that a transaction "reserve" its resources in advance. Where a transaction can predict the resources it needs (the resources used must be knowable without knowing the values contained in any of the resources to be used), the token reservation mechanism is useful. ## 4.1.2 Constrast with locking and serializers Most of the discussion of transactions is couched in the language and mechanisms of locking. Gray[Gray77) gives quite a readable summary of the use of the locking approach in managing a database. In essence, the locking approach requires that one seize exclusive control of the objects to be read and written for a period of real time. Exclusive control is granted by gaining possession of a lock associated with the object, such that only one process has the lock set at any one time. Transactions may not read or write any data for which they don't hold locks.1 In order to guarantee that a consistent system state is observed during the execution of a transaction, there must be one point during the transaction where all of the objects touched by the transaction are simultaneously locked. In Eswaran, et a/.[Eswaran76] this is called a two-phase transaction (the first phase is acquiring the locks, and the second is releasing the locks). Eswaran, et al. show that transactions that are not two phase can be executed in such a way that objects referred to by such transactions can be changed or observed by other transactions in the middle of the transaction. Further, there must be a mechanism that guarantees that all updates generated by a transaction are either completed or not done at all before any other transaction is allowed to read the updated objects. Thus, by the time any lock is released, all updates to be made must be known to the system. If the objects to be updated lie on several nodes of a distributed system, ensuring that there is a point in time when all locks are held simultaneously can be very wasteful, because there must be at least one node that knows that all the locks are thus set -- implicitly then, the delay built into the locking scheme is at least the time for all nodes involved in the transaction to send messages to a common node that the objects at the sending node are locked, followed by whatever computation is to be done, followed by the time to signal to all nodes involved to store whatever changes that have been made, followed by a wait for commitment, followed by messages to all nodes releasing locks and guaranteeing that all other nodes have committed. If a transaction involving a large number of nodes is executed with the locking scheme, it is clear that the period of time for which other transactions are prevented from looking at the objects it touches is potentially large. Thus, the likelihood of conflicts between transactions is increased, even under the assumption that it is rare that transactions involving the 1. As a refinement, some systems opt1m1ze the case of reads of an object by defining read-only and update locking modes. Any number of transactions may hold read-only locks for an object, but if any transaction holds an update lock for an object, no other transaction can hold any lock for that object. This refinement doesn't affect the arguments that bllow. same data are requested from different nodes at the same time. In contrast, in my system, I have traded off some space to reduce delay. The tradeoff is particularly clear when looking at the interference between read-only transactions like the summarize transaction above, and updates, such as the transfer transactions. Accessing a very large number of account balances to get statistics has little effect on transfer requests -- by the time the statistics gathering transaction gets to a particular account, the transfers accessing that account may have made a number of changes affecting later pseudo-times than the one used by the statistics gatherer, but since the statistics gatherer specifies what state of the system it wants to access, there will be no problem in getting the old version desired by the statistics gatherer. Of course, the implication is that multiple versions of an object have been preserved, rather than just the most current version, resulting in a cost in space. Quite often, though, space is much cheaper than the delay resulting from a statistics gatherer locking out all updates in order to get to a point where locks are set on all objects simultaneously. I am not aware of any scheme that uses locking in a distributed system that can execute transactions reliably in the face of failures, while preserving the nice properties of transactions as described above. This is not to say that such a scheme could not eventually be worked out, just that I have not seen one that simultaneously handled all of the problems. The most unfortunate kind of results of failures may be those that leave objects locked, when the transaction doing the locking has long since failed, or on the other hand, having a lock come unlocked in the middle of a transaction, without the node executing the transaction being aware that the lock was not locked for the whole of the execution of the transaction. The use of locks also raises the specter of deadlocks that can result if some discipline is not used in the setting of locks. In a distributed system, the requirements of autonomy preclude setting locks all at once, and may preclude defining a lock hierarchy in order to preclude deadlock. The reason is that the objects touched by an operation involving objects at multiple nodes may not be known or knowable in advance because of the hiding of the implementation of the objects provided to assure autonomy. Consequently, some deadlock detection and correction mechanism must be developed that will work in the face of failures. My system has the advantage that there are no locks, and therefore no direct source of deadlock. Basically, deadlock is avoided by providing a time bound on the length of time a possibility can remain in the wait state. Thus, transactions may be aborted too often in my scheme, but there is no static deadlock that can arise. Dynamic deadlock can occur, however, as noted above. Another problem with locking is that it is hard to add new transactions by defining new modules. If we have an existing transaction, it sets whatever locks are necessary inside the transaction. If we wish to create a new transaction that consists of executing a sequence of existing transactions, we cannot simply call them in sequence because that would not result in a two phase transaction when the locks set and released by each transaction are considered as a whole. Thus, we must make it possible to seize the locks needed by all of the combined transactions before executing any one of them, and release all of the locks needed after the new composite transaction is completed. Thus, in building new transactions out of existing ones, the locks set by each transaction must be known outside the modules that require the locks to be set. It is thus hard to ensure that the locks needed by a module are set properly, since the module now depends on the caller to do it right. Another approach to consistency is to design the system such that any two objects that can be simultaneously accessed by a transaction must be accessed by requesting the action through a guard process, whose job is to ensure that the data being accessed is accessed all in a consistent state of the system, and that the operation is completed before other requested operations involving the same objects are started. The serializer concept of Hewitt and Atkinson[Atkinson78] provides this mechanism as a basic synchronization tool. Two basic problems with serializers do not trouble NAMOS. First, with serializers there is no explicit mechanism whereby a serializer can handle the problems of errors that occur making the objects protected by the serializers inaccessible. In a sense, the serializer is in the right place to ensure order, but without the tools that allow ensuring the order. Second, in a system that has independently designed mechanisms with autonomous parts, it is unlikely that a common synchronizing process will have been designed in from the start, yet without such a common process, synchronization may be very difficult to achieve. Again, if we allow construction of new transactions out of previously existing actions, it may be that two existing actions to be used in a new transaction are not protected by a common serializer. Such a common serializer would have to be constructed and ---- ~--~-~---- --~~ users of the objects protected by the new serializer would have to be changed to use the new serializer. The primary problem with serializers as a synchronization mechanism in the kind of distributed system I am considering is that they require foreknowledge of the kinds of transactions that the user may want to achieve. If the bank system considered above were designed with serializers, it is fairly likely that someone coming up with a later requirement for some statistics not provided normally through the serializer interface would not be able to get those statistics reliably until the system had been reimplemented with a serializer that handled the new transaction type. ## 4.2 Backup An interesting problem that is closely related to synchronization is that of implementing what I call consistent backup. Suppose that, as a result of user mistakes, some set of operations that has made changes to the system was in error. The user may have typed something at a terminal that was wrong, or whatever, or some processor was temporarily producing incorrect results. \Vhat would be desirable as a recovery action would be to restore part of the state of the system to an earlier time. Now this really consists of two parts -- first, finding out the part of the state that should be restored, and then restoring the state of the objects that must be restored. Finding out the part of the system state that must be restored is often quite difficult, since it is possible that based on the changes made by the erroneous computation, a large number of other changes to the objects in the system have been made. Reversing those changes must be accomplished, as well, in order to completely restore the state of the system to a correct one. In order to do the reversal, the system would have to maintain a dependency graph, where an edge is present in the dependency graph whenever a version depends on another version. Such a graph could be maintained in NAMOS, if a list, called the depends-on-list, would be kept associated with each version. Each entry of the depends-on-list would be the name of a version of another object that has depended on the version containing the depends-on-list. Finding the objects that must be restored based on a computation· that has modified some set M of objects would then involve getting the transitive closure of the depends-on relation, and then finding those objects whose current version depends-on the set M. Keeping the depends-on-list, however, may be quite difficult and expensive. An alternative would be to have a backup mechanism in which the user would have to guess what objects should be restored to their original state. It would be possible to design local depends-on-lists wherever the cost is justified, to help in discovering this. The result is that restoration of system state after this kind of error may not be correct, if the user or the modules that figure out the dependencies are incorrect. Once the set of objects to be restored is chosen, however, a consistent restoration of the object states is a quite simple operation. State restoration simply involves making the version of an object that was defined in the pseudo-time corresponding to the system state to be restored the version that is valid in the current pseudo-time. We can define the restoration of an object in terms of the existing version reference operations: version_ref$define( version_ref$f reeze( ob j 1 ,pt2), version_ref$look up( version_ref$f reeze( ob j 1, pt 1)), poss) will make the version of objl at pseudo-time pt2 the same as that existing at the earlier pseudo-time ptl. If we execute a group of these operations all under the same possibility, we can make the state of all the objects the same as the state that existed at pseudo-time ptl, thus reversing all actions taken at pseudo-times between ptl and pt2. In order that the code above will work, it is necessary that the version as of ptl still can be gotten without a forgotten_state error resulting from the system having discarded it. It is also possible that the restoration \\'ill fail as a result of some simultaneous transaction defining the version at pt2 through a lookup with a later pseudo-time. At the language level, it is much more convenient to define a per-type restore operation, such that type$restore(objl,ptl) when executed in a transaction whose pseudo-temporal environment provides pt2 from its pseudo-temporal environment, will have the effect of restoring objl to the state it had as of ptl. In implementing type$restore for an abstract type, the definer of the type must make sure to restore the state of all objects in the representation of the object. The designer of the type must take into account the same issues he must deal with when defining a copy operation in CLU -- in particular, he must decide whether objects referred to in the representation are part of the object or not. If a stack that has been pushed is restored, it certainly should be popped, but the objects referred to by the stack probably should not be changed by a restore on the stack (unless the objects referred to were actually changed by the operation being undone). All primitive types that can be updated, such as records and arrays, will have restore operations built in, so that abstract types can use these restore operations to build their restore operations. In addition to a restore operation for each type, we need at the language level the ability to obtain pseudo-times to pass to the restore operation. A simple interface would be to have an operation available at the language interface to obtain a checkpoint to which one can restore objects. The checkpoint operation would simply involve getting the current pseudo-time by invoking pte$current on the regnant pseudo-temporal environment. \Ve might write this as a statement: checkpoint c; where c is a variable whose type is pseudo-time. Desugaring the checkpoint statement simply results in an assignment into c from an invocation of pte$current on the regnant pseudo-temporal environment. Of course, certain kinds of failures may still prevent state restoration. In particular, if the object history for each object is not maintained forever, there may be a certain point in the past before which the state cannot be restored. Choosing how much to keep of an object history, then, must be a carefully made design choice that properly trades off the cost of keeping the old versions against the value of being able to restore on errors. As noted, this is only a partial solution to the problem of state restoration, but the ability to name individual versions of objects makes at least part of the problem quite simple. In a system without the autonomy constraints assumed in the thesis, constructing the depends-on relation may be more feasible on a system-wide basis. In such a case, a complete solution to the problem of consistent backup may be possible. However, discovering the true dependencies between object versions ts highly dependent on the semantics of the computations that generate versions. The system, in the absence of such information, would have to make assumptions that are worst case -- e.g. if some process has ever touched object X, all objects ever touched by that process may depend on X. For example if discovering a particular value in X is what causes some set of earlier updates to be completed by completing some possibility, those values depend on version X. Just by seeing what the process actually did, one cannot discover that the earlier updates would have been completed in any case, independent of the value of X. Consequently, in the absence of any other information, the depends-on relation would be very bushy, requiring a much larger number of backups to recover from an error than might actually be the minimum required. Consequently, I suspect that the best approach, whether or not the system has the autonomy requirements of the distributed systems I have considered, is to leave keeping up dependencies to a much higher level, and use a mechanism like mine to do the state restoration, once the set of objects to be restored is known. ## 4.3 Conversational System Interactions Unplanned transactions are not the most difficult kind of interaction that the system may have to support. One factor that unplanned transactions have is that the code for the transaction is entirely within the system at the time of execution. In the case of conversational interactions such as those that might be supported by an interactive database query application, a multi-node debugger, or an interactive program library system used by multiple people, not even the program to be executed can be known by the system in advance. Nonetheless, there is a need in such interactive environments to obtain and act upon data from a consistent state of the system. Further, there may be a need for running a particular set of operations, checking to see that the result is correct, and then either aborting or completing the operations. It is fairly easy to make a conversational interaction work in my system, with the use of the tools already present. The entire interaction ought to be carried out in a single pseudo-temporal environment, under a single possibility, just as in a transaction. The timeout specified when the possibility is created must be large enough to carry out whatever updates are contemplated. The interactive user 1s then free to pursue whatever interaction he desires to make. Upon finishing the interaction, the user lets the system know that the interaction is over, specifying whether or not to complete the possibility. One basic problem with conversational interactions m any system is that the user must be prepared to have his interaction aborted. In my system, there are two kinds of failures - inaccessibility of a particular object version that is to be read, and aborting the possibility under which the interaction is carried out. Inaccessibility is a soft failure that the user may want to handle by ignoring it or by accessing another version. Aborting the possibility is important if updates are involved -- in which case the user can decide if he wants to try again or not. He must be aware that other values in the system may have changed, and so may want to inspect them again in the pseudo-temporal environment in which the retry is executed. I can imagine a simple kind of assistance that the system could perform, which would involve warning the user that his possibility is about to expire so that he can finish his updates, and which would also involve keeping track of those objects that are touched in the current input state, so that if the transaction is aborted, the values that change between that state and the retry state can be identified for the user. Conversational interactions are much more difficult in a locking based scheme. One must be sure that all of the locks are set, and that the locks are properly cleared when the transaction is done. More importantly, since conversational transactions take a long time, the interference caused by reading of data with updates may become severe. Because the conversational transaction is unpredictable in what it will access, the only recourse for handling deadlock is some sort of deadlock detection and correction scheme. In a locking based scheme, aborting is at least as difficult as in my scheme. Serializers allow for no conversational interactions other than the preplanned ones packaged up as part of the serializer requests. ## 4.4 Partially Recoverable Operations In the previous chapter I noted that there is a need for operations that use multiple possibilities in their execution, making it more difficult to handle failures, since some of the actions carried out by a partially recoverable operation will not be reversed by aborting a single possibility. I would like to give several examples to justify this need, and to show how good use may be made of the ability to use multiple possibilities in an operation. Perhaps the simplest example I can give 1s the keeping of metering information associated with an object. Perhaps it is desirable to keep track of the number of times attempts (whether or not aborted) to update an object are made. In order to do this, a way of keeping this count associated with the object without having it backed up when some failure having nothing to do with the object itself happens is needed. One simple way to build such a counter into the operations on the object is to update the counter under a brand-new possibility that is completed immediately after the update. In the bank example, one could build into the transfer transaction the following code: transfer = proc(acctl, acct2:account, amount, counter:int) signals(insufficient_funds); ip:possi :== possibility$create(2); % create an independent possibility were ip do counter := counter + 1; end possibility$complete(ip); % the counter is now permanently incremented dp:possi := possibility$dependent(2); % create a dependent possibility were dp do account$credit (acct2, amount); account$debit(acctl, amount) except when insufficient_[ unds: possibility$abort(dp); signal insufficient_funds; end; end possibility$complete(dp); return; end transfer; This code ensures that any attempt to transfer money results in the parameter counter being incremented. It is important to note that the program uses multiple possibilities here, but did not use a new pseudo-temporal environment. Thus the change made to debit.count is only visible after the output state of the transaction, whether or not it is completed. Had a new pseudo-temporal environment been used, it is possible that for two transfers, the counting of the transfers would happen in a different order than the transfers actually happened, and might be actually not visible m pseudo-time till much later than either of the transfers. Another important use of local possibilities is m the form of run-time optimization often called "memoizing." In this form of optimization, upon each use of an operation on some object, the results of that operation are remembered, along with the state of the parameters that led to the result. Then later, if the operation is re-requested with the same parameters, or some operation that has similar parameters is requested, the saved results can be used to more quickly compute the new results. If all of the updates made by an operation were undone by aborting the possibility, then such memoizing would only help in cases where the overall computation that generated the saved results was completed. An important use of such memoizing might be to reduce recomputation in the case of failure, however, by detecting the fact that he computation requested is the same. By computing memoized results under a possibility that is completed once the saved results are available, the memoization can be completed independent of the completion of the enclosing computation. Since memoizing can be used in such a way as not to change the interface behavior of the object operations, the fact that the memoizing is not recoverable upon failure is not serious. The common theme among these examples of partially recoverable operations is that the primary results of operations, that is the changes made by the operations that are important at the interface, are still recoverable, having been made under the possibility that is current at the invocation of the operation. Only secondary changes are made under possibilities that are completed independent of the overall computation, and in some sense the completion or non-completion of these secondary changes does not change the important semantic properties of the interface. la:n:: 11ib .jj; ui !V>qq~ b!t,..di i!t 71dirb ~l~ ~·16 ~-:i.€c, . u . " & ooita~ '(t4:»up ~.;om ~! b$t:f.r w ·~- ~. ~- '*; ·· · :-~ ~- :::~~=:~!:~l?~~!~::;:..tt~•,,~j!~ W ':<~t;.') ~.-iJ Ul !10hBJUq~~ ~-: .. "Wiirf•frj.)tlgi-lo ·tau tllaf~tfil -~Hw;..,:: ~,-.,;r ~i &~t~,;1,1 ~~~~ .4 ~'M.Jitl-~..-.;., i~~t *~~1 . . -!»ltV) b~·~ ii !SAt t~ lo rn5~~00! ~t~4):) ·:lid !{1'Jl •~;••••~•- ..• f&'f .c$ ... ~ ~-J'B stfj. t!W J-:ml $Wit}Y•c~~~ (iiain~ ·. » ~!~· . .-;;~MJ"1tl~ -~:lri.tf :-.lt9, !ff~T 1(d ~bum i?~l!ilM'l :~11 ~ s~dt .~~-.ltf•·-@tu~lfi:j.: tw Jl ~ ~~n~ri .~1'!¥«01 um ~ ·.·~. ~t·~·,.·~: ... '~ ~-'VJqt) ~dt .nofJI$~~r;, ~rit -lo ncitii~vn! ~ U ~~--- ~.ILR.~IIlt ·~ ·~~h...., ~s~fnoo :nr. ~~Irlt ~rrH~ ~ Jt.lw: ,.. . ; ~ ·•• ~- ~~?R · ~130 'ID. ncit,fqlf!'C"O ~rit . ~Q-~ ~ ru * "' .. ~~--fi.., ~ ·:.· .'to . ii!Z"Jbn~ni " tesJ,uqt;J >tlt 'ln.a> - ~ _.. =~~~== # Chapter Five: Implementation of Possibilities and Tokens A key notion in NAMOS is the idea of a possibility. So far, a possibility has been described as a somewhat special entity that has no history in pseudo-time. The purpose of the possibility is to represent the ultimate choice made by a computation of whether or not to make a particular hypothetical set of changes computed for shared objects real and known to other users of the objects. In this chapter, we discuss the realization of possibilities in a decentralized system of the sort described in the first two chapters. An important problem in the implementation is dealing with multiple kinds of failures. Two basic kinds of failures are important here. Lack of availability due to communications failure or node failure (where refusal of a node to communicate is considered a "failure") is one sort of failure. The other sort is the failure of a computation somewhere in the middle. Both of these failures are really viewed as excessive delay -- the first sort being refusal to communicate for an overlong time, and the second sort being a long delay in the execution of a computation. Since long delays look like failures, one can never be sure whether a computation or communications path has stopped operating or whether it is still working, but slowly. Consequently, whenever a failure is discovered, the mechanisms that recover from the failure must not only recover in the case where the failing component is really dead, but they must also handle the case where the "failing" component is alive and continuing to attempt to operate on that part of the system state that has been the subject of recovery. It is in the handling of failures that the implementation of possibilities and tokens becomes difficult. The chapter will first discuss the overall problem of "atomic commit" that is basic to the implementation. We motivate the idea of a commit record as the implementation of a possibility, and contrast it with some similar mechanisms that achieve solutions to the atomic commit problem. After this discussion, the mechanism by which tokens become versions or aborted versions is described, and the effects of failures are shown. We then discuss enhancements to the basic commit record mechanism. Use of the commit record to ensure atomic commitment of tokens introduces problems of delay and inaccessibility that can be reduced by encaching the state of commit records with the token. Further reduction of delay can be achieved by enhancing the commit record mechanism to automatically distribute changes of state at the earliest possible time. The implementation of possibilities is then described, first for an implementation where the possibility is represented by a single commit record at a single site, and then for an implementation where the possibility is represented by multiple commit records "distributed" among several sites to provide a greater degree of availability. Finally, the storage management mechanisms by which the storage used to implement possibilities can be reclaimed will be discussed. ## 5.1 Atomic commit An "atomic commit" mechanism is one that causes some set of actions to happen "simultaneously" as far as any outside observers are concerned. In the case of the decentralized system, the actions that are to be performed "simultaneously" are transformations of some set of tokens from tokens to verstons. In fact, simultaneity is not the important factor, though it is often discussed in this way. The requirement is that of the two possible results for each object token, version or aborted version, the same choice gets made eventually at all object tokens. A mistake leading to one token becoming a version and another one becoming an aborted version would lead to an inconsistency in the system. The possibility is the abstract mechanism used for achieving atomic commit. All of the tokens created associated with a particular possibility form the set of objects affected by the atomic commit. The possibility$complete operation is an attempt to change all such tokens associated with the possibility into versions, while the possibility$abort operation is an attempt to change all such tokens into aborted versions. Some computation in the system will be the causal agent of the atomic commit. That is, the causal agent is the computation that is intended to complete or abort the possibility. It is important that the system protect itself against the loss of the causal agent (or alternatively, excessive delay in deciding what to do, or a failure of communications between the causal agent and the set of actions to be performed). Thus, designed into the interface to possibilities is the idea of a timeout causing a default decision to abort the possibility. In the case where the causal agent either fails or takes an excessively long time to act, the possibility automatically goes to the aborted state. Then, no matter what action the causal agent may take (if it has not really failed) it cannot reverse the decision to abort. In my system, an atomic commit mechanism is built out of a mechanism that is specialized to the purpose. This mechanism we call a commit record. A commit record is a piece of reliable storage that is created with a fixed initial state, then can be changed by an atomic action to either one of two other states, and can never again be changed. Basically, it is a piece of non-volatile write-once storage that can be in one of three states. A commit record's state has one of three values at any instant that it is read -- call them waiting, complete and aborted, in analogy to the states of possibilities. Further, if any read of the commit record's state returns either the value complete or the value aborted (call these final values), then all other observations will return either that value or the value waiting. It is not necessary that reads be ordered with respect to writes, although in most real implementations once a final value has been returned, later reads will never return the value waiting. Lampson and Sturgis[Lampson76] have described a mechanism for achieving atomic commit. Their mechanism differs in some detail from that used in NAMOS, and uses a slightly different basic mechanism. Their basic mechanism is what they call atomic stable storage.1 The property of atomic stable storage is that it behaves as if any attempt to write the storage either finishes or it doesn't start (leaving the storage unchanged). Thus any read returns a value that was written by the most recent write to complete, rather than allowing the possibility that failing or concurrent writes will cause reads to obtain values that mingle bits stored by several different writes. Commit records have this property, but in addition are also 'vrite once, and have the range of values restricted. 1. Atomic stable storage is a further enhancement of the stable storage described in chapter two. The distinction is that with atomic stable storage there is no possibility that a modification to the storage will be left partially completed -- either the modification will never have happened, or it will have been completed. Lampson and Sturgis describe a way of achieving atomic stable storage by using a disk with each record stored twice with an error detecting checksum. The atomic property is built by using a clever reading algorithm that reads both records, checking the checksum and comparing the two copies. If the checksum on the first record is correct, but it differs from the second copy, then the first copy is correct, and the second copy is old, so it is copied from the first copy. If the checksum on the first copy is wrong, then the second copy is correct, and is returned. Otherwise, either copy will be correct. Their algorithm as described requires that \\Tites be mutually exclusive, but this is easily achievable in a single computer system. The lock mechanism described in chapter two can be used to achieve this mutual exclusion. This mechanism could also be used in the implementation of commit records, by simply ensuring that the commit record is only written once. However, other implementation strategies are possible. Gray[Gray77] has described another mechanism for a centralized system to achieve atomic commit. Recovery from failure in his system depends on the fact that the whole system stops upon a failure, so that a recovery program can be run to back up the state of the variables changed before the failure, while no other computations can be observing the values created by the failing transaction. Because it assumes that the whole system is serviced by a centralized recovery algorithm that always gains control upon failure, and which can know how to restore all the states of objects touched by failing computations, it is not an acceptable approach for a decentralized system. ## 5.2 Tokens The mechanism by which tokens become apprised of the change to a commit record is based on a passive mechanism. Stored with a token is information sufficient to designate and locate the commit record associated with the possibility under which it was created. Whenever it is necessary to check whether a token should really be a version or an aborted version, the system containing the commit record sends a query message to the system containing the commit record. The response generated for such a query will be the state of the commit record -- waiting, complete, or aborted. Since the commit record can never have been in both the complete state and the aborted state, if the answer to the query is either complete or aborted, all other queries referring to the same commit record will get either the same final ans\\'er, the answer "waiting" or no answer. A waiting response has basically the same information about the state of the token as no response at all. Since a waiting token is neither completed nor aborted, it is unknown what the final state of the token will be. Between the time the waiting response was generated and the time the site of the token receives the response, the commit record may have been set to one of the final states. However, once one token has received a final answer. all other tokens referring to the same commit record will receive the same answer if they wait long enough (assuming that the site containing the commit record and communications to it do not fail permanently). The mechanism described so far has a built-in delay, since determining the state of a token always requires sending a message to the commit record and waiting for a response. In addition, the commit record must occupy storage for a long time, since it must always be present to decide for each token whether it is a version or not. We would like to be able to reclaim the storage for a commit record relatively quickly. Finally, for the period that a commit record is inaccessible, all tokens that refer to it appear inaccessible as well. Thus the likelihood of inaccessibility of a token may be very high, even after the token has become a version. We would like the extra inaccessibility resulting from the use of commit records to be as small as possible. To improve the commit record mechanism, reducing delay, storage requirements, and inaccessibility problems, we introduce the notion of encaching the commit state in each token. In addition to the location of the commit record, the last known state (initially waiting) is stored with each token. Call this part of the token the ECS (encached commit state). Whenever a response from a commit record is received, if the response is complete or aborted, that value is stored in the token's ECS. Thus, once the commit record signals a state of complete or aborted, no further queries are needed to ascertain the status of a token. In the absence of errors, each token need wait for only one query and response after the commit record is set to the final state. Delay is thus reduced, and for those tokens that have already copied a final state, any inaccessibility of the token is irrelevant. There is a b:'ls}c problem, however, in that there is always a period of time between the time the commit record enters its final state and the time that the tokens dependent upon it know what the final state is. Worse yet, due to the possibility of errors, this time cannot be bounded. Thus, even if the token is accessible some of the time, and the commit record is accessible some of the time, the token's state may be inaccessible for an unbounded period of time. Is this a bug? Unfortunately not -- it is due to the same basic difficulty that makes the two generals unable to bound the time needed to make a decision. If were to accept a non-zero probability of making a wrong decision, the delay could be bounded. However, given that we always want to make the right decision, the maximum delay is unbounded. Delay in encaching the information from the commit record can be further reduced by eliminating the delay due to the query sent by the token. If the response is labeled so that receipt of it before any query can be properly handled, then once the commit record reaches a final state, "unrequested responses" to queries about the status of the commit record can be sent to all tokens interested in the state of the commit record. These responses can be viewed as a pure optimization, since ignoring them does not cause incorrect operation of the system. However, if they are reflected in the ECS of each token that correctly receives the "unrequested response," then the delay due to querying the commit record after it is final will be non-existent. Keeping track of where the tokens interested in such "unrequested responses" are can be done in several ways. It turns out that much the same information is needed to reclaim the storage used by commit records safely, so I defer the discussion of this to later in the chapter. ## 5.3 Possibility implemented as a single commit record The simplest implementation of a possibility is based on storing the state of the possibility as a single commit record at a single site. This site serves as an arbiter, funnelling the manipulations of a possibility through a single queue that processes each request to manipulate a particular possibility in the order of arrival. What, then, does a commit record look like in such an implementation, and how is it manipulated? The commit record is stored in stable storage at the site. Crashes of the site do not affect the value of the commit record. As noted in chapter two, such st;1ble storage is, in practice, not perfectly achievable. However, the probability of failure of some devices, such as disks, optical memories, and others, can be made quite low at reasonable cost by judicious use of redundancy local to the site. The commit record contains at least the following fields: commit_state: a two bit quantity, set to zero when the commit record is created. The first bit, commit_state.c, is set to one in a possibility$complete operation. The second bit, commit_state.a, is set to one m a possibilitySabort operation, or upon timeout. The possible values are: 00 waiting. The initial state. 01, ll aborted. Aborting takes precedence over completing. 10 completed. timeout: a clock time accurate to some preclSlon (say 1 millisecond), set to the time after which the commit state should be turned from zero to the aborted value, if not already completed. The timeout is never changed, once the commit record is allocated. The commit state is write-once storage, that is written atomically. The atomic write property can be achieved in several ways. As an example, one might use write-once memory built by having a laser burn a hole in a piece of mylar as in the Ampex terabit memory for each one bit. Another possibility might be to use the same trick used by Lampson and Sturgis, storing two copies of the commit state on disk. There are three types of operations that can be requested for a commit record -- complete, abort, and test. They are implemented quite simply. The only detail that I have not mentioned is that the clock used as the standard against which the timeout is compared is the local site clock at the site of the commit record. It is really quite unimportant what clock is used, as long as the clock will reproduce the intended timeout reasonably accurately. If timeout happens early or late, the logical correctness of the system is not violated, but performance may suffer (early timeouts prevent normal completion of operations, while late timeouts result in delay when checking a token created by a failed operation). The algorithms are: complete 0. set commit_state.c = 1 1. return not(commit_state.a) abort 0. if commit_state.c=O then set commit_state.a= 1 1. return commit_state.a test 0. if timeout > time() then call abort. 1. return commit_state In the implementation of these operations, mutual exclusion is necessary. Step 0. of the abort operation must be atomic with respect to other complete or abort operations. A simple way to insure the proper mutual exclusion is by having a lock that must be set to gain access to read or write a particular commit record. The lock is cleared at the end of operations, and cleared also whenever the site comes up after a crash or power-off. The locking mechanism for single objects described in chapter two is sufficient for this purpose. Since these operations are short, the overhead of locking need not be great, consequently an alternatiYe scheme that uses a single lock for all commit records at a site may be quite acceptable. If the storage to be used by commit records is to be re-used, the addressing scheme I.ISed for commit records should incorporate a mechanism for detecting dangling pointers. Consequently, the name used to designate a commit record at a remote site might include not only information sufficient to designate the storage address, but also a unique tag (generated by reading the local site clock, perhaps, if a clock of sufficient resolution is available). Another field in 'the commit record would contain the unique tag. If the tag in the name for a commit record does not match that stored in the commit record, then the commit record has been deleted. The meaning of a deleted commit record when discovered by a query from a token will be discussed when we discuss reclamation of commit records. If a possibility is implemented by a commit record stored at a single site, the continuing accessibility of that site to the sites containing the created tokens may be a question of some importance to the nodes creating tokens, since the token may prevent transactions that manipulate the object containing the token from proceeding if the commit record is inaccessible. For this reason, a node may choose to refuse to create a token based on its lack of trust of the accessibility (or correct implementation) of the commit record based on its location. Nodes that provide highly accessible, correctly implemented commit records will be one of the necessary components of the system I propose. These nodes may either be provided as part of the network, or they may be provided by mutual agreement among those nodes that have resources that might reasonably be used together. Assuring the correctness of and availability of such nodes must be done by observations and agreements outside the system. ## 5.4 Dependent possibilities There are at least two ways that dependent possibilities can be implemented. In one way, a dependent possibility is a commit record as above with an additional information field that refers to the possibility depended upon. The possibilityScomplete and possibility$abort operations on dependent possibilities would be exactly the same, manipulating the commit_state field of the dependent possibility's commit record. The possibility$test operation, however, would be different. The test operation on a dependent possibility that has been completed must involve testing the state of the depended-upon possibility. If the depended-upon possibility responds that its state is completed or aborted then the the dependent possibility can return that value. 1 If the depended-upon possibility is waiting, then a new kind of response is sent, indicating that the dependent possibility is completed, and naming the depended-upon possibility. The depended upon possibility's name then replaces the dependent possibility's name m the tokrn, so that future tests after waiting bypass the dependent possibility. An alternative way to implement dependent possibilities is to represent the name of a depcndrnt possibility by a pair of names. The first element of the pair identifies the commit record that is modified by possibility$complete and possibilitySabort operations, and the second element idt>ntifies the dept>nded-upon possibility.2 The possibility$test operation then consists of testing the commit record that is first on the list using the basic test algorithm defined in the previous section. If waiting or aborted, then the test finishes immediately, returning waiting or aborted. Otherwise, the pair is replaced by the second element of the pair, and the test is repeated. The second approach suffers from the need to store potentially rather long names for possibilities in each token. However, once the token is turned into a version, there is no need to store the name of any possibility, so the storage is only required during the window of time while the token has not yet become a vers10n. The main advantage of the second approach is that the protocol for dealing with commit records is simple and uniform -- all of the complexity is localized in the algorithm executed at the token. ## 5.5 Determining the right to access a token The representation of. the name of a dependent possibility as a pair consisting of the name of a commit record and the name of a possibility (dependent or independent) is very useful in determining whether a computation may obtain the value stored in a token, however. Recall from chapter three that a computation that attempts to read a token may obtain the value if the possibility in ,,,hich it is executing is "the same" as the one the token was created 1. To reducr delay on successive tests, the dependent possibility can also encache the state of the depended-upon possibility. 2. If the depended-upon possibility is a dependent possibility, then its name will be a pair also, and so on, until an independent possibility ends the chain. m, where "the same" has a very particular meanmg. Algorithmically, the phrase "the same" can be understood to mean "search up the chain of dependent possibilities from the token until the first non-completed possibility is found. Then if that possibility is a member of the chain of possibilities under which the computation is executing. the token's value may be accessed by the computation." As a side effect of either implementation of dependent possibilities, the test ·operation causes the token to know the name of the first non-completed possibility. This name can then be checked against the name of the possibility under which the computation is executing to see if it is a member of the chain. If the possibility under which we are executing is represented in the pair (or list) representation, this check is simple and local. If only the name of the topmost dependent possibility is known, then it would be necessary to inquire of that possibility whether the non-completed possibility matches any in the chain, possibly requiring a flurry of messages between sites containing the various commit records. ## 5.6 Possibilities implemented using multiple commit records as voters In order to increase availability, one might desire to try to implement possibilities using several commit records at different sites. A number of algorithms that attempt to implement multiple-site updates of data stored redundantly at multiple sites are given m the literature[Alsberg76,Johnson75,Thomas76], however, these algorithms are too elaborate for the rather simple properties desired of possibilities. A modification of the majority rule approach developed by Johnson and Thomas[Johnson75] seems to provide an effective approach, however. The problem is to implement an object whose representation does not require that a particular site be up to read from or store into it. The behavior of the object must, however, be the same as a commit record, in that the complete and abort operations should be atomic. The essence of the majority rule solution is as follows. The state of a commit record is a composite of the state of N J-'oters, commit records stored at N different sites. The state of each voter is either waiting, completed, or aborted (just as before). When a majority of the N voters are in either the completed state or the aborted state, then the state of the possibility is the same as the state of the majority. In order to prevent a tie, the case where exactly half have voted for the completed state ts defined to be a completed state of the possibility. Voters are not allowed to change their vote -- thus they have a state that is write-once. Further, to handle the timeout, if a voter has not decided which state to vote for after the timeout has been exceeded according to the local site clock, the voter must vote for the aborted state. Thus, in behavior, a multi-site commit record is created out of data structures that look just like the single-site commit record described above. Testing the state of a multi-site commit record involves taking a poll of the N sites. Because only a majority is needed to make a decision, the minimum number of sites that must be accessible to make the test will be LN/2J (in the case of a decision to complete) or L:N /2J+ 1 (in the case of an abort). However, the maximum needed to be accessible to make a decision is N, in the unlikely circumstance that the vote is nearly a tie and the voters are queried in worst-case order. Thus, we want to minimize the likelihood of a tie. I will generalize the notion of majority rule a little bit, since there is -really not some magic property of :N/2 that ensures that the multi-site commit record works. It is only necessary that there be some threshold value K (l~K~N) for the decision whether the possibility is completed or aborted. If K voters are completed, then the test says completed. If N-K+l voters are aborted, then the test says aborted. Otherwise, the state of the possibility is waiting. I call K the complete threshold and N-K+l the abort threshold (if N=l, both the thresholds are required to be 1, so this case is the same as the single commit record implementation). To execute a possibility$abort or possibility$complete operation on the multi-site possibility, the site requesting the abort or complete sends messages to all of the voters representing the possibility (some messages may be lost, of course). Each message is processed at the receiving site, and the voter is set to the completed or aborted state as required, unless it has already been set. The requesting computation does not proceed until all voters have been contacted and have responded, or until a sufficient timeout has expired due to inaccessibility of one of the voters (the requesting computation retransmits requests to decrease the probability of lost messages). In the case that the computation requesting a possibility$complete on the multi-site possibility fails in mid-stream, before sending some requests to voters, each voter independently times out, based on a local clock, entering the aborted state if no complete request has been received promptly enough. The timeout at each voter site also handles the case of a site that was inaccessible to a computation that requested a possibility$complete. The voter at the inaccessible site will eventually enter the aborted state. There are two cases that lead to a high likelihood of having a near-tie m the state of the voters. One case is that of near simultaneous abort and complete operations. If an abort gets to approximately N-K+ 1 of the voters first, while a complete gets to approximately K, a near tie occurs. In the use of the system, it is easy to avoid the circumstance. First, the abort operation is logically unnecessary because of the timeout, so it should only be used in order to speed up the process of aborting when it is known that no complete operation may be attempted. Second, in designing programs, it is normally the case that the execution sequences that explicitly abort will never go through an attempt to complete (as in all the chapter four examples). The second case is when a complete operation happens to signal the voters at around the time of timeout. Thus, some of the voters may have timed out already when the complete arrives. The probability of this circumstance arising can be drastically reduced by a simple trick. If the clocks local to each site· are reasonably synchronized (with some small probability of being more than E seconds out of synch), and if network delays are roughly bounded (with some small probability of being more than o seconds), then if a complete is attempted within o+£ seconds of the timeout on the possibility, it should be refused out of hand at the requesting site, before sending anything to voters (in fact, it may send aborts just to speed up the aborting process). Thus the probability of a timeout overlapping a complete can be made small by making the timeout somewhat bigger than the expected time to complete the operation done under the possibility. In order for these algorithms to work, the requesting site must have enough knowledge to locate each voter of a multi-site possibility separately -- so the name of a multi-site possibility may be somewhat larger than names of objects (that naturally have a single home). In addition, for the refinement just mentioned, the requesting site must be aware of the timeout set on the possibility. Also, the requesting site must know K Thus a reference to a multi-site commit record looks like figure 10. Fig. 10. Reference to Multi-site Commit record complete threshold abort threshold Timeout I 1 list of sites \ L------------------~ In appendix A, an analysis of the probability of availability of a possibility implemented as multiple voter commit records is given. The basic conclusion is that as you increase N. two factors affect availability. First, if the probability of failure during a possibilityScomplete operation is low, the likelihood of a near-tie decreases as N increases. Opposing the first effect, however, is a second one. The probability of failure during a possibilityScomplete operation increases as the number of sites to be notified increases. This can increase both the likelihood that a near tie will occur, and the likelihood that the possibility can't be completed. In addition, the cost in terms of messages sent, load on the network, etc. increases as N increases. Thus, there is probably an optimal value of N which is relatively small, given normal site availability and network reliability. If K is about half of N, it is equally easy to find out that the possibility IS aborted as completed, whereas as K decreases, determining that the possibility is completed becomes easier and easier. Since the normal case is that operations are completed, smaller values of K ought to increase performance overall, reducing the number of responses needed to determine the state of a possibility. Values of IC greater than one half of N don't seem to be useful, though. 5. 7 Reclamation of commit records So far, commit records have been considered to be permanently allocated. The cost of permanent allocation of commit records can be very large, since every transaction or other operation involving shared objects will require a distinct commit record to represent the possibility associated with the operation. Consequently a scheme to reclaim commit records when they are no longer needed is desirable. Since the state of commit records is eventually encached within the versions and aborted versions stored as part of the object known history, it is clear that eventually there will be no references to a commit record. When there are no references from tokens still outstanding it is quite safe to delete a commit record. It is not a good idea to delete a commit record while it is still in the wait state, though, since some computation may still refer to the commit record through the possibility mechanism. That computation may yet create new tokens that depend on the possibility for realization. The key issues in implementing a deletion mechanism for possibilities are: 1. It must be possible to detect or create the situation that no token exists that has a reference to a particular commit record. 2. Since computations may refer to commit records through possibilities, the use of possibilities that refer to deleted commit records must be prevented. It is extremely dangerous to delete a commit record that has not had its state encached in all of the tokens referring to it. The result of such a deletion would be to make all such tokens permanently inaccessible, thus blocking read operations on the known histories containing those tokens. Consequently, any deletion algorithm should err only by not deleting unneeded commit records, never by deleting needed commit records. Bec<1use of the modularity of programs, at the time a possibility is completed the program doing the completing may not be aware of the entire set of references to the commit record that have been generated by operations invoked in the possibility. For this reason, an explicit delete-commit-record operation that can be used by application programs is not a reasonable solution. Even if the program could figure out the set of references to the commit record that exist in objects, the possibility of programming errors in using the explicit deletion would argue <1gainst such a strategy, the cost is quite high if such a mistake is made. A commit record must thus contain enough information to allow determination of when it is safe to delete the commit record. Then the site containing the commit record can be responsible for ensuring that the commit record is deleted only when no references to it exist in tokens. If the commit record site behaves improperly, deleting it even when the site knows that references exist, tokens depending on the commit record will become permanently locked up. For this reason, a basic tenet of the system is that any site creating a token must trust that the site implementing the commit record associated with the token does so correctly. If a non-trustworthy site is proposed as the home for a commit record, the token may simply not be created, and an error response be generated. \Vhen a token is created, it is necessary to know that the commit record on which it is to depend (a) still exists, and (b) is not completed or aborted. To msure (a) and (b), the site creating the token must first inquire of the commit record its state. If either condition is not satisfied, the token is not created, and an error is returned. Since a message exchange with the commit record is already needed, we can use the message exchange to tell the commit record that a token referring to the commit record is about to be created. Thus, when a commit record receives such a request, it can record the name of the token (object name together with pseudo-time it is valid from). It is not too difficult for a commit record to obtain the list of all tokens that depend on it. To use the list, the commit record must be aware when a token on the list no longer depends on it. This can happen three ways. 1. A token depending on the commit record successfully encaches the state of the commit record. 2. A token depending on the commit record is deleted. 3. A token listed as depending on the commit record was in fact never created (the list is formed before tokens are created, so a failure after a token was entered on the list could prevent the creation of the token). \Vhen a token encaches the commit record state or is deleted, a message can be sent to the commit record indicating that the reference is deleted. However, a failure in the sending of this message would result in not deleting the commit record even though it is deletable. Consequently, the primary means of checking the dcletability of the commit record is by polling from the commit record. The commit record, once it reaches a final state can poll the objects named in its dependency list. A trick that can be used is to encode an aborted commit record by immediately deleting it. Any request for the state of the commit record after it is deleted can be answered by saying "no such commit record exists." If the request was from a token, it knows that the token was not completed, and since commit records in the wait state are not deleted, it must be aborted. However if the request for the commit record comes as a result of an attempt to create a token, the token will not be created. The messages between tokens and commit records are thus the following. T->CR create-ref(CR-name, token-name): query to commit record whether token referring to the commit record may be created. CR-name is the name of the commit record queried, while token-name is the name to be used to refer to the token. CR-> T permit-create(CR-name, token-name, ok?): response to create-ref. If ok? is yes, then the commit record was in the wait state, and an entry was added to the list of tokens referring to the commit record. Otherwise, the commit record was in either the complete or aborted states. A deleted commit record also returns a "no" response. If no response is received, the create-ref may be retransmitted. T->CR test(CR-name, token-name): message that is sent by a site containing a token to get the state of a commit record, in order to decide whether the token value can be returned as the result of a read or not. CR-> T state(CR-name, token-name, s): sent either 111 response to a test() or when it is desired to delete the commit record after it has been completed. In the case of a deleted or aborted commit record, s is "aborted". If the state of the commit record is complete, then s is "complete". If the state is waiting, no state(s) response is generated. T->CR no-ref(token-name): sent when a state("complete") message is received, once the token encaches the fact that the commit record is complete or immediately if the token has already been deleted (see chapter six for details about deletion of tokens). The commit-record deletes the token named token-name from its list of tokens referring to the commit record. The no-ref message allows the deletion of commit records. All of the other messages are needed already for the function of commit records, independently from ddetion. Once a commit record enters the complete state, it immediately starts polling the dependent tokens by sending state("complete") messages to all the tokens on its list, until such tokens are all removed from the list by no-ref( token) messages. Once such tokens are all removed, the commit record can be deleted. A nice property of this scheme is that it reduces delay in encaching the state of commit records into tokens, since an immediate attempt is made to broadcast the commit record state to all dependent tokens. :\-Iulti-site possibilities can be managed by a modification of the same mechanism. However, individual commit records making up the possibility cannot be deleted until the possibility as a whole is aborted, or until the possibility is completed (as a whole) and that fact is encached in all tokens referring to the possibility. The fact that the possibility as a whole is aborted or completed is normally detected by some token as the result of a number of messages from individual voters specifying their state. The token will then encache the state of the possibility. In the single commit record implementation, the token would respond to the state() request with a no-ref() request to signal that no reference remained to the commit record from the token. In the single commit record case, the no-ref() request is not needed if the state of the possibility is aborted, since the commit record could be immediately deleted no matter how many references existed to it. However, since the token is the only entity with knowledge about the state of the possibility as a whole, the token must initiate the deletion of the commit record. Consequently, in the multiple commit record implementation, a new request is required -- the overall-state(CR-name, token-name, state) message, sent from the token discovering the overall-state to at least one of the commit records (it may be sent to any number as an optimization). As a result of receiving an overall-state message, the commit record receiving it knows the overall state of the possibility. This knowledge is sufficient to initiate deletion. It also can be used to optimize further requests from tokens -- since the overall state is known at a commit record, that commit record can act in behalf of all other commit records and unilaterally specify the state of the entire possibility. We can take advantage of this optimization by allowing two additional values to be returned by the state() request from the commit record to the requesting token -- one meaning "the possibility is completed overall" and the other meaning "the possibility is aborted overall". These messages have the effect at the token of immediately deciding the voting without further tallying of votes from other voters. Once a commit record knows that the possibility is aborted, it can delete itself (thus discoYery of a deleted commit record in a possibility means that the possibility is aborted overall). However, if the possibility is aborted, all tokens referring to the possibility must he known to have encached the state of the possibility before any of the commit records are deleted. The set of tokens referring to commit records representing a possibility is the union of the private lists maintained by each individual commit record as the result of "yes" permit-create responses, minus those tokens that have sent overall-state() messages to one or more of the commit records. A relatively simple algorithm for determining when the commit records can be deleted is to have the recipient of an overall-state message poll all other commit records to determine the entire set of tokens that have references to the possibility and to collect the set of overall-state messages so far received at other commit records. Then the recipient of the overall-state message can poll all of the tokens by sending a state("overall complete") message to each token. In response, each site will send back an overall-state("complete") message to confirm (note that this always has to be sent, even if the token has been deleted) that the token has encached the state and no longer will refer to the possibility. When the set of tokens referring to the possibility has been determined to be empty in this manner, then the commit record that determines it can signal all others to delete themselves and delete itself. If any of the messages are lost at this point the others may not know to delete themselves. Since no tokens refer to the commit records any more, the commit records would never be deleted. To guarantee that all of the commit records are deleted eventually, we need to ha\'e each commit record poll periodically to see what the state of the other commit records making up the same possibility is. For this purpose, we can organize the commit records into a "ring" so that each commit record knows about a left and right neighbor commit record. Periodically, each commit record polls both its left and right neighbors with a test operation. If it gets an "overall aborted", or a "deleted" response, it deletes itself. If it gets an "overall completed" response, then it marks itself as knowing the commit record is "overall completed" as well. Any other response can be ignored. As noted above, when a token is created, it sends out create-ref requests to all of the voters. Each voter that receives such a request records the name of the token that might be created (the object id and the pseudo-time of creation) on a private list to be used in the deletion of the commit record. The permit -crea te("yes") response is returned by a voter if the voter is still in the waiting state, othen ... ·ise a "no" response is sent. In order for a token to be created, the possibility as a whole must be in the waiting state. Thus, a token may be created only if max(N-K+ l,K) voters send back "yes" responses. 1 Each successful token creation will thus result in at least max(N-K+ 1.~<) entries among the private lists of references maintained by the commit records making up the possibility. Thus, when taking the union of the lists to determine the set of tokens referring to the possibility, one need only include those tokens included max(N-K+ 1 ,K) times. ## 5.8 Summary In this chapter we have discussed the implementation of possibilities in terms of commit records. Two basic strategies have been described -- a single commit record implementation and a multiple commit record implementation. The single commit record implementation is much simpler and more efficient, though it does have the drawback of decreasing the availability .of tokens since the availability of a token depends both on the availability of the site containing the token and the site containing the commit record (and the communications in between). Although the availability decrease due to use of a commit record can be made smaller by broadcasting its state once it changes and encaching the state in the token, still, there is a window during which the availability of the token depends on the availability of the commit record, and the size of this window cannot be reduced. The multiple commit record implementation increases the availability of the possibility as a whole during that window, at the cost of a more expensive (in terms of messages sent, storage, and CPU cycles) and more complicated implementation. We conclude that the multiple commit record implementation should only be used when availability is more valuable than the costs of implementing the multiple commit record implementation. It is possible for both 1. Actually, if the permit-create request were modified to indicate whether the present state of the voter was completed, aborted, deleted, or waiting, then the number of responses needed to create could be somewhat reduced -- the token need only prove that the possibility is not yet out of the waiting state. This optimization is not important, since it only makes things better when the possibility is in the middle of changing its state to either the completed or aborted state overall, and the ability to more speedily create a token at the point after its possibility is being forced into its final state is of dubious value at best. implementations to coexist 111 the same system, with the multiple commit record implementation to be used only for those operations that deal with objects that have high availability requirements. It would be perfectly reasonable for a request to create a token for an object to be rejected by the manager of the object on the basis that the possibility controlling the conversion of the token into a version has not been implemented with sufficient availability guarantees. # Chapter Six: Implementation of Objects: Known Histories, Versions, etc. This chapter completes the description of implementation of the system. In chapter three, the behavior of objects was described in terms of known histories that provide a mapping from pseudo-time to versions valid in particular pseudo-times. Many issues that are important in a practical implementation were not discussed in chapter three, and will be discussed here. Some of the issues are: * maintenance of pseudo-time at multiple sites. * maintaining the set of versions in the known history. * creation and deletion of objects. * storage reclamation of versions that are out-of-date. * data objects that can have special implementations. * copying versions of objects (encachement). * handling related groups of objects, by "paging." * reducing the likelihood of dynamic deadlock. First, the relationship of pseudo-time to real time, and the mechanisms of implementation of pseudo-time will be explained. The next few issues have to do with the representation and manipulation of objects at their home node. First a set of mechanisms are developed that can implement what I call a cell data type, or what might be also referred to as a mutable record type. This is a universal data type, out of which any other type can be built. However, there are possible better implementations for particular data types -- two of these types in particular will be discussed, queues and accumulators. Finally, certain enhancements to the mechanism that can be used to optimize special performance problems are discussed -- a space and delay problem due to computations dealing with many small objects is solved by a grouping called "paging", a delay problem when dealing with primarily read-only data is solved by encachement of versiOns of objects, and a delay problem when there are computations that manipulate the same objects close together in time is ameliorated by an optional mechanism called token reservations. ## 6.1 Representation of Pseudo-times and Pseudo-temporal Environments In chapter three, we discussed the properties required of pseudo-times and pseudo-temporal environments. Pseudo-times are values beionging to an ordered set. Pseudo-temporal environments are objects that keep track of the progress of a particular computation. We require that the pseudo-times used for updates executed as part of two sequential steps in a computation be ordered, such that if step A precedes step B, all pseudo-times used in A for updates precede all pseudo-times used in B for updates. In other words, the pseudo-times given out by the pteSnext operations executed on a pseudo-temporal environment must be given out in increasing order. A pseudo-temporal environment essentially is a way of keeping track of the largest pseudo-time used so far in its associated computation. The pte$next operation simply returns a still larger pseudo-time and changes the pseudo-temporal environment to reflect the new largest pseudo-time used. There IS further structure to pseudo-time and pseudo-temporal environments, however, due to the existence of concurrent computations. We wish to guarantee that two concurrent updates to primitive objects do not execute in the same pseudo-time, so that any two updates to the same object are totally ordered. More strongly, we wish to guarantee that the pseudo-times used for updates in two independently executing (possibly concurrent) transactions are ordered such that all pseudo-times used in one transaction follow all pseudo-times used in the other. At the top level, there are a set of concurrently executing computations that are executing independently, that is, with no a priori relationship of the ordering between steps in distinct computations. Each of these computations has its own pseudo-temporal environment from which it gets pseudo-times, by pteScurrent and pteSnext, and pseudo-temporal environments in which to execute multi-step transactions. For the moment, let us ignore the complication introduced by multi-step transactions, and think about a transaction as dealing with two pseudo-times, an input state reference which the transaction uses to read all of inputs, and an output state reference which the transaction uses for all of the updates it eventually makes. What we want is for a transaction executed in a top-level pseudo-temporal environment to be atomic with respect to all other transactions -- that is, the pseudo-times between the input state and the output state are not used for updates by any other transaction. A top-level pseudo-temporal environment is a list of two integers, last-time and pteid. Each top-level pseudo-temporal environment is assigned a unique value of pteid. The last-time field is used to guarantee that the pseudo-times resulting from successive pte$next operations in a computation are monotonically increasing. Pseudo-times returned by pte$next in a top-level environment are obtained by reading a clock (about which more will be said later), waiting until the clock value is greater than the value of last-time, then updating last-time to the clock value, and returning a top-level pseudo-time consisting of a list containing the new last-time and the pteid. The pteid guarantees that pseudo-times from pte$next in different top-level pseudo-temporal environments are distinct. In general, a pseudo-time is represented by a list of integers. Two pseudo-times are ordered by finding the first position in which the pseudo-times differ (if the lists are of different lengths, then the shorter list is thought of as being extended with zeros to the length of the longer), and using the ordering of the integers at the position of difference. Thus, for example, two pseudo-times resulting from different pseudo-temporal environments by pte$next are ordered first by the times obtained from the clocks read, and if the times happen to be equal. the tie is broken arbitrarily by using the ordering of pteids. Now, how are pseudo-temporal environments derived from top-level pseudo-temporal environments? All pseudo-times obtained from such a derived pseudo-temporal environment must belong to one tick of the top-level clock. The trick is to add "low order digits" to pseudo-time, such that the increases in pseudo-times returned from a derived pseudo-temporal environment are confined to these "low order digits". Thus, all the pseudo-times obtained by pteSnext and pteScurrent from a pseudo-temporal environment derived using pte$ transaction from a top-level pseudo-temporal environment are four element lists, where the first two elements are the same for all such pseudo-times, and specify the "instant" of top-lrn'i pseudo-time. The third elements of successive pseudo-times derived in this way are in increasing order. The fourth element is always zero for a transaction pseudo-temporal environment, but in one of a set of parallel executions resulting from executing pteSparaction, the fourth element uniquely identifies the particular derived pseudo-temporal environment. A derived pseudo-temporal environment has three parts, last-time, pteid, and time-derived. The new field, time-derived, specifies the "instant" of pseudo-time in which the computation carried out in the derived pseudo-temporal environment executes. For a pseudo-temporal environment derived from a top-level pseudo-temporal environment, time-derived is a list of two integers. The pteSnext operation ,..,.orks as before, but returns a value that consists of time-derived concatenated with last-time and pteid. \Ve can handle any depth of derivation with this structure -- time-derived just IS a longer and longer list. To execute pte$transaction in some pseudo-temporal environment, we get a new time, L, larger than the last-time field in the deri,·ed-from pte. The new pte is constructed by setting its last-time field to L, its pteid to zero, and making up a ne,..,· derived-time by concatenating the derived-time field of the derived-from pte with (L-1) and the pteid of the derived-from pte. The pteSparaction operation constructs the derived pte's m a similar way, such that the derived pte's differ initially only in the pteid field. As a pre1ctical matter, we can observe that individual steps in a computation are unlikely to execute more frequently than once every microsecond or so, on today's hardware, so a resolution of one microsecond on the integer clock values is sufficient. Similarly, it is unlikely that pseudo-times referring to the state of objects more than a few years in the past will be in use. So the integer clock times can easily be encoded in a fixed 48-bit field, by storing the time in microseconds since some fixed reference time, modulo 248. With the exception of top-le,·el pseudo-temporal environments, the pteid field need be no more than 8 bits or so to distinguish all of the parallel executions created by one paraction call. Top le"el computations can be uniquely identified by their time of creation, which can again be encoded in 48 bits. So a pseudo-time could be easily encoded in 96 + 56n bits where n is the number of levels of derivation. In a system that did not make use of derived levels, i.e. one that does not support the modular composition of transactions, a fixed size 96-bit allocation would suffice. In this representation, if we ignore the modulo-248 encoding (by limiting the lifetime of the system to 248 microseconds), we can think of pseudo-times as simple binary fractions on the interval [0,1). Pseudo-temporal environments for two transactions such that one is not derived from the other can be though of as disjoint subintervals. Two parallel actions created by the same pte$paraction operation can be each thought of as the union of disjoint subintervals (corresponding to sub-transactions), such that the union of the parallel action ptes is a subinterval of the pte from which it was derived. ## 6.2 Maintaining the time - pseudo-time relationship In conventional systems, operations make their changes always to the "current" state of the system; what is needed is to ensure that a notion of the current state be embodied in the construction of NAMOS. In NAMOS, the pseudo-times obtained from top-level pseudo-temporal environments function as the current state would in the more conventional system. To achieve this behavior, a mechanism is needed for choosing the instant of pseudo-time in which a transaction is executed that is later than the pseudo-times of operations that execute before the current operation in real time. One possible mechanism would be to use a central service that gives out pseudo-time values in increasing order -- essentially a central sequencer as defined by Reed and Kanodia[Reed78]. The problem with this approach is that the sequencer becomes a bottleneck in the system, both in terms of performance, and in terms of hanging up the system when it becomes inaccessible. It is important to note that the mechanism that chooses pseudo-times need not perfectly follow the requirement that pseudo-times be given out in ascending order -- regardless of the order in which they are chosen, they may actually be used in a different order anyway. For example, transaction A may choose its instant of pseudo-time before transaction B does, but there may be some delay that prevents A from actually completing its operation until after B is completed. If A and B deal with disjoint sets of objects, this switching of execution order will have no effect on the the transactions or correct operation of the system, while on the other hand if some data is common to them both, the rules for educing known histories will prevent inconsistent results, perhaps aborting A to insure correctness. The system is thus highly tolerant of pseudo-times for transactions being chosen out of order. Since it is my basic assumption that transactions that conflict on their set of objects to be manipulated will not be likely to happen close together in time, a mechanism that chooses output pseudo-times such that two such choices separated widely in real time will give pseudo-times that are ordered in correspondence with the real time ordering \viii suffice. The easiest way to do this is to use approximately synchronized clocks. By using a set of approximately synchronized clocks, one per node, one can ensure the property that any time one gets a value it will be greater than the values obtained at all other nodes at times sufficiently far in the past. As noted above, the clocks at different nodes need not be in perfect synchrony. However, if one clock is consistently slow, it will have a serious effect on the performance of operations originating at that node. If operations originating at two different nodes encounter a conflict that causes one of them to abort, the one whose clock is slow is the one that will be likely to abort. If the clock at a site is extremely slow, it is possible that its updates will always abort, resulting in effectively preventing that site from having an effect. Synchronizing the system clocks whenever they come up by usmg the operator's watch will usually get the system time accurate within a few minutes. Depending upon the rate at which clocks drift, and the likelihood of two operations running \vithin a few minutes of each other attempting to update the same data, this may be sufficient synchronization. By taking great care, but without using particularly expensive technology, clocks that are synchronized within a fe\v microseconds are possible, using broadcast signals such as those from station \V\VV as a time standard, and reasonably stable clock circuits. Given that we are using these techniques, one can do still better by using a technique proposed by Lamport[Lamport78]. Essentially the mechanism is this. Whenever any mess<1ge is sent between two nodes, it contains the time the message \\·as sent at the originating node. The receiver of the message inspects the timestamp, and if the time is in fact greater than his own real time clock, one of two things is wrong -- either the source's clock is fast, or the receiver's clock is slow, in either case by an amount at least as great as the difference between the message timestamp and the receiver timestamp. Lamport proposes a strategy that amounts to adjusting the receiver's clock forward in such a case so that whenever a message is received that originated at time 1, the receiver node's clock is set to t if it is not already greater than t. This has the effect of synchronizing each clock to the rate of the fastest clock in the system. There is a problem with this approach, however. If some clock advances much too fast, or if it is deliberately set far into the future, the node containing the clock will get priority in all operations, and more importantly, be able to lock out all updates from other nodes until those nodes advance their clocks. A modified version of Lamport's strategy, in which a message that has a timestamp very much greater than the receiver's clock will not be processed, helps to solve this problem. This technique will also help to solve the problem of incorrectly set clocks. ## 6.3 Known Histories The known history 1s the mechanism that maintains the relationship between versions and their pseudo-time of validity. It is realized as a data structure stored at the home of an object. The primary purpose of the data structure is to keep track of the individual versions, tokens and aborted versions associated with the object, and to change as operations are applied to the object. Implementation of known histories is fairly straightforward, but it does involve some slightly tricky details. It is assumed, as a basis of robust operation, that once an operation on the object has signalled its completion, that the changes made by that operation are safely stored away on stable storage. Thus, it is required that all of the versions, tokens, and the known history data structure itself be stored on stable storage before signalling the completion of an operation. Further, it is necessary that no matter where in the process of manipulating the known history the home node fails, the known history be left in a consistent state. The local locking mechanism described in chapter two can be used to achieve this result, by keeping the previous consistent state of the known history such that it is automatically restored if the manipulation fails while the known history is locked. The known history data structure in its simplest form consists of a list of entries that contain a pointer to the representation of the value of a particular version, the start and end pseudo-times that define its validity, a reference (possibly to another node or set of nodes) to a commit record(or records) to specify the possibility under which the version is created, and the cache for the Fig. ll. Known History Entry value start PT end PT commit record commit state preVIOUS commit record's state (see figure 11 ). These entries are threaded together as a singly threaded list in reverse chronological order of pseudo-times. This threading ensures that it is easy to add a new entry in between any pair of elements by a single atomic pointer swap. The object itself is then represented by a cell in stable storage, called the object Fig. 12. Known History Representation Object Header List of Known History Entries l thread --iii----.....,_---. header (see figure 12), that contains a pointer to the head of the list of known history entries. The two basic operations on the known history are the basic lookup operation, which attempts to find the version of the object that corresponds to a particular pseudo-time, and the new-token operation, which attempts to make a new token that is valid from a particular pseudo-time. I will consider these in turn. The lookup and new-token operations provide basic tools that allow the creation of objects represented as cells that contain record values, where the value of the cell is loaded to inspect the state of the object and the value of the cell is changed by a store operation to change the state of the object. While cells are in a sense complete -- they can be used to construct any kind of mutable object, there are some kinds of objects that may be better represented in a slightly different way, taking direct advantage of the constraints provided by the restriction on the kinds of operations allowed on an object. In this sense, what is about to be described is a default implementation strategy that is known to work for all kinds of mutable objects. After this strategy is described, alternative implementation for special types of mutable objects will be discussed, with the example being queues. ## 6.3.1 Lookup requests The lookup operation is a search of the known history, looking for the version or token whose start and end pseudo-times bracket the pseudo-time searched for. If no such version or token exists, then the version or token whose start time comes closest to, but does not come after, the specified pseudo-time is found. If this process results in finding a token, then the state of the commit record must be queried to determine whether or not the token's data can be returned as the version looked for. If a version is found in the search, then it is returned, and its end time is extended, if necessary, to include the pseudo-time specified in the search. Figure 13 illustrates the message passing structures that can result from a lookup request. Fig. 13. Communication in a lookup request (1) lookup requestor object home (2) value (a) The version referred to is not a token. object home requestor test ommit recor . state va ue (b) The version referred to is a token. The lookup operation is invoked as a response to a message from some remote user, in many cases, and there is a question with regard to how the waiting for a response from a token should be managed. One possibility is that the action on finding a token is that a query is sent from the home node to the site of the commit record, and another message is sent to the requesting node, indicating that it should try again later. This approach has the advantage that no memory of the pending lookup operation need be maintained at the node containing the object. Since no memory is allocated while waiting, if the response is lost, there is nothing to clean up. The requester recovers from an error by the simple mechanism of resending the request after a timeout. At some time in the future, a response will come from the commit record, and if that response is that the commit record is complete, then the token becomes a version that can be read later. This approach, while it simplifies recovery after a lost message, has the drawback that it may cause a rather large delay in the case where a token is accessed soon after it is updated. The other possible approach for handling the waiting is to send the query to the tokrn's commit record, but not respond to the requesting node until the commit record responds either positively or negatively. This mechanism requires remembering the request at the home of the object while waiting, to recall what node the lookup request came from, and wh1t pseudo-time was specified as the target of the lookup request. However, the advantage is that as soon as the state of the commit record is known, it can be reflected back to the requester. There is a disadvantage, however, in addition to the memory required, in that the requester cannot distinguish the delay due to querying a commit record from a delay resulting because the original lookup request was lost before arriving at the object's home node. Neither of these approaches is completely satisfactory, but a combination of the t\vo can solve most of the problems of each. Upon receiving a request to lookup a specific version, the home node responds to the requester immediately, either with the ,·ersion, or with a message meaning "I have a token to check on." If this latter message is sent, a query is sent to the token, and in volatile storage, an entry is made that remembers the request -- the requester node, the object, and the pseudo-time -- enabling the immediate forwarding of the response from the commit record back to the requester. When the commit record's response comes back, the volatile storage entry is used to find the particulars about the request, and if the token is now a version, the result of the lookup is forwarded to the requester. If the token is aborted, then it is deleted from the known history, and the lookup operation is reinitiated, resulting in looking at the next previous entry of the known history. As a general rule 111 the implementation of NAMOS, we may use volatile storage to hold information that allows early forwarding of messages, or for other performance enhancements that are not strictly required for NAMOS to work correctly. The combined approach has the advantage that if no error occurs, the response to a lookup that encounters a token is just about as fast as possible. On the other hand, because volatile storage is used to remember the information for forwarding a request, there is no problem in recovering the storage used to remember the state of requests involving tokens, should some failure occur. Let's consider the three kinds of failures that can occur. First, the commit record can become unavailable, either through loss of the query to the commit record, the loss of the response from the commit record, or loss of availability of the site containing the commit record. In this case, the requester node will get no response other than possibly the response that says the home has received the request. After some period of time, the requester will time out and resend his request. Then, the home node will aga111 query the commit record, and the request will proceed as before. Second, the requester can fail after making its request. This can occur either because the requester times out, or because of a crash. Eventually, the home node may send a response to the requester, but there is no awaiting a reply from this response, so the requester cannot destroy the system by failing. Third, the home node can fail, losing volatile storage. In this case, the response from the commit record may never get reflected back to the requester, who will then time out and retry. The response from the query to the commit record may come back at a time when it can be reflected in the state of the token of interrst -- this will only optimize a retried request, or the response may come back while the home node is inaccessible, in which case, the retried request will perform as if the original request had not happened. ## 6.3.2 New-token requests The new-token request is much simpler than the lookup request, since the new-token request does not depend on the state of tokens already in the known history. The purpose of the new-token request is to install a new token in the known history to reflect a pending change to the object. Parameters to the new-token request are the \'alue of the new token, the commit record that represents the possibility under which the token is created, and the pseudo-time at which the new token is to be valid from. The basic action is to create (if possible) a new entry in the known history whose start and end times are equal to that specified in the new-token request. As notrd in the previous chapter, if the commit record must be reclaimed once it is no longer needed, it is important that before a token is placed in the known history, the commit record know about the token that may depend on it. Consequently, a create-ref message is sent to the commit record, and when a permit-create response is received, the fate of the token is decided. Figure 14 shows the pattern of messages that make up a new-token request. Fig. 14. New-token request processing requestor object home commit node ~~--~~--~_, Again, to handle the problem of failures at the home node, the requester is responsible for ultimately causing the retransmissions needed to handle lost messages and unavailable nodes. While the create-ref message is outstanding, no response is made to the requester. An entry in volatile storage is made to handle the permit-create response when it comes back. This entry contains the parameters of the new-token request. The new-token request fails if there is already a version whose start and end pseudo-times bracket the pseudo-time the token is to be valid from. If such a condition is detected when the token is to be created, then no change is made to the known history, and an error response is sent to the requester. This condition can be detected either before or after the create-ref /permit-create exchange. As noted in chapter five, we need not be concerned if the new-token processing fails after the create-ok message is sent; there is no problem if the commit record has a reference to a nonexistent token, since the query from the commit record to the object will generate a no-ref response indicating that no token exists that refers to the commit record. If a token already exists that was created at the pseudo-time specified in the new-token request, then it may be the case that an earlier attempt to perform the new-token request failed after the token was entered into the known history, but before the response reached the requester; the requester may resend a duplicate request to recover from such an error. It is also possible that the new-token request \Vas duplicated in the network. In either case, an error response should not be returned. Instead, the name of the possibility specified in the token's knO\vn history entry should be compared with the name of the possibility that is specified in the new-token request. If equal, then the message is a duplicate, and a response indicating the request was successfully performed is generated, since returning no response would not help the requester in the case of a failure that prompted retry of his request. If the possibility is not the same, then an error response should be generated, since this results from the case where a requester (or multiple requesters) try to create the same version under different possibilities -- a meaningless thing to do. Having discussed the mechanism for implementing the new-token request, let us contrast it with an alternative mechanism that can be used to achieve the same effect, but perhaps with fewer messages and less delay. The observation that motivates the alternative mechanism is that a new token can never be created before polling the commit record to inform it that a possible reference is being created. This requires a pair of messages, increasing the delay significantly if the commit record is not local to the node containing the object of the new-token request. One fewer message can be used by sending the new-token request through the commit record site on its way to the home of the object. When it passes the commit record. a reference to the new token that might be created is entered onto the commit record's reference list, and a notation that is equivalent to a create-ok message in information content would be added to the message before forwarding it to the home of the object. The new token could then be immediately added to the known history of the object, and the response could then he sent to the requester. The triangular pattern of messages that results is shown in figure 15. Fig. 15. Alternative new-token processing requestor ( 1) new-token & create-ref 3) token-created object home 1+---------------t:ommit recor (2) new-token & permit-create \Vhat is wrong '"'ith this approach? The basic problem is that it does not admit of any case where the requester is unaware whether or not the request he is sending involves the creation of a new token, or any case where the requester cannot knmv the name of the new tokens that are being created. If objects are implemented by an interface that hides their internal representation, then very commonly, the name used for the object by the requester will be quite different from the name(s) used for the object(s) that is(are) a part of the object's representation. So, for example, an individual's bank balance. may seem at some level to be a single object that can be changed by certain requests. However, internally. the balance may consist of several lower level abstract types of objects that are located at several nodes. A request to change the bank balance may involve updates to objects the requester never even dreamed existed, so there is no way to inform the commit record what objects may refer to it. In some implementations, such a request could involve creation and modifications of new objects, as well. These new objects would have to be created by the requester in order to make sure the commit record is properly informed. There are, however, techniques for reducing the number of individual create-ref /permit-create exchanges that occur as part and thus reducing delay as well as message traffic. discussed later as part of the section on "paging". ## 6.4 Non-cell object types of a composite operation, These techniques will be So far, with the new-token and lookup operations, we have the basic tools for implementing cells having load and store operations. Other types of objects, such as stacks, queues, accumulators, databases, etc. can be implemented using just cells as their basic tool for achieving mutability, but it may be that more optimal mechanisms can be used when the operations are more complex than simple load and store operations. A general class of object types for which particularly nice implementation techniques exist are called accumulator types. The best example of this kind of object is an integer cell that has operations like adding a constant to the cell, subtracting a constant from the cell, and multiplying the cell by a constant, none of which return a value, and another operation to obtain the value of the cell. Implementing such an object using the mechanism described so far requires that the operations on an object be performed one at a time, m the order of the pseudo-times assigned to the operations. Thus a delayed request to perform an operation on an object will be aborted if an operation at a greater pseudo-time was already executed. It is possible to implement the cell very efficiently by storing just the operation (add subtract or multiply) and the constant operand in each entry of a modified known history. A new token in the known history contains the operation and operand with the pseudo-time at which the operation is to be performed. That token becomes a version when its associated possibility is set to the complete state. The actual computation of the values resulting from the operations can be deferred until a value is actually requested. When the value of the cell is requested, however, it will be necessary to actually perform the computations requested by the operations whose pseudo-times precede the pseudo-time at which the value is requested. First, all tokens must be either aborted or become verswns. Then, starting with the oldest (in pseudo-time) version whose value has not yet been determined, the values of all versions whose range of validity precede the pseudo-time of the value request are computed. Since each version depends on the previous version, the range of validity of the previous version must be extended to close any gap in pseudo-time that may exist between successive versions. This implementation of the accumulator allows update operations to be performed without aborting each other if they happen particularly close together in time. The only time at which the update operations will be aborted in this scheme is when a value for the accumulator is desired. Then, any updates that have not yet been communicated to the accumulator home, but whose pseudo-times precede that of the value request, will be aborted. In general, an accumulator type is a type of object for which there are one or more operations that change the state of the object without returning any results that depend on either the old or new state of the object. The technique just described can always be used to implement such operations. The advantage is always that the update operations do not delay or abort each other. Disadvantages include more complex implementations of such objects and longer delay whenever an operation whose result does depend on the state of the object is executed. The accumulator implementation strategy is akin to a strategy often used to procrss updates like deposits to bank accounts -- the strategy of hatching updates together and performing them during slack time on the system unless there is an urgent need to determine the effect of the updates before such a slack time (usually overnight) comes about. The strategy is also a special case of "lazy evaluation" or "call by need". What NAMOS does is provide a framework for the synchronization of updates to an object so that the arrival order of update requests for an object is not significant in assuring that results are consistent. An interesting variation on the accumulator type is exemplified by the symbol table type. A symbol table has three operations, insert, which adds a new name and associated value to the symbol table, delete, which removes the entry corresponding to a name from the symbol table, and lookup, which returns the value associated with a particular name. To make the symbol table into an accumulator type, we must define the insert operation when the name already exists in the symbol table to change the associated value to the one specified in the insert; if an error were signalled in this case, the insert operation would have a result that depended on the state of the symbol table (error /no error). Similarly, a delete operation on a name that was not present would just return with no error. The techniques used above could be used to implement the symbol table as an accumulator; however, another technique could also be used. Suppose we were to choose a tree representation for the symbol table, with binary search to do the lookup. Imagine the symbol table as always containing all of the names e,·er to be used (inserted, looked-up, or deleted), and have a known history for e operation Is similar. except that instead of a new value, the reserved value indicating no value exists is to be placed in the known history. The lookup operation checks to see if either a normal value or the reserved value is associated with the pseudo-time of the request (extending the range of validity of an earlier value if necessary). If such a value exists, lookup returns it. If no version or token exists for the pseudo-time of the lookup or any earlier pseudo-time, the look up request creates a token with the reserved value as its value, and then returns the fact that the name is undefined. In this symbol table implementation, the arrival ordering of requests affecting diffrrent names is completely irrelevant. The only requests that can abort each other are requests with the same name. Were our original mechanism, or the accumulator enhancement just described, to be used, operations on different names could cause each other to be aborted. To do a lookup or insert in a binary tree composed of individual record objects whose updates are controlkd by NAMOS, the states of all records above the record containing the name referred to would have to be known, so operations on those names could be interfered with. A final example of interest is a FIFO queue type, with enqueue and dequeue operations. We assume that the enqueue operation does not return a value depending on the state of the queue (so a queue overflow error cannot be part of the interface). The queue object is an accumulator because of the enqueue operation, but, as with the symbol table, there is a better implementation. The important observation to make about the two queue operations is that when the dequeue operation executed in pseudo-time t' returns the value enqueued in pseudo-time t, the only knowledge that can be deduced knowing the results of dequeue operations thus far is the set of values enqueued in pseudo-times up to and including t. In particular, nothing is known about enqueues that may be executed between t and t'. This observation and the fact that values are returned in the order enqueued lead to a nice implementation. To represent the history of enqueue operations we use the same structure as a known history, where each known history entry has as its v<~lue part the value enqueued at its start pseudo-time. The enqueue operation is performed by adding a new token to this enqueue known history in the usual fashion. A second known history represents the history of dequeue operations. The values in this known history represent the pseudo-time at which the value dequeued was enqueued. Thus, the dequeue at t' above would result in adding an entry to the dequeue known history whose value was t, and whose start pseudo-time was t'. A dequeue operation works by first doing a lookup on the dequeue known history, to obtain the pseudo-time the value previously dequeued was enqueued. Then the enqueue known history is searched to find the entry with the earliest pseudo-time after that pseudo-time. If no entry is thus found, the dequeue operation returns an empty-queue error, recording the pseudo-time of the dequeue as a new token in the dequeue known history. Otherwise, the entry found contains the value to be returned by the dequeue, and the pseudo-time at which it is enqueued is recorded in the dequeue known history as a token with a start pseudo-time equal to the pseudo-time of the dequeue request. Before returning, the dequeue operation extends the range of validity of the preceding version in the dequeue known history to close up any gap. The resulting queue implementation, though complex to describe, allows enqueue requests to arrive in quite a different order than the assigned pseudo-times of the enqueues without aborting the enqueues. The queue type is particularly nice in this respect. Figure 16 illustrates the effect of a sequence of transactions on a particular queue. For simplicity, the pseudo-times in which the queue operations are executed are rendered as a pair of integers. The first integer is the pseudo-time in which the input state of the queue would be observed in ordinary implementations of the queue operations, while the second is the pseudo-time associated with the modification to be made to the queue. The enqueue and dequeue known histories are shown after each operation. The changes are highlighted by underlining. It is fairly easy to see that the arrival order of the queue operations is not severely constrained -- only the final enqueue shown is aborted because it arrives out of order with respect to its pseudo-time of execution. Of our three examples, the symbol table example has perhaps the largest practical importance, since our example symbol table could be generalized to any associative lookup mechanism, for example a large relational database. All of the optimizations described in this section, however, rely on the fact that the object implementation can be exclusively locked for the duration of the execution of an Fig. 16. History of several queue operations Operation State (PT) Value Enqueue Known History Enqueue Enqueue Enqueue Dequeue Enqueue Dequeue Enqueue Input Output Dequeue Known History A [ 11 I 11 ,A ][0,0,-] [0,0,0] B [ll,ll,A] [6,6,B][O,O,-] [0,0,0] C [21,2l,Cl [ll,ll,A] [6,6,B][O,O,-] [0,0,0] B [21.21,C] [11,ll,A] [6,6,B] [0.~.-] [22,22,6] [O.Il.O] D [25,25,0] [21,2l,C] [11,11,A] [6,6,B] [0,5,-] [22,22,6] [0,21,0] A [25,25,0] [21,21,C] [11,1l,A] [6,10,B] [0,5,-] [26,26, 11] [22,25 ,6] [0,21 ,0) E [25,25,0] [21,21,C] [ll,ll,A) [6,10,B] [0,5,-] [26,26,11] [22,25,6] [0,21,0] ... fails. because there is already a version in the enqueue known history valid in 8. Legend: Known History Entry [Start PT, End PT, Value] operation, so these tricks can be applied only to single node objects. ## 6.5 Creation and Deletion of Objects So far, we haven't yet discussed the mechanisms by which objects are created and deleted. In the following discussion, I assume that objects are explicitly deleted, so that a means for detecting "dangling references" must be provided. If some sort of automatic deletion of objects based on knowing that there will ne\'er be any references to an object after a particular pseudo-time can be provided, then the mechanism could be simplified by eliminating the need for detecting references to an object after it is deleted. Such an automatic deletion scheme would be hard to provide, however. First of all, NAMOS is intended to be used in 1 he decentralized multi-node environment described in chapter one. It would be rather difficult, and certainly rather expensive to provide a distributed garbage-collection algorithm, although a scheme based on reference counts might be a good \vay to begin, were the second complication to be described not to exist. Second, and perhaps more importantly, the automatic deletion algorithm must know, for each object reference to an object, what pseudo-times are to be used with that reference in order to refer to a particular version. By taking the least pseudo-time, L, that can still be used (either because it is still to be past in some executing computation's pseudo-temporal environment, or because it is stored in some checkpoint as suggested in chapter four) with any object reference, the system could construct the transitive closure of the refers-to relation, where an object refers to another if some version of the object valid after L refers to the other object. All objects reachable from executing computations in this closure cannot be deleted. Any components of the closure that are unconnected to existing computations could be deleted. This strategy for garbage collection is both difficult to implement in a distributed system, and does not guarantee to find all deletable objects. The important issue m creating and deleting objects is that the creation and deletion of an object has an effect on the observable behavior of an object in pseudo-time. Thus, the pseudo-time of creation of an object defines the earliest pseudo-time that the object can ever be assigned a value or read, while the deletion pseudo-time defines the latest such pseudo-time. Thus the known history as a whole must keep track of these times, once they are known. Consequently, the object header must specify the creation and deletion pseudo-times, once they are known. It is possible that an object is created by a composite operation that later fails. Consequently, the creation must be mediated by a commit record. The protocol mechanism for this is simple. Creation of an object occurs in a particular state, by the creation of the first token of a known history. The first token is special, in that it must be committed before any other operation on the object C Thus, in nddition to the creation pseudo-time, the object header must contain a flag indicating \vhether the object was really created. This flag simply encaches the commit state of the of the initial token. The encachement is necessary to allow the initial version to be eventually deleted, by the version deletion mechanism to be discussed. Deletion of an object does not imply the freeing of storage of the object, stnce there may exist requests yet to happen that will attempt to refer to versions of the object that correspond to pseudo-times earlier than the pseudo-time associated with deletion. If storage were immediately freed, then those requests could not be satisfied, an unfortunate kind of behavior. Consequently, deletion simply prevents operations at a later pseudo-time from the deletion from being able to access the object. A separate mechanism for deletion of individual versions will enable the eventual freeing of storage for the object. Deletion of an object requires care in implementation. Deletion of an object basically consists of freezing the evolution of the known history at a particular point -- however, the freezing must be mediated by a commit record. Deletion thus marks the object header as "potentially deleted," and saves the commit record pointer associated with the deletion and the pseudo-time of deletion in the object header. Later attempts to access the known history that would require that the cursor be advanced are delayed until the deletion is known to have happened (by the commit record entering the complete state) at which time the requests are denied. If the deletion fails (its commit record goes to the abort state), accesses past the pseudo-time of attempted deletion are permitted. As a result of the modifications made to the object header to handle creation and deletion, it now looks as shown in figure 17. The object header can be freed once it is successfully deleted by the above mechanism and all versions have been also deleted by the mechanism described in the following section. ## 6.6 Deletion of Object Versions Object ,·ersions may be deleted form the known history, thus reducing the memory needed to retain the known history. Certain restrictions apply. The main restriction is that once a version has existed for an object, no other version can ever be made valid in the range of validity of the deleted version. Fig. 17. Object header, revised to handle creation and deletion Object Header List of Known History Entries thread create PT created flag delete PT del~te commit rec. delete state Consequently, there must be some way to represent in the known history the ranges of validity of all versions that have ever existed. An approach that saves some of the storage associated with verstons ts to delete only the value associated with a deleted version, while keeping the known history entries and marking them as deleted. A deleted known history entry would then just be place holder, preventing new tokens from being created there. This approach is still inadequate because storage required for an object that can be updated remains unbounded. Essentially, the result of deleting verswns is to save space at the cost of possibly causing certain operations that are still looking into "old" states to fail. Depending on the characteristics of use of data, some rather flexible strategies can be used. For example, one may implement many of the objects in a traditional large data base such that all versions and tokens (except the most recent version) whose range of validity strictly precedes N seconds before the current real time are deleted. This strategy will work quite well if transactions against the data base are executed in environments whose input state corresponds to the real time the transaction began, and if all the transactions have a high probability of completing in Jess than N seconds. Implementing this strategy in the known history is quite simple. In the object header the value N would be stored, and any attempt to create a new token or lookup a ,·;due in a pseudo-time older than the current real time minus ~ would be prevented, giving an error message indicating that the version referred to no longer can exist. Versions and tokens whose ranges of validity end before the current real time minus N can be deleted when convenient. One other rule must be applied, in order to avoid losing the only version. The latest version and tokens with later pseudo-times may not be deleted, even if their ranges of validity lie before the current real time minus N, unless the object has been deleted. Thus we are assured that an attempt to get the current value (the value using the current real time as the pseudo-time of reference) will always succeed unless the object has been successfully deleted. A more restrictive strategy is to keep only the most recent version and later tokens. In high update traffic where occasionally there are long executing transactions that attempt to do a coherent query of many data base records, this may prevent these large coherent queries from being very likely to succeed. Howcn'r, this strategy is logically equivalent to a locking strategy, in that one is only guaranteed to be able to access the "current" version. Except in abnormal cases, only one token will exist, so this strategy can be viewed as a complete methodology for the distributed locking problem. As I noted in chapter four, I am aware of no other methodology that handles the problem of maintaining consistency by locking in a distributed data base in the case where arbitrary crashes and loss of messages can occur. Consequently, if the advantages of maintaining multiple versions, and supporting interfaces that work in environments that are unknown at design time, were not considered important, the methodology of this thesis still can be of great help in designing distributed data bases. In some implementations, old versions might never be deleted, but rather would be moved to some kind of write-once, low cost backup storage. Not only does this provide a complete audit trail of changes to the data base, but, as noted already in chapter four, it makes possible undoing later changes to parts of the data base where such changes may have resulted from user error. One can simply use the backup storage versions to retrieve old versions that are consistent in a particular state, and install them as the present state. Once a versiOn has been copied to backup storage, it doesn't really make sense for its range of validity to be changed. Consequently, to implement this strategy, the idea of using the value (real time)-N as a boundary before which tokens cannot be created and versions cannot have their ranges of validity chang('d is still important. This value is also used to select versions to move to backup storage. Versions are written into backup storage with associated information that specifies the range of validity. Since there may be holes between the versions put in backup storage, at the time each version is "frozen" for backup (when its end pseudo-time is less than (real time)-N), its range of validity is extended to include any following hole, in order to make sure that a backup copy exists for any pseudo-time that lies in the range from creation to deletion. If this strategy of keeping old versions in archival storage is used, it may be inappropriate to try to retrieve them for ordinary accesses because of excessive delay. Consequently, an appropriate mechanism must be used to distinguish references that are prepared to fetch from archival storage when necessary. A mechanism that is somewhat general is to specify how long a request is to wait for a value before it is declared inaccessible. The same mechanism would be useful for controlling the wait for a value that is on a node currently inaccessible due to a system crash or communications failures. It is important to note that applying these implementation techniques blindly to the queue implementation described earlier will result in bad behavior. The version deletion mechanism for the known history that represents the values enqueued must recognize that there are references in the known history containing the last dequeue pseudo-time that will be left dangling if the (real time)-N strategy is applied blindly to the enqueued values known history. The proper approach is to delete only those versions in the enqueued value known history that are not referenced by the last dequeue pseudo-time known history. 6. 7 Small Objects and "Paging" An attracti"e way of handling storage and encachement algorithms for related groups of small objects is "paging". Simply put, in paging a group of objects are handled as a single object for the purposes of synchronization and storage management (including encaching as noted in the previous section). In the model proposed here, it is possible to reduce the overhead of storing ranges of validity with object versions and keeping known histories by sharing rangt:>s of validity across multiple objects in a "page." This strategy is particularly inviting from the space reduction viewpoint when composite operations that affect most or all of the objects in a page are common. The basic mechanism is to maintain a known history for the page, consisting of page lWSions and rnc:c tokens. Every change to any object in the page causes the generation of a llt'W p<1ge version (although changes to multiple objects in the page that are effective in the same output state with the same commit record will result in only one new page version -- how this is achieved is described shortly). Every attempt to change an object will generate a new page token unless the correct one already exists. The only trick is managing the page tokens such that multiple changes to the page token are allowed. Our earlier protocol description for record objects would suggest that the second attempt to update the page token would be ignored as a duplicate request. In fact, we need a mechanism that allows multiple writes to the same page token if the writes are to disjoint objects. Basically, with the page token, we must keep a list of the objects for which new tokens are created, to which objects new update requests should be treated as duplicate messages. This list, like the pointer to the commit record, is not needed after the page token is committed. Use of pages introduces some restrictions. For example, creation, deletion, and relocation of individual objects on a page seems to be possible, but allowing for it greatly complicates bookkeeping, and may not be worth the trouble to implement. Howewr, creating, deleting, and relocating all of the page's objects as a group is quite simple. Perhaps the greatest advantage of the "paging" strategy in this system is that in creating a page token and then doing all of the later changes, only one create-ref /permit-create exchange need be done. Thus, if a number of objects are used to represent a particular abstraction that are usually all changed at the same time, the message overhead of communication with the commit record on each new-token request will be drastically reduced. ## 6.8 Copying of Object Versions Since object versions are immutable, they can be freely copied to nodes other than their home node. One rnight want to perform such a copy to optimize performance, where an operation needs to refer to a particular object quite frequently, yet the object changes (generating a new version) only rarely. There are, of course, other considerations that would argue against copying versions of objects -- in particular, the information hiding afforded by keeping the representation of the object only known at its home node, and the protection resulting from that information hiding that can restrict the ways in which the object can be inspected. However, given that copying is possible for the particular object, the system keeps enough information to allow the copying to take place. \Ve can view the copying of an object version as an encachement of the object, since the home of the object still contains the master copy of the versions of the object. When the object version is copied, it and the range of validity in pseudo-time of the object version are transmitted to the using system. At the using system, whenever a lookup request is requested for that object with a pseudo-time in the range of validity known to the using system, the copied version can satisfy the request. A small detail of the mechanism for encachement may not be obvious, though. In particular, object versions can be copied when the end of their range of validity is unknown, either because there is a token following it that has not been committed, or because no read has extended the range of validity up to the time of the next version. In either case, the full range of validity of the version is not yet known at the time of the copy. If a lookup request for the object is not in the range of an encached version, the encached version might not be useless. By augmenting the protocol for doing a remote lookup, it is possible to extend the range of validity of the encached version without the full cost of recopying the entire version. Basically, we add to the remote lookup request a parameter specifying the final time of the closest preceding encached version on the requesting site. The handler of the request may then need only to ship a special message that says, in effect, "your version that started at pseudo-time T is valid through time T'." Although this may not reduce delay, it certainly can help reduce the volume of network traffic. In fact, this will be a very common case, where multiple re!'d operations in successiYely later pseudo-times are issued at a site. An optimization that will reduce delay somewhat for this case would be to remember at the home site the locations of encached versions, to enable immediate transmission of the updated range of validity of encached versions. When new versions are created, the entire version could be shipped in the same way to the cache site. When a site no longer wishes to be a cache site, it should just forget about the encached object versions, and respond to updates with a no-cache(object) message, signalling the object home to remove from its memory the existence of the cache. Some applications of the encaching strategy seem to be extremely useful. For example, the strategy seems to be just what is needed for distributing new versions of programs. NAMOS is so easily extended to include encachement because the information needed to synchronize the encached copy with the master copy is already needed for maintaining inter-object consistency and proper synchronization. Encaching writable data in a database using locking for synchronization would not result in such a uniform mechanism. ## 6.9 Reducing the amount of work aborted \Vhrn an operation is aborted due to the failure of a new-token request, the oprration may have done a substantial amount of computation that will all have to be redone. This wasted work results from the fact that tokens are not created until it is known that a ne\v value ,·viii be assigned to a particular object, so another interfering computation may perform a read that extends the range of validity of an earlier version, preventing the creation of the token. If it were known in advance that a particular object will be updated by an operation, then a much better strategy would be to have the operation reserve the right to create a token in advance, and abort itself if that reservation cannot be made. It is not (llways possible. of course, to know what will be updated by an operation, so the case where such information is available should be treated as an optional optimization. A mechanism to make such reservations is fairly easily added to the system. A new kind of entity, a token reservation, ts the tool by which such reservations are made. A token reservation is represented by a known history entry that looks just like a token, but which has no value. A token reservation refers to a particular commit record, and may be deleted from the known history at any time -- its purpose is to mark the fact that a token may be created at some later time, but it does not guarantee that the token can be created. Of course, deleting the token reservation right away without giving the operation a chance to actually create the token obviates the purpose of. token reservations. The times when a token reservation ought to be deleted are (a) when the commit record enters either the aborted or completed state (if no token has been created by then, the operation will not ever attempt to create a token), or (b) after a sufficiently long time -- the timeout can be set to be some value greater than the timeout on the commit record, or (c) if the commit record has been deleted. Case (b) ensures that· the token reservation does not depend on the accessibility of the commit record for its deletion, while case (c) ensures that the commit record need not record references to it from token reservations, thus eliminating the need for create-ref /permit-create exchanges at the time token reservations are created. A token reservation is converted into a token when a new-token request specifying the same pseudo-time arrives at the home of the object. At that time, the create-ref /permit-create exchange of messages occurs. If a different commit record than the one under which the token reservation was created is specified in the new-token request, an error is signalled -- while this error signal is unnecessary (the token reservation is just an optimization), using different commit records is a misuse of the mechanism. The lookup request is affected by the existence of token reservations as if the token reservation were a token, with two differences. Before querying the commit record, the local timeout on the token reservation is checked, and if expired, the token reservation is deleted, and the lookup continues with the next previous version or token. Also, if the result of the query is a state("aborted") or a state("complete") message, the token reservation is deleted. Thus, a reservation is only held while the commit record remains in the wait state. The use of token reservations can help reduce the likelihood of dynamic deadlock in the system, as well. By making all of the token reservations as quickly as possible, the likelihood of having two conflicting operations that run at nearly the same time is reduced. by our assumption that conflicting operations are rarely close together in time. An even more potent strategy that can be used to prevent dynamic deadlock would be to define an ordering of objects, and to ask for the token reservations in all operations in a sequence that is a subsequence of the order on all objects. As it does in the case where one is requesting locks, this strategy would guarantee that in any conflict situation, at least one operation would be allowed to finish, eventually breaking the dynamic deadlock. I should reiterate here, hm-..·ever, that the use of token reservations ts entirely optional -- if they are used correctly they will improve the performance of individual operations in some cases, perhaps at the cost of reducing the performance of other operations. To show how other operations could be adn·rsely affected, consider the strategy of obtaining token reservations on all the objects that an operation might want to update, rather than just the objects that we are sure will be updated. Eventually, those objects that are not updated by the operation will delete the token reservations either due to timeout or detecting the completion of the operation's associated commit record. However, while the token reservations are around, they will slow down responses to lookups by forcing them to go look at commit records. Consequently, other operations that are later in pseudo-time than the one creating the token reservations may be delayed excessively as a result. Judicious use of token reservations is thus very important to good performance. ## 6.10 Summary In this rather long chapter, a number of mechanisms involved in the implementation of objects in the system have been discussed. The really important part of the system design is in the management of clocks and the generation of pseudo-time, and in the management of the known histories of objects. Although we have seen a number of optional enhancements, such as the encachement of objects, special representations for special types, and token reservations, the system without optimizations is sufficient by itself to solve a wide range of synchronization problems. # Chapter Seven: Conclusions and Directions In this dissertation, I have developed a new approach to the synchronization of accesses to shared data. In this chapter the key concepts, the range of applicability, and the limitations of the new approach are explored. Then possible directions for further development of this approach are suggested implementation, modification to remove limitations, and specialization of the approach for particular applications. 7 .l Concepts There are several key concepts that I would like to reemphasize by listing them here. They include a new view of the semantics of updates, the notion that abstractions must be preserved properly in an environment where concurrency, sharing, and failures are unavoidable, the close tie between synchronization and error recovery, and the idea of defining a system-wide state without reference to an instantaneous snapshot of the entire system. 7 .l.l Synchronization of shared data In the thesis \ve have concentrated our attention on one aspect of synchronization -- control of simultaneous accesses to shared data objects. It has been traditional to treat such synchronization with the same ideas and mechanisms as other problems of synchronization, such as disk queue scheduling and inter process control communication, 1 even though synchronization of access to data is a very simple and important case. The power of synchronization 1. Interprocess control communication (IPCC) is a generic term for mechanisms that allow one process to block itself when it has nothing to do, and be awakened by another process when something for it to do arrives. Although IPCC has been used in the implementation of mechanisms for controlling access to shared data, IPCC is more generally useful for controlling the timing of processes that must synchronize themselves for other reasons. mechanisms has been measured by determining what "synchronization problems" they can and cannot solve, v•here such problems usually have little to do with the very important case of access to data. As we have seen, by treating data synchronization alone, we need not be so concerned a bout the timing of programs accessing data, but rather we concern ourselves with the more relevant requirement that the program access the correct states of its data. The division of synchronization into two classes, data access synchronization and process (timing) synchronization, seems to be a useful and powerful division. 7 .1.2 New update semantics Our view that a data object really stands for a sequence of states and that accesses to the object (both read-only and update) are operations on that sequence is rather powerful. By defining a naming mechanism for selecting the point in the sequence of states to be operated on and allowing programs to use that naming mechanism, programs accessing shared objects can be defined without need to consider their timing. Since timing of programs is one of the attributes of program execution over which the designer has very little control, reducing the importance of timing in understanding the execution of programs simplifies the task of the designer. This view has also facilitated the ability to manage "out of date" states of data objects. By keeping states of a data object older than the current one, the system can allow more concurrency. In particular, it is not necessary for read accesses to an object to lock out subsequent writes. In a geographically distributed system, where delays are large, this locking introduces delay, since any write must delay sufficiently to determine that no remote computation has requested a read prior to the write. But since "out of date" versions are kept for a period of time, writes can be begun with confidence that read requests for an earlier version will not be interfered with. The ability to manage "out of date" states of objects also enables the encachement of objects to support frequent remote reading that was described in chapter six, and the restoration of old system states for the purpose of recovering from severe errors. It is interesting to note that our semantics ts somewhere between the traditional von Neumann machine semantics based on changeable memory locations and more recent "side-effect free" machine semantics best illustrated by dataflow machine architecture[Dennis75]. Although the objects implemented in ~A~IOS can be updated, they are built on a substructure consisting of immutable object rersions that correspond to the structured objects available in a dataflow machine. The immutability of object versions leads to the same advantage that is accrued from immutability of objects in a dataflow architecture, that the timing of concurrent programs is not important to the behavior of the program. However, by supporting an update semantics on top of the immutable versions, we support a user view of the system as being an extensive memory with state changing operations, a view that seems to be better for inter-user sharing. Thus we may have gotten the "best of both worlds." 7 .1.3 Abstraction and parallelism Updates to objects shared among parallel computations make it very difficult to construct programs out of modular parts. In non-parallel computations, one can view the execution of a subroutine as an operation whose internal implementation is largely invisible to its user. For example, a sorting routine can be thought of in terms of a rather simple specification that relates the states of its input to the ultimate outputs. The implementation of a sorting routine, on the other hand, can vary quite a bit while satisfying the same specification. In the case of parallel execution on shared data (unavoidable in the case of a multi-user database or file system), the semantics of a routine depends on the pattern of accesses made by the implementation of the routine, so it is possible to "look inside" an interface at the implementation by executing the routine in parallel with other computations that access the same data objects. Thus in the parallel execution of computations, the ability to construct abstract operations is severely curtailed. A partial solution to the problem of constructing abstract operations m a parallel execution environment is to add explicit locking to the language, so that a routine can gain exclusive control of a set of resources to inhibit concurrent access to the data it accesses. The solution is only partial, however, since it becomes necessary to include in the interface specification of a module what locks it needs set in order to use that module as part of a larger module that also needs to set locks. By exposing the set of resources that must be locked outside the module, the implementation is exposed in a slightly different way -- one need not try running computations in parallel to discover the implementation, since much of the structure of the implementation may be deduced from the resources it accesses. Our thesis is that it is both possible and extremely desirable to have system support for modules whose behavior does not depend on the behavior of programs accessing the same data concurrently. The designer and user of such modules need not concern themselves with parallel execution, locking, etc. in order to make sure the modules work as expected. In particular, the transaction pseudo-temporal environment and the dependent possibility support the implementation of such modulrs. Preserving the degree of abstraction afforded by a module interface has required that certain problems be solved that are normally very difficult to solve in a system that uses locking for synchronization. In particular, our approach to synchronization can handle cases where the data objects to be accessed by an operation are dependent on the input values to the operation. Predicate locking, proposed by Eswaran, et a/.[Eswaran76], attacks a similar problem, but still requires some care in specifying the class of objects that a program may access. 7 .1.4 Synchronization and Recovery from Failures In a system designed to be used in building modular abstract operations, both' the synchronization and recovery mechanisms must be designed to preserve the degree of abstraction provided by a module interface. Failures during the execution of a module may cause its implementation to become important to the users of the module, while failure of a module being used to implement part of a larger transaction must be reflected to the other parts of the larger transaction - undoing any changes that may have already been made if the failure requires that the larger transaction be aborted. Since both failure management and synchronization are tightly tied to the construction of abstractions, they must be carefully designed to work together . .Most of the attempts to solve the problems of synchronization assume that the problems of assuring reliability are solved at a lower level. While it is possible with enough redundancy to construct a system whose reliability is high enough that the likelihood of hardware failures can be ignored, it may be that the cost of achie,·ing reliable systems in this way is far higher than the cost of achieving reliability given knowledge about which parts of the implementation of the system must be reliable. Since we must already cope with unexpected loss of availability of objects and computational resources in a decentralized system (because of autonomy), handling failures of the communications system in the same way may achieve a cost saving by removing the need for a separate set of mechanisms to handle hardware failures. 7 .l.S System-wide state defined independent of time By defining a correspondence between the states of individual objects, we have defined a concept of a system-wide state, such that the system goes through a sequence of such states as a result of computations executing in the system. The mechanism for defining the correspondence, using pseudo-time, has the advantage that it is only loosely coupled with the passage of time. A definition of system state that uses time to relate states of individual objects runs into serious problems for several reasons. First, there is the problem that in a geographically distributed system, such a definition of a system state requires that to observe all the objects in a particular state, one must take a snapshot of all of the objects at an instant of time -- since communication delays in such a system make precisely simultaneous observations practically impossible, system states thus defined are not observable inside the system. A second problem is that the running of transactions concurrently in the system makes it very unlikely that the system state at any particular instant of time is consistent with some external ordering of actions. The result of this is that it is very hard to use that notion of system state in describing the behavior of programs to ensure that the system's behavior matches some external specification of correct operation. Such a definition of system state has led to the unsatisfying notion of defining a system as operating correctly in terms of its behavior after some "quiescing" action. For example, Thomas claims that his algorithm for synchronizing updates guarantees that if new requests to update are halted (the system is quiesced), the system will eventually stop in a state where all updates have been processed, in the proper order[Thomas76]. The problem with such a specification of a system is that the system may never be thus quiesced (an airline reservation system, for example, may always have several uncompleted seat reservation transactions for different flights in progress). In fact, a system may satisfy such a specification by entering a correct state only when the system is quiesced, but nonetheless processing all requests incorrectly! Our definition of system state, since it is independent of time, allowed the definition of consistent system-wide states without having to talk about quiescing the system. A transaction in progress in the system does not preclude an observable consistent state within NAMOS, since the transaction does not destroy the existing consistent state it observes as its input state, it only creates a new, presumably consistent state. ## 7.2 Applicability of the concepts In chapter one, we emphasized that the primary application of the ideas in the thesis is to the problems of synchronization and failure management in a decentralized, possibly geographically distributed, computer system composed of multiple. separately managed nodes sharing information via a communications network. Certainly the decentralized system application was the primary motivation for our work, but the ideas do seem to have wider applicability. Our approach to synchronization has been motivated by a particular desire to support modular design and implementation of programs, and we believe our approach is a quite effective way to manage synchronization and error recovery problems in a system where program development is decentralized to the point that there is no one central designer who specifies the set of atomic transactions that the system ,,·ill support. Even if the system were entirely confined within a single processor system, using shared secondary memory for the shared objects of interest, NAMOS seems to be a good way to support modular design. In such an application of NAMOS, the costs of managing individual object known histories, both 111 terms of space and time, can be controlled somewhat by an implementation specific to the single system case. Space can be conserved by storing only the most current version and at most one token for each object (requiring that an update arri,·ing at an object with a token outstanding \\·ait until the token is turned into a version or aborted). In the single system case, the complex protocols described in chapter five for recovering the storage for commit records need not be used because we can assume that the whole system is either up or down -- thus the commit record can immediately signal all tokens referring to it when it is completed, aborted or timed out. Similarly, in a single system, the system usually knows when a process is terminated due to some error, so in normal failures the aborting of the commit record(s) associated with a computation can be made to happen sooner by reflecting the failure immediately. The mechanisms of NAMOS can also be applied to solve synchronization problems where none of the problems of modular system construction exist. An example would be a "garden variety" database system used to support some sort of recordkeeping application such as accounting, payroll, inventory control, etc. In such applications, usually the whole system can be designed (by a "database administrator"), put into use, and will remain virtually unchanged for quite a long time. \Ve certainly don't need the ability to add new transactions dynamically to the set of transactions that can be executed. The advantages of NAMOS over other methods in these applications are that geographically distributed data can be properly synchronized, that both synchronization and error recovery do not require as large a design effort as would be needed if explicit locking and checkpointing had to be designed in, and that later modifications to add features to the system, if needed, will not require existing synchronization code (probably there is some such code in each module of the system) to be modified. For such a database system, :NAMOS can be simplified to reduce its complexity. Since support for modules as abstract operations is not needed in this application, dependent possibilities are unnecessary, and all transactions are created at the top level. If the database system is not distributed, then the optimizations noted above for the single-processor case can be applied. ## 7.3 Limitations \Ve cannot claim, however, that the ideas described here are universally practical. \Ve have made certain basic assumptions about the environment in which NA~IOS is to be used, and where those assumptions are violated, NAMOS works poorly, if at ail. A key assumption we have made is that the likelihood of two transactions concurrently accessing the same data is reasonably small. If this assumption is not true. then tr<1nsactions that read values out of objects will with high frequency cause transactions that perform updates on the same objects to be aborted. Although our assumption is true in many systems that allow sharing of objects, some systems do manage such objects that have high rates of contention; those systems may need additional mechanisms to support their concurrency control. Essentially, in the case of high contention, a more efficient way to do business is to schedule conflicting transactions so that one transaction completes its accesses to the shared data before any later ones are allowed to proceed. NAMOS's mechanism of token reservations, described in chapter six, serves as a kind of scheduling mechanism. but since it requires reservations to be made for all objects to be touched it may be quite costly in terms of communications overhead. An alternative, more centralized, scheduler could be designed that ordered transactions based on high-level knowledge about which transactions are likely to conflict. Of course, such a scheduler must be designed to deal with failure of a transaction, so that such a failure does not prevent later transactions from being scheduled. The mechanisms of NAMOS will still be useful in a system with such a central scheduler. NAMOS's recovery mechanisms still provide a good way to deal with failure of transactions. The synchronization mechanisms of NAMOS can be thought of as dynamic verification that proper synchronization is being achieved by the central scheduler, such that if the central scheduler erroneously schedules two transactions acting on the same data at the same time, the NAMOS mechanisms will ensure consistency or abort one or both of the transactions. In fact. this suggests an interesting strategy for the design of a central scheduler. Instead of being conservative, always deferring one transaction whenever there is the slightest chance that two transactions will conflict, the central scheduler can be more optimistic, and only defer a transaction when it has a high chance of conflicting v•ith one already executing. The basic mechanisms of NAMOS then ensure proper synchronization and recovery, while the central scheduler optimizes performance, increasing the chances of proper termination of transactions. ## 7.4 Directions for further research So far, we have seen a relatively complete design for a mechanism to handlr the problems of synchronizing and managing failures of accesses to objects. It is. however, only a paper design, so many of the aspects of its performance and usability can be characterized only qualitatively. Constructing a prototype implementation for the purpose of evaluating its implementability, performance, and usability seems to be the obvious next step. The full NAMOS system need not be constructed for some of its attributes to be evaluated. A first step would be to replace the transaction synchronization and recovery mechanisms of some ex1stmg database system with the synchronization and recovery mechanisms of NAMOS. The objects of the system would be the data records or relation tuples maintained by the data management system. The transactions of the data management system would be implemented as computations executing in a transaction pseudo-temporal environment. This would serve as a test of the performance of NAMOS. An extension along this direction would be to distribute the database (requiring a way to decide where a particular record or tuple is located), so that communications failures, and perhaps autonomy, can be incorporated into the substrate on which the NAMOS mechanisms operate. A test on an existing database system would not show the usability afforded by NAMOS's support of modular construction methodologies. To test these features, a more interesting use of NAMOS would be required. One possible application of NAMOS would be in the construction of a decentralized network of "personal computers" where a strong need to share permanently stored data is needed. One kind of data that might be shared among such a set of computers would be useful user-written and maintained programs, such as sophisticated editors, compilers, etc. Small databases, such as files of papers in progress (i.e. journal articles or letters), annotated bibliographies, etc., might also be structured objects that are shared. It is reasonable to assume that such shared objects will occasionally be updated by the provider or users of the objects, so there will be problems in managing the concurrent accesses to the objects that are likely to occur. The mechanisms of NAMOS can be used to manage such sharing. Another possible test of the ability to build modular systems in NAMOS \vould be to build a continually modified database system (such as, for example, a system like that the :'vl.I.T. registrar uses to keep track of the subjects taken, grades. and other information it keeps about each student -- this system needs to be changed regularly as the rules and structure of M.I.T. change) using NAMOS. One could then see if the tools provided by NAMOS lead to a simplification of the task of modifying the system to incorporate new features. A direction for exploring the issues surrounding NAMOS that is more speculative is to incorporate the synchronization and failure recovery semantics of NA\-IOS directly in the computational model of some computer design. Such a direction is not without precedent. Randell has explored a similar direction in de,·eloping a hardware support for recovery blocks[Randell75], and numerous hardware designs have incorporated synchronization mechanisms such as semaphores. The advantage of directly implementing the NAMOS synchronization and reliability mechanisms in hardware is performance. The algorithm that finds the correct version of an object given a version reference composed of an object identifier and pseudo-time should execute as fast as possible, since it is used on every access to an object. Similarly, defining a new version must be as fast as possible. In a distributed system, where the time to access an object is controlled primarily by communication delay, accessing and updating objects using the mechanisms of NAMOS may not be very costly, but using NAMOS inside a single system for purely local operations might be rather costly if NAMOS is implemented entirely in software. The attributes of NAMOS, particularly the support of modular synchronization and reliability, make it otherwise attractive for synchronization of accesses purely local to a single system. Incorporating the basic operations of NAMOS in a computer design, using special hardware designed to optimize the naming of versions, would make NAMOS attractive in such a case. Other future research could be directed at removing the major limitation of NAMOS -- that it can't handle a high degree of contention among the transactions acting on a particular object. We have suggested above a strategy that mixes together NAMOS and some sort of centralized transaction scheduling discipline. This approach must be explored in more detail to see if it does fulfill its promise of supporting high-contention situations. Another related idea that can r~''':~""~~~-'".-:~•c•~~~~~~~-, -··;··---~-~~~~I:,I\!I,Jifllftli,-.c?:~ii! I''- ! ---··-·:· - ... kal at Uti~" pi-( .... ~'-~ t$( ----J-1 ~ - -_:; - # Appendix A: Analysis of Availability of Multi-site Possibility To show that the multi-site possibility provides more accessibility than a single site possibility, an analysis of the probability of availability is needed. Here I include an analysis based on some simple, but reasonable assumptions about the ~n·ailability of sites and reliability of messages. I lump site availability and lost message probabilities together, and assume that all sites behave the same. First, consider a test of the state of the whole commit record. If the test does not make a decision within .,. seconds, the commit record is considered to be unavailable. Each voter site is assumed to behave similarly when its state is polled, providing a response saying whether the voter is complete or aborted within time r with probability q. The value of q includes both the probability of site inaccessibility and the probabilities of transient loss of messages to and from the site. When a complete or abort operation is attempted, we assume that there IS no problem with interference from local voter timeouts (we assume the probability of this is negligible, because of the trick described above). If some individual site does not acknowledge an attempt to complete or abort it within time .,.·, the requesting site gives up. The probability that a site does not process a complete or abort sent to it within time r • is p. The probability p again includes both the probability of message loss and the probability of site failure or inaccessibility. Finally, we assume that the requesting site sends out the messages sequentially, and may fail in between any of the N messages. To characterize the probability of failure. I assume that with probability 1-

~ow let us consider the problem of accessibility. What we want to know is the likelihood that some attempt to test the state of a commit record will be unable to decide the state of the commit record within time r. There are two cases, depending on whether there was an attempt to complete the commit record or not. If a complete was attempted, the probability that a tester will not be able to decide we call P cfail• and if no complete was attempted, we call the probability of not deciding Pafail· For a single-site commit record, P cfail=P afail=l-q. For a multi-site commit record, the situation is more complex. Pafail for a multi-site commit record is the easiest case. To decide that the commit record is aborted, at least N-K+ 1 sites must respond. The probability of N N this is 1: ("i) qi(l-q)(N-i). Thus, Pafail is the probability that at most N-K i=N-K+ 1 sites respond. N-K p afail = 1: (~) qi(l-q)(N-i). i=O P cfail is more complex. If an attempt to complete the commit record has been made, there is some probability distribution among the states that the voters may h;n-e reached that depends on p and . The probability P cfail can be expressed as 1-Pc-P A· where Pc is the probability that the tester will decide that the commit record is completed, and P A is the probability that the tester will decide that the commit record is aborted (these are clearly mutually exclusive, so with P cfail the probabilities sum to 1 ). Each voter can be viewed as an intermediate station in a message transmission from the complete request to the tester of the commit record. The probability that a message sent by the requester will get to the tester is pq. If we assume that the requester got to send exactly k messages before failing, then the probability that the tester will decide that the commit record was completed is Qk = .~ (~)(pq)i(l-pq)k-i. The probability that t=K the requester got to send exactly k messages, once deciding to attempt to complete, is cflN if k=N, and k(l-) otherwise. Thus, N-1 Pc = N QN + 1: k(l-<1>) Qk. k=K Similarly, g1ven that k messages were sent by the requester, the tester has a certain probability of determining that N-K+l voters are in the abort state. Now we ha"e two cases. Among the k sites that messages were addressed to, some of the sites will enter the aborted state because of messages lost with probability ( 1-p ), but will supply an answer to the tester. For any of the k sites, this will happen with probability (1-p)q. For the other N-k sites, the aborted state is guaranteed to be entered, and the probability that the tester gets an aborted response 1s 4· Thus, the probability that the tester gets exactly i aborted responses IS min(i,N-k) N-k . N-k-. k i-. k-i+. Ti k = L: ( j )qJ( 1-q) J(i-j)((l-p)q) J(l-(1-p)q) J. ' j=max(O,i-k) · So. the probability of getting at least N-K+ 1 responses that say abort, given k messages sent is N Rk = L: Ti k· i=N-K+l ' Consequently, we can compute the probability of deciding aborted as N-1 p A = ct>::'JRN + L: ct>k(l-)Rk. k=O The expression for P cfail is thus quite complicated, and doesn't seem to be amt."nable to simplification. However, I have shown by experimentation with reasonable values of p, q, and ct> that values of N and K other than one (the single site case) can give either improvements in availability of the commit record's state, or can reduce availability. A sample graph of the variation of P cfail as N varies owr odd numbers of sites from 1 to 15, holding p, q, and ct> all constant at 0.9, and with K=(~+l)/2, is shown in figure 18. Improvements result because the expected number of sites to respond completed is about pqN (as it would be if <1> were one), then as N becomes large, the probability that K= ol.N (where ~ Fig. 18. G rnph of P cfail as the number of sites varies 0.1 X X X X Pcfail 1 5 7 X N X X X The overall availability of a possibility depends on the likelihood that opera1 ions that are controlled by it will fail to finish before attempting to complete. This likelihood is strongly application dependent, and cannot be determined by the system. If it were known, however, a reasonably optimum choice of N and K could be made. One factor ignored so far is the delay and cost of message traffic needed to achieve a particular level of reliability and availability. It is clear that one can improve p and q by increasing potential delay (by, for example, retransmitting requec;ts periodically). Similarly, increasing N can increase the message traffic in the network, and possibly indirectly add queueing delay. Varying K can reduce or increase the delay before deciding that a commit record is complete, while affecting the delay for deciding the same kind of commit record is aborted in the opposite direction. i-; By keepiaa ~N/21. Md bipfli~H~itiiJ{fft)."-:l). tile •n•• 4e1ays. and costs can be ltept...U. •-tile ,.,. • .,._.., aotttthtedliJI.r.._ d be optimized .... ia ..................... . ,."P~ ~,a-.'(1 .. ____ -~~-,~ -at~ 1>nA _ ----~ ... -.. ~-.. -,_~ ## References [Alsberg76) Alsberg, P.A., Belford, G.G., Day, J.D., Grapa, E., "Multi-Copy Resiliency Techniques," CAC Document # 202, May, 1976. [Atkinson78] Atkinson, R.A., and Hewitt, C.E., "Specification and Proof Techniques for Serializers," Draft, March 20, 1978. [Backus78] Backus, J., "Can Programming be Liberated from the von Neumann Style? A Functional Style and its Logic of Programs," 1977 ACM Turing Award Lecture, published in CACM 21, 8 (August 1978), pp. 613-641. [Bernstein77] Bernstein, P.A., Shipman, D.W., Rothnie, J.B., and Goodman, N., 'The concurrency control mechanism of SDD-1: A system for distributed databases (The general case)," Computer Corporation of America technical report CCA-77-09, December 15, 1977. [Bobrow72) Bobrow, D., et al., "TENEX - a paged time sharing system for the PDP-10," CACJI 15, 3 (March 1972), pp. 135-143. [Corbato65] Corbato, F.J., and Vyssotsky, V.A., "Introduction and overview of the MUL TICS system," Proceedings of the AFIPS 1965 Fall Joint Computer Conference, Vol. 27, Pt. I, AFIPS Press, Montvale, N.J. pp. 213-230. [Crocker75] Crocker, S.D., 'The National Software Works: A new method for providing software development tools using the ARPANET," Proc. Meeting on 20 years of Computer Science, Pisa, Italy, July 1975. [DOliveira77] d'Oli"eira, C.R., "An Analysis of Computer Decentalization,'' M.I.T. Laboratory for Computer Science Technical Memo TM-90 (October, 1977). [Davies73] Davies, C.T., "Recovery semantics for a DB/DC system," Proceedings of the 1973 ACM National Conference, New York (1973), pp. 136-141. [Dennis75] Dennis J.B., "First Version of a Data Flow Procedure Language," M.I.T. Laboratory for Computer Science Technical Memo, TM-61, May 1975. [Eastlake69] Eastlake, D., et al., ITS 1.5 Reference Manual, M.I.T. Artificial Intelligence Laboratory Memo AIM-161A, July 1969. [Eswaran76] Eswaran. Gray, Lorie, Traiger, "The Notions of Consistency and Predicate Locks in a Database System," CACM 19, 11, November, 1976. [Frankston74] Frankston, R.M., 'The computer utility as the marketplace for computer services," M.I.T. Laboratory for Computer Science Technical Report TR-128 (1974). [Gaines72] Gaines, R.S., "An Operating System Based on the Concept of a Supervisory Computer," CACM 15, 3 (March 1972), pp. 150-156. [Goodenough75] Goodenough, J.D., "Exception Handling: Issues and a Proposed Notation," CACM 18, 12 (December 1975), pp.683-696. [Gray77] Gray, J.N., "Notes on Data Base Operating Systems," Operating Systems: An Advanced Course, in Volume 60 of Lecture Notes in Computer Science, Springer-Verlag, 197 8, pp.393-481. [Henderson75] Henderson, D.A., 'The Binding Model: A Semantic Base for ~Iodular Programming Systems," MIT-LCS TR-145, February, 1975. [Hewitt76] Hewitt, C., "Viewing Control Structures as Patterns of Passing Messages," M.I.T. Artificial Intelligence Laboratory, A.l. Memo #410, December, 1976. [Hewitt77] Hewitt, C. and Baker, H., "Laws for Communicating Parallel Processes," Proc. IFIP 77, August 1977. [Hoare74] Hoare, C.A.R., "Monitors: an operating system structuring concept," CACM I 7, 5 (October 1974), pp. 549-557. [Johnson75] Johnson, P.R. and R.H. Thomas, "The Maintenance of Duplicate Databases," ARPANET NWG/RFC #677, January 1975. [Kent76] Kent, S. T., "Encryption-Based Protection Protocols for Interactive User-Computer Communication," MIT-LCS TR-162, May, 1976. [Lamport78] Lamport, L., "Time, Clocks, and the Ordering of Events m a Distributed System," CACM 21, 7 (July 1978), pp.558-565. [Lampson76] Lampson, B. and Sturgis, H., "Crash Recovery in a Distributed Data Storage System," Xerox Palo Alto Research Center, Ca. November, 1976. To appear in CACM. [Levin77] Levin, R., "Program Structures for Exceptional Condition Handling," Ph.D. Thesis, Department of Computer Science, Carnegie-Mellon University, June 1977. [Liskov76] Liskov, B.H., "A note on CLU," CSG Memo # 136, M.I.T. Laboratory for Computer Science, February. 1976. [Liskov77a] Liskov, B.H., et al., "Abstraction Mechanisms in CLU," CACM 20, 8 (August 1977), pp. 564-576. [Liskov77b] Liskov, B.H., and Snyder, A., "Structured Exception Handling," M.I.T. Laboratory for Computer Science Computation Structures Group .Memo 155, December, 1977. [Liskov78] Liskov, B.H., et al., "The CLU Reference Manual," CSG Memo # 161, M.I.T. Laboratory for Computer Science, July, 1978. [Metcalfe73] Metcalfe, R.:M., "Packet Communication," M.I.T. Laboratory for Computer Science Technical Report TR-114 (December 1973). [.Metcalfe76] I\.fetcalfe, R.M., et a!., "Ethernet: Distributed Packet Switching for Local Computer Networks," CACM/9, No. 7, pp. 395-404, July, 1976. [Randell75] Randell, B., "System Structure for Software Fault Tolerance," IEEE Transactions on Software Engineering, SE-1, 2 (June 1975), pp. 220-232. [Ranclell78] Randell, B., Lee, P.A., and Treleaven, P.C., "Reliability Issues in Computing System Design," ACM Computing Surveys 10, 2 (June 1978), pp.l23-166. [Reed78) Reed, D.P., "Synchronization with Eventcounts and Sequencers," to appear in CACM. (Presented at Sixth ACM Symposium on Operating System Principles, November 1977). [Rothnie77] Rothnie, J.B., Bernstein, P.A., Goodman, N., and Papadimitriou, C.A., "The Redundant Update Methodology of SDD-1: A System for Distributed Databases," Computer Corporation of America Technical Report, February, 1977. [Saltze>r78] Saltz.er, J.H., "Research Problems of Decentralized Systems with Largely Autonomous Nodes", Operating Systems Review 12, 1 (January 1978) pp. 43-52. [Thomas76) Thomas, R. H., "A Solution to the Update Problem for Multiple Copy Data Bases Which Uses Distributed Control,'' BB:N Report #3340, July, 1976. [VanHorn66) Van Horn, E.C., "Computer Design for Asynchronously Reproducible Multiprocessing," Ph.D. thesis, M.I.T. Department of Electrical Engineering. Also available as Project MAC Technical Report TR-34, from the M.I.T. Laboratory for Computer Science. [\Vulf7 4) \Vulf, \V.A., "ALPHARD: Towards a language to support structured programming," Carnegie-Mellon University Dept. of Computer Science, April 197 4. [Wulf75] Wulf, W.A., Levin, R. and Pierson, C., "Overview of the Hydra operating system development", Proc. Fifth Symposium on Operating Systems Principles, 131, November 1975. :$k£QHho'1Q'Jl·~~·.YJl.qp~.:lltiU f&#il13~ lo t®~ni~ ~TJM ~Jl ~T ~· .·t=icn1 ~be~ 101 tto.J~fl4~-- ~tHJU& ··~· ## Biographical Note David Patrick Reed was born on January 31, 1952, in Portsmouth, Virginia. He grew up in Norfolk, Virginia, in Watertown, Massachusetts, in Kittery, Maine, in Jacksom·ille, Florida, in Edison, New Jersey, in Alexandria, Virginia, and in Hingham. ~Iassachusetts. He graduated from Hingham High School, Hingham, :Y1ass .. in 1969. He received both the Rensellaer Medal Award and the Bausch and Lomb Science Medal at that time, and was a member of the National Honor Society. From 1969 1o 1978 he has attended the Massachusetts Institute of Technology, receiving a host of degrees. His undergraduate education was supported by a National }.1erit Scholarship and an American \Vater Works Foundation Scholarship. He received the B.S. degree from the Department of Electrical Engineering in June, 197 3. His B.S. thesis was entitled "Estimation of Primary Memory Requirements for Processes in Multics." As a graduate student at \1.1.T., he was supported as a research assistant in the Computer Systems Research Group of the M.I.T. Laboratory for Computer Science, and as a teaching assistant in the Department of Electrical Engineering and Computer Science. He received the S.M. degree from the Department of Electrical Engineering and Computer Science in August 1975 and the Electrical Engineer degree in January 1976. His S.M. and E.E. thesis was entitled "Processor ~1ultiplexing in a Layered Operating System." He received the Department of Electrical Engineering and Computer Science Teaching Award in May 1975. As an undergraduate student, Mr. Reed, along with a group of three other students, designed and implemented the Multics version of the MACLISP interpreter and compiler for the LISP language. He also participated in the design and implementation of the Multics operating system carried out at Project MAC at M.I.T. He has also worked at the IBM San Jose Research Laboratory during the summer of 1975. :'vir. Reed is a member of the Association for Computing Machinery, and its special interest groups on Operating Systems, Programming Languages, and Communications. He is also a member of the Sigma Xi scientific honorary society, and the American Association for the Advancement of Science. In September, 1978, Mr. Reed assumed the rank of Assistant Professor. of Computer Science and Engineering at the Massachusetts Institute of Technology. He is married to Lynn Susan Reed, and has one son, Colin Alexander Reed. Mr. Reed's publications include: David P. Reed and Rajendra K. Kanodia, "Synchronization with Eventcounts and Sequencers," to be published in CACM. David D. Clark, Kenneth T. Pogran, and David P. Reed, "An Introduction to Local Networks," to be published in IEEE Proceedings. This empty page was substih1ted for a blank page in the original document. CS-TR Scanning Project Document Control Form Report # L.c.s -TP-...-l. DS Date : ... h . ../ I;)_ I qs· Each of the following should be identified by a checkmark: Originating Department: D Artificial lntellegence Laboratory (AI) .)(Laboratory for Computer Science (LCS) Document Type: ~Technical Report (TR) D Other: D Technical Memo (TM) ---------------------- Document Information Number of pages: f~J.-( IZg~ /rrlf/~i:-s) - Not to include DOD forms, printer intstruetions, etc ... original pages only. Originals are: D Single-sided or .)( Double-sided Print type: 0 Typewriter 0 Offset Press Intended to be printed as : D Single-sided or )(Double-sided D Laser Print D InkJet Printer )z(_ Unknown 0 rnner: __________________ __ Check each if included with document: D DODForm ~Spine D Other: 0 Funding Agent Form 0 Printers Notes -------------------------------Page Data: )( Cover Page D Photo negatives Blank Pages(by.-oenumbe<): J0 if(. iD'l !C-3, 17'/-, /'8CI ;:,PC fRl?~ F,J....i;,:'J;,vrr: ("!!, "' )J 7 ' Photographs/Tonal Material (by.-ue number): ________ _ Other <,.,.. clesaiptionlpag number): Description : Page Number: . ::ftnac;-r f'rl~~: (1-1~).... -) e&tvifJ'"'o TITutrs«. ~-lb'f;c.trJ-it~ BLANk J J (ro- ~~~ 2 5, 61 ,..€oNTholy c;o v~Sf[l\la !f'GI~(i) ; J Scanning Agent Signoff: Date Received: J!._tll. l_jl_ Date Scanned: ...!!._1 Jo /~S .. Date Returned: _1_1 1 _9_t qs- ~~~~-~ Scanning Agent Signature:. ______ ~<-..:....:=t....l-~~~~.L.;;...;~.....lo<:~LLI,,....p.-- ROOY 9i8o4 DSII.CS 0oc:ument Conlrol Form csbfoml. vsd Scanning Agent Identification· Target Scanning of this document was supported in part by the Corporation for National Research Initiatives, using funds from the Advanced Research Projects Agency of the United states Government under Grant: MDA972-92-Jl029. The scanning agent for this project was the Document Services department of the M.l. T Libraries. Technical support for this project was also provided by the M.I.T. Laboratory for Computer Sciences. darptrgt.wpw Rev. 9/94 ----- ERROR NOTICE ----- Sorry, this page (numbered 96) was missing from the archive of scanned page images for LCS- TR-205. We are attempting to restore it. For now, please see the MIT Thesis form of this document in the Theses digital library, http:/ /theses.mit.edu/, document I978-38. Since the pagination is different, see pages II6 and II 7 in the thesis.