first acquire the lock associated with it. This lock is held until the iteration terminates, at which point the iteration releases all of its locks. If an iteration is unable to acquire a lock on an object, this means that a second iteration is currently accessing the object, and one of the two iterations must be rolled back. Rollbacks are accomplished by copying an object before it is modified, and restoring from that copy upon rollback. Thus, in a system in which all objects use the catch-and-keep policy, serialization of iterations is easy to ensure. Acquiring and releasing locks, making backup copies of objects, etc., is performed automatically by our run-time system, as explained in Section 3. 3. It is also possible to use hardware transactional memory (TM). 7

While catch-and-keep classes are simple to implement, they may not provide enough concurrency. Work-sets are themselves data structures, and they are implemented using classes in the Galois library. Since each iteration gets an element from the work-set at the beginning and may add elements to it at the end, a catch-and-keep implementation of the work-set class would permit only one iteration to execute at a time.

Catch-and-release Classes: To solve this problem, the Galois system supports the catch-and-release policy for concurrently accessed objects such as the graph and work-set in mesh refinement, or the kd-tree in agglomerative clustering. To access a catch-and-release object, an iteration must acquire the lock on the object. However, unlike in catch-and-keep, the lock is released as soon as the method completes. Releasing the lock allows interleaving of method invocations from different iterations, which increases concurrency.

The key problem in catch-and-release is to ensure that the method interleavings do not violate serializability of iterations. This is nontrivial, as demonstrated by the programs in Figure 7, which show iterations manipulating a set that supports add, remove, and contains, with the standard semantics. In Figure 7(a), we see that in any sequential execution, the call contains(x) will return false. However, for the interleaving shown in the figure, the call will return true. On the other hand, for the program in Figure 7(b), all possible interleavings of the methods match a serial execution. For a catch-and-release object,

figure 7. interleaving method invocations from different iterations.

Set S

S.add(x)

S.add(x)

Set S

S.contains?(x)

S.contains?(y)

S.remove(x)

S.remove(x)

(a)

(b)

how can we determine which interleavings are legal, and which should be disallowed?

The key is semantic commutativity, described at the beginning of this section. Method invocations to a given object from two iterations can be interleaved safely provided that the final abstract state is consistent with some serial order of iteration execution. In Figure 7(a), the invocation contains(x) does not commute with the operations from the other thread, so the invocations from the two iterations must not be interleaved. In Figure 7(b), contains(y) commutes with the other operations, so the iterations can execute in parallel. Note that commutativity may depend on the arguments or return values of methods.

Because iterations are executed in parallel, it is possible for commutativity conflicts to prevent an iteration from completing, requiring that iterations be rolled back. Because semantic commutativity does not track the concrete state of an object, simply creating copies of the concrete state (as in catch-and-keep classes) does not suffice. Instead, every method of a catch-and-release object that may modify the state of that object must have an associated inverse method that undoes the side-effects of that method invocation. For example, for a set that does not contain x, the inverse of a method invocation that adds an element x to a set is a method invocation that removes it from that set. As in the case of commutativity, what is relevant for our purpose is an inverse in the semantic sense; invoking a method and its inverse in succession may not restore the concrete data structure to what it was.

Note that when an iteration rolls back, all of the methods which it invokes during roll-back must succeed. Thus, we must never encounter conflicts when invoking inverse methods. When the Galois system checks commutativity, it also checks commutativity with the associated inverse method.

Putting It All Together: ADT commutativity and undo must be specified by the class designer. Figure 8 illustrates how

figure 8. example Galois class for a set.

class Set {

//interface methods void add ( Element x );

[ commutes ]

— add ( y ) { y != x }

— remove (y) {y != x} — contains (y) {y != x}

[ inverse ] remove (x) void remove ( Element x );

[ commutes ]

— add ( y ) { y != x }

— remove (y) {y != x}
— contains (y) {y != x}
[ inverse ] add ( x )
boolean contains ( Element x );
[ commutes ]

— add ( y ) { y != x }

— remove (y) {y != x} — contains (*)//any call to contains