Question whether a problem with race conditions exists in this case

[Saxo]

     You'll still have the problem that threads T1 and T2 could get()
different values from the same Node, and both be working with those
conflicting values at the same time.  An "instantaneous" change will
not avoid the issue -- so either (a) it better not be an issue, or
(b) you need The Mother Of All Locks around the whole shebang ...

     Also, the problem ordinarily addressed by a "commit" mechanism
is somewhat different: You want to make changes to Nodes N1 and N2,
and you want to make sure an observer sees either the two old values
or the two new values, but never a mixture.  Again, "instantaneous"
change won't solve the problem, not even in the simple case of just
one mutator and one observer:

        Observer: Fetch the N1 value, then ...
        Mutator: CHANGE THE WORLD INSTANTANEOUSLY
        Observer: ... fetch the N2 value

For the observer's view of N1 and N2 to be consistent, it's not
enough that each get() be guarded against interference; you need
the pair of get()'s guarded as a unit.  Very likely, you also need
the changes to N1 and N2 guarded as a unit.

Eric Sosman

All right, I see that the issue cannot be understood without
explaining mmore of the whole thing. What I want to develop is a
transactional concurrent map that is protected by an optimistic
locking mechanism. For every such map there is backing map that
carries the consistent snapshots from commit to commit. The user
interacts with the backing map through a locle cache:

BackingMap backingMap = new BackingMap();

LocalMap map1 = new LocalMap(backingMap);
map1.begin();
Node node1 = map1.get(key1); // line x - this is the get from my
initial post, augmented by a key for the map value lookup
Node node2 = map1.get(key1); // line y
node2.value = newValue;
Node node3 = map1.putAndGet(key1, node2);
map1.commit(); // or map1.mergeCommit();

The node objects hold a lock counter to determine whether an
optimistic locking conflict has occured. When map1.get(key) is done
the node object from the corresponding node object in the backing map
is copied and returned. It is then stored in the local cache with the
lock counter in the state when the original node from the backing map
was copied. When another time get is done as in line y, the same value
is returned as in line x even when it has meanwhile changed in the
backing map as on a repeated get for a node already in the local
cache, only the node in the local cache is returned. You can think of
adding a getRepeatableRead(key) method that refetches the current
value from the backing map with the current value of the lock counter.
But this is something for later considerations.

Until the commit is done all changes are held in a local change list.
When the commit is done, the >single< committing thread checks for
every change object in the change list whether the lock counter is
still the same as in the backing map. If so, the values of the change
list are transfered to the backing map as explained in my initial
post. If not, an optimistic locking exception is thrown and the local
change list is thrown away. In case of map1.commit() the commit fails
in case the backing map has changed in any way whether this concerns
the value for key1 or not. In case of map1.mergeCommit() the commit
only fails if the value for key1 has changed meanwhile from within a
different thread.

I now need to return to the get method of my initial post:

public Object get() {
synchronized(lock) {
if(useNewValue.get()) // 1
return newValue; // 2
return previousValue; // 3
}
}

Let's say the map1.commit() is done as in the example at the beginning
of this post. During the commit phase some other thread x calls
get(key1). When for the commit no optimistic locking conflict has been
detected and the new values have been transfered from the change list,
the atomic boolean useNewValue is set to true. Let's say at this time
thread x were in line 3 (see line numbers in the example above). Then
the meanwhile outdated value previousValue would be returned. But
strictly speaking, chronologically thread x has by passed line 1 at
the time useNewValue was changed to true. So seen from this
perspective there is no true race condition here. Now, if we assume
that what is returned from the synchronized block must be inline with
the value in the backing map, there is a race condition. True. On the
other hand, the purpose of the synchronized block is only to make sure
that get() and setNewValue() are not called at the same time. When a
commit is done with the situation as described in this block, an
optimistic locking conflict would occur and the data would return
consistent. Now you can argue whether the optimistic locking exception
in this case is correct or should not have happened. In my opinion, in
the situation just described, thread x was at the critical line 1

before< the commit thread changed useNewValue. From that perspective

chronological order was retained correctly.

Thinking about it, I'm still not sure whether newValue or
previousValue need to volatile. They were changed from within a
synchronized block and are returned from with a synchronized block.
Hm ...

Hope this helped a bit.
Regards, Oliver

 

[Saxo]

And, yes ... I have no clue while the line width is that short on
every of my post. The window I type in the text is much wider. After
posting the whole thing every line is wrapped after a much shorter
number of chars per line. Wished I knew how to change this.

-- Oliver

 

[Lew]

This is really funny and made me laugh. Thanks .

Why are you wasting your and my time on this board?

Why do you even bother asking for help here?

 

[Tom Anderson]

The purpose is only to indicate that some more fine-gtrained locking
would be used for the real thing instead of doing a synchronized(this)
{ ... } thing.

It's quite a common pattern. I'm always a bit dubious about using an
public object (FSVO 'public') as the victim of a synchronized block; how
do i know some random other bit of code in some other thread isn't going
to try to lock the object at some point, and cause trouble? You wouldn't
expose a field, would you? So why expose an object's lock? Essentially, i
see an object's lock as a feature, like a method or a field; it should
only be exposed to other classes after due consideration, and if it is,
its proper use should be documented.

The locking analogue of a private field is an object like the above,
created for the sole purpose of supplying a lock that is provably only
accessible to code which can see the private details of the class.

I have coined the name 'lockguffin' for these objects, and i encourage you
all to use it.

tom

 

[Tom Anderson]

From examples posted here during the last few years, I've come to think,
that one just cannot really understand concurrency and memory-barriers.
If one thinks he does, then he either missed the hairier bits, or just
doesn't (perhaps rightly so) believe them.

Really?

I have come to think that to understand concurrency and the effects of
memory barriers, one must think *strictly* and *only* in terms of
happens-before relationships, as specified by the JLS. The whole of
section 17.4 is relevant, with 17.4.5 being the heart of the matter:

http://java.sun.com/docs/books/jls/third_edition/html/memory.html#17.4

The rules for working out happens-before relationships are simple. At
least, the fundamental idea is simple; the details of exactly when a
relationship arises are less simple, but if you know the few most
important ones, you will be fine most of the time. *Every Java programmer
should know these rules*.

To paraphrase the JLS slightly, they are:

1. If x and y are actions of the same thread and x comes before y in
program order, then x happens before y

('actions' mostly means reads and writes on memory, and a few other, less
important things; 'program order' means the order of actions within a
single thread)

2. If x happens before y, and y happens before z, then x happens before z

3. The release of a lock happens before any subsequent acquisition of that
lock

4. A write to a volatile variable happens before any subsequent read of
that variable

There are further rules about interruption, thread birth and death, and
object initialisation, but they are significantly less important. I still
think everyone ought to know them, but i will understand if they don't (i
don't know the ones about interruption and thread lifecycle off the top of
my head!).

From these rules, you can work out if there is a happens-before
relationship between any two actions. Doing so is not necessarily trivial,
but it is no more complex than, say, solving a sudoku problem. It's a
question of applying the rules, and trying to find a chain of
happens-before relationships. If you can't find one, you conclude one
doesn't exist.

You don't need to know any more about memory barriers than that. The
effects of memory barriers are as required by these rules.

tom

 

[Saxo]

All right, think a found a solution for my initial problem, which was
context switches bewtween lines 1,2,3:

public Object get() {
synchronized(lock) {
if(useNewValue.get()) // 1
return newValue; // 2
return previousValue; // 3
}
}

Solution for the new Node class looks like this (hope it works out
well with indentation and line breaks):

package test.switchover;

import java.util.concurrent.atomic.AtomicBoolean;

public class SwitchableValue
{

private Object lock = new Object();
private Object switchOverLock = null;
private Object newValue = null;
private Object previousValue = null;
private AtomicBoolean useNewValue = new AtomicBoolean(false);

public SwitchableValue() {
super();
}

public SwitchableValue(Object currentValue) {
super();
this.newValue = currentValue;
}

public void set(Object newValue, AtomicBoolean useNewValue, Object
switchOverLock) {
synchronized (lock) {
assert useNewValue.get() == false;
this.switchOverLock = switchOverLock;
this.useNewValue = useNewValue;
this.previousValue = this.newValue;
this.newValue = newValue;
}
}

public Object get() {
synchronized (lock) {
if(switchOverLock == null) {
// optimization to avoid 2 nested synchronized blocks
when
// not switching over to the new value, which is mostly
the case
return newValue;
}
synchronized (switchOverLock) {
// do the switch over, the if-then-else block should be
without
// any problems caused by context switches in between as
done
// from within the switchOverLock
if(useNewValue.get()) {
switchOverLock = null;
useNewValue = null;
return newValue;
}
return previousValue;
}
}
}
}


Here is some code to run a test case:

package test.switchover;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.concurrent.atomic.AtomicBoolean;

public class SwitchOverTest {


public static void main(String[] args)
{
final int maxValues = 100;
List<Runnable> pollingRunnables = new ArrayList<Runnable>();
final List<SwitchableValue> values = new
ArrayList<SwitchableValue>();
final AtomicBoolean proceed = new AtomicBoolean(true);
for (int i = 0; i < maxValues; i++) {
final int j = i;
values.add(new SwitchableValue(new Integer(i)));
pollingRunnables.add(new Runnable() {
int pos = j;
public void run() {
while(proceed.get()) {
System.out.println("Value of runnable " + pos + ": " +
values.get(pos).get());
try {
Thread.sleep(1000);
} catch (InterruptedException e) { }
}
});
}

Iterator<Runnable> it = pollingRunnables.iterator();
while(it.hasNext()) {
new Thread(it.next()).start();
}

try {
Thread.sleep(2000);
} catch (InterruptedException e) { }

Object switchOverLock = new Object();
AtomicBoolean useNewValue = new AtomicBoolean(false);

for (int i = 0; i < maxValues; i++) {
values.get(i).set(i + 1, useNewValue, switchOverLock);
}

synchronized (switchOverLock) {
try {
System.out.println("Now all output to the console is suspended,
because the switchOverLock is held by the commit thread.");
System.out.println("Waiting for 4 seconds to be able to read the
message...");
Thread.sleep(4000);
System.out.println("All output to the console is resumed and the
values are all incremented by 1.");
System.out.println("Waiting for 4 seconds to be able to read the
message...");
Thread.sleep(4000);
} catch (InterruptedException e) { }
useNewValue.compareAndSet(false, true);
}

try {
Thread.sleep(2000);
} catch (InterruptedException e) { }

System.out.println("stopping ...");
proceed.compareAndSet(true, false);

try {
Thread.sleep(1000);
} catch (InterruptedException e) { }

System.out.println("done.");
}
}

Cheers, Oliver

 

[Gene Wirchenko]

On Thu, 15 Dec 2011 14:58:04 +0000, Tom Anderson

[snip]

The rules for working out happens-before relationships are simple. At
least, the fundamental idea is simple; the details of exactly when a
relationship arises are less simple, but if you know the few most
important ones, you will be fine most of the time. *Every Java programmer
should know these rules*.

To paraphrase the JLS slightly, they are:

1. If x and y are actions of the same thread and x comes before y in
program order, then x happens before y

('actions' mostly means reads and writes on memory, and a few other, less
important things; 'program order' means the order of actions within a
single thread)

Is this actually the case? IIRC, C has an as-if rule. An
implementation can break the rules if it can be guaranteed that the
result will be the same as if the rules were followed.

[snip]

Sincerely,

Gene Wirchenko

 

[Daniel Pitts]

It is passed in so that the visibility change from previousValue to
newValue can be done with a single atomic change of useNewValue by
reference from outside the synchronized block for all nodes in the
list at once. This is also the reason why boolean wouldn't work as not
accessible by reference and why it has to be aAtomicBoolean as the
commit thread changing the value of useNewValue does not enter the
synchronized block.



This is true for all threads calling aNode.get(), but not for the
single commit thread that changes useNewValue atomically by reference
from outside the synchronized block.

This sounds like the wrong reason to use AtomicBoolean, but perhaps I'm
not understanding your use-case.

Hmm, actually, now I think I do... Its kind of a transaction thing,
isn't it?

Basically, you want to commit a change only under some circumstance, and
you want the "last to set before they commit" to win on commit.

Hmm... Interesting. Have you looked at AtomicReference, or
AtomicStampedReference? I think they do exactly what you're trying to do.

<http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/atomic/AtomicReference.html>
<http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/atomic/AtomicStampedReference.html>

For example:
AtomicReference<V> reference;

public void process() {
final V oldValue = reference.get();
V result = doSomeProcessing(oldValue);
// commit phase:
reference.compareAndSet(oldValue, result);
}

OR, if you need to only commit if there haven't been *any* other changes:


AtomicStampedReference<V> reference;

public void process() {
final int[] stampHolder = new int[1];
final V oldValue = reference.get(stampHolder);
V result = doSomeProcessing(oldValue);
// commit phase:
reference.compareAndSet(oldValue, result, stampHolder[0],
stampHolder[0]+1);
}


The reason you might want Stamped is in the following situation:

Thread 1 grabs value "A".
Thread 2 grabs value "A".
Thread 1 uses CAS for "A" to "B", so value is now committed as "B"
Thread 3 grabs value "B"
Thread 3 uses CAS for "B" to "A", so value is now committed as "A"
Thread 1 uses CAS for "A" to C". The result is different for stamped vs
unstamped...

Stamped, the result is "A" remains the value (because the stamp has
changed so the CAS fails). For unstamped, the value is "C", because the
old value was "A".

Decide on which outcome you care about in that approach, in order to
decide whether to use Stamped or not.

 

[Saxo]

Hmm, actually, now I think I do...  Its kind of a transaction thing,
isn't it?

Hi Daniel, the AtomicBoolean ist not needed any more in my second
approach where useNewValue is protected by the switchOverLock lock.
But it has to be an object, of which the value can be changed by
reference when the commit is to be donne atomically "in one go" for
all nodes, which cannot be done with java.util.Boolean since it is
constant. I would have to create own MyChangeableBoolean class. Looked
to me like an overkill and therefore held on to that AtomicBoolean
instance. For the real thing I need to add a comment explaining this
or create that MyChangeableBoolean class ;-)

Basically, you want to commit a change only under some circumstance, and
you want the "last to set before they commit" to win on commit.

Hmm... Interesting. Have you looked at AtomicReference, or
AtomicStampedReference? I think they do exactly what you're trying to do.

I had a short look at AtomicStampedReference. Maybe it was too short
and I should have a closer look at it.

AtomicStampedReference<V> reference;

public void process() {
      final int[] stampHolder = new int[1];
      final V oldValue = reference.get(stampHolder);
      V result = doSomeProcessing(oldValue);
      // commit phase:
      reference.compareAndSet(oldValue, result, stampHolder[0],
                             stampHolder[0]+1);

}

Yes, I see. Problem is that there is a list of SwitchableValues
(because several changes were made in the transaction) and they all
need to switch values "in one go" for the commit to be atomic, e.g.
all changes of the transaction become visible at once or not at all.
Have to see whether this can be done with such an
AtomicStampedReference.

The reason you might want Stamped is in the following situation:

Thread 1 grabs value "A".
Thread 2 grabs value "A".
Thread 1 uses CAS for "A" to "B", so value is now committed as "B"
Thread 3 grabs value "B"
Thread 3 uses CAS for "B" to "A", so value is now committed as "A"
Thread 1 uses CAS for "A" to C".  The result is different for stamped vs
unstamped...

Stamped, the result is "A" remains the value (because the stamp has
changed so the CAS fails).  For unstamped, the value is "C", because the
old value was "A".

Decide on which outcome you care about in that approach, in order to
decide whether to use Stamped or not.

This is interesting. Have to go to work now and will have a closer
look at it later.

Regards, Oliver

 

[Tom Anderson]

On Thu, 15 Dec 2011 14:58:04 +0000, Tom Anderson

[snip]

The rules for working out happens-before relationships are simple. At
least, the fundamental idea is simple; the details of exactly when a
relationship arises are less simple, but if you know the few most
important ones, you will be fine most of the time. *Every Java programmer
should know these rules*.

To paraphrase the JLS slightly, they are:

1. If x and y are actions of the same thread and x comes before y in
program order, then x happens before y

('actions' mostly means reads and writes on memory, and a few other, less
important things; 'program order' means the order of actions within a
single thread)

Is this actually the case? IIRC, C has an as-if rule. An
implementation can break the rules if it can be guaranteed that the
result will be the same as if the rules were followed.

Possibly. But i don't really know what such a rule really even means; how
could you have a rule that banned as-if behaviour? How would that be
enforced? How could you tell if it was being broken? Isn't there an
implicit as-if rule in every specification? It seems like a meaningless
thing to state explicitly.

tom

 

[Lew]

It's quite a common pattern. I'm always a bit dubious about using an
public object (FSVO 'public') as the victim of a synchronized block; how
do i know some random other bit of code in some other thread isn't going
to try to lock the object at some point, and cause trouble? You wouldn't
expose a field, would you? So why expose an object's lock? Essentially, i
see an object's lock as a feature, like a method or a field; it should
only be exposed to other classes after due consideration, and if it is,
its proper use should be documented.

I control that by who sees the object, e.g., a 'Collections.synchronizedList()'.

I see the point in what you're saying but I find it over-cautious sometimes..
It depends on whether you want the object to control its own internal locking,
which sometimes you do, or to be part of its client's thread control, as the numerous standard API classes with 'synchronized' methods do.

The locking analogue of a private field is an object like the above,
created for the sole purpose of supplying a lock that is provably only
accessible to code which can see the private details of the class.

I have coined the name 'lockguffin' for these objects, and i encourage you
all to use it.

When appropriate.

 

[Daniel Pitts]

Yes, I see. Problem is that there is a list of SwitchableValues
(because several changes were made in the transaction) and they all
need to switch values "in one go" for the commit to be atomic, e.g.
all changes of the transaction become visible at once or not at all.
Have to see whether this can be done with such an
AtomicStampedReference.

Okay, based on your other thread about transactions, I think you're
starting to get a little being the scope of the original question here.
And general advice for transaction management is a little out of my
league. However, if I understood *exactly* your requirements, I might
be able to give specific advice.

The approach you're currently taking can't be fixed to support two
concurrent transactions that may interfere with each-other. You'd have
to have some mechanism to detect a conflict and roll-back or retry in
that case.

Is this purely a learning exercise or are you actually hoping that this
code goes into production somewhere? If it is purely an experiment then
kudos at that, but if not then I suggest escalating the problem to a
more experienced developer. These kinds of things you usually can't
afford to get wrong. unless you have read and fully understood enough
literature on the subject, it is easy to get wrong.

Good luck! This *is* a field I've been interested in, so please keep
following up with your findings!

Thanks,
Daniel.

 

[Daniel Pitts]

I control that by who sees the object, e.g., a 'Collections.synchronizedList()'.

I see the point in what you're saying but I find it over-cautious sometimes..
It depends on whether you want the object to control its own internal locking,
which sometimes you do, or to be part of its client's thread control, as the numerous standard API classes with 'synchronized' methods do.

I seem to recall this practice of using an internal lock object being
advocated in JCIP, but I'm not near my bookshelf at the moment so I
can't be sure.

I happen to agree with Eric on this one though. If you expose any method
as "synchronized" (whether it is public or not), then you have added an
implicit contract to your object that you may not have intended. That
contract is "If *any* external process synchronizes on this object, it
will be serialized with certain operations I perform."

More often than not, you will want to be explicit about behavior in
concurrent situations, not implicit.

When appropriate.

"When appropriate" should be the default modifier for all statements,
because you shouldn't ever do something when its not appropriate

 

[Gene Wirchenko]

On Thu, 15 Dec 2011 14:58:04 +0000, Tom Anderson

[snip]

The rules for working out happens-before relationships are simple. At
least, the fundamental idea is simple; the details of exactly when a
relationship arises are less simple, but if you know the few most
important ones, you will be fine most of the time. *Every Java programmer
should know these rules*.

To paraphrase the JLS slightly, they are:

1. If x and y are actions of the same thread and x comes before y in
program order, then x happens before y

('actions' mostly means reads and writes on memory, and a few other, less
important things; 'program order' means the order of actions within a
single thread)

Is this actually the case? IIRC, C has an as-if rule. An
implementation can break the rules if it can be guaranteed that the
result will be the same as if the rules were followed.

Possibly. But i don't really know what such a rule really even means; how
could you have a rule that banned as-if behaviour? How would that be
enforced? How could you tell if it was being broken? Isn't there an
implicit as-if rule in every specification? It seems like a meaningless
thing to state explicitly.

A language might have a rule that a certain case must be handled
in a certain way.

If a compiler could determine in code analysis that that case
could never occur, then it could omit generating code that handled
that case.

Sincerely,

Gene Wirchenko

 

[Tom Anderson]

I control that by who sees the object, e.g., a 'Collections.synchronizedList()'.

That's why i said "public object (FSVO 'public')" - there are times when
you can wrap your objects like that, but others when it doesn't make
sense, because of the extra complexity it introduces.

Wrapping is definitely a powerful tool here, though, very good point.
Wrapping is, generally, a way of creating a sort of neutral zone; things
that are behind the wrapper can be public without actually being very
exposed. You control their effective scope by controlling the availability
of the reference.

I see the point in what you're saying but I find it over-cautious sometimes.

Fair point. I suppose this is something you can do if you want to be able
to make strong assumptions about when the object is locked. You don't
always need that.

It depends on whether you want the object to control its own internal
locking, which sometimes you do, or to be part of its client's thread
control, as the numerous standard API classes with 'synchronized'
methods do.

Yes, quite true. This is what i was getting at with "an object's lock
[...] should only be exposed to other classes after due consideration, and
if it is, its proper use should be documented". Making it part of the
client's thread control is a valid thing to do, but it should be a
considered act.

When appropriate.

Oh, sorry, i meant that i encourage you to use the name, not the pattern!
The name is always appropriate; the pattern certainly might not be.

tom

 

[Tom Anderson]

"When appropriate" should be the default modifier for all statements,
because you shouldn't ever do something when its not appropriate

that doesn't sound like any fun at all.

tom

 

[Saxo]

On 12/15/11 11:01 PM, Saxo wrote:

The approach you're currently taking can't be fixed to support two
concurrent transactions that may interfere with each-other. You'd have
to have some mechanism to detect a conflict and roll-back or retry in
that case.

Hi Daniel, you are exactly right with this and I have also thought
about the problem with interference. What I want to do is a map
implementation that supports optimistic locking. I tried to describe
this in brief in my post from Dec 15, 8:25 am (or my 8th post in this
thread, I don't know whether the same time stamps are displayed for
you over there):

(1) BackingMap backingMap = new BackingMap();

(2) LocalMap map1 = new LocalMap(backingMap);
(3) map1.begin();
(4) Node node1 = map1.get(key1);
(5) node1.value = newValue;
(6) Node node2 = map1.putAndGet(key1, node1);
(7) map1.commit(); // or map1.mergeCommit();

A transaction knows the keys of the values that were changed (because
either a put or a remove was done using those keys). If the
transaction commits, the map needs to check whether some other
transaction is currently running its commit process and whether at
least one of the keys are shared with that committing transaction. If
so, it has to wait till the other transaction has finished committing.
If two transaction that both want to commit don't share any keys the
can commit in parallel. However, the user needs to have issued what I
called in line (7) above a merge commit. In that case keys are
"merged" in in parallel. If the entire map must have remained
unchanged from the beginning of the transaction to the end, an
ordinary commit is issued (map1.commit() in line 7) and the thing
fails fast if the map's change counter has changed meanwhile.

Is this purely a learning exercise or are you actually hoping that this
code goes into production somewhere? If it is purely an experiment then
kudos at that, but if not then I suggest escalating the problem to a
more experienced developer.  These kinds of things you usually can't
afford to get wrong. unless you have read and fully understood enough
literature on the subject, it is easy to get wrong.

This is a fun/learning exercise. But I still want to develop something
that one day can be used for some real purpose. The critical difficult
part is the commit phase. I might stick to some STM framework like
Deuce STM (http://www.deucestm.org) and let Deuce do the difficult
things:

@Atomic
public void commit() {
// no serialization of transactions or other critical things need to
be done
// because marked atomic and hence Deuce will take care of this
}

But that would only be done as an option to calm people down. The fun
part is really to develop a solution of my own and implement
it ... ;-).

Good luck! This *is* a field I've been interested in, so please keep
following up with your findings!

Thanks,
Daniel.

Thanks for the good wishes! Will take some time till I have something
finished as I don't have that much time for it. But I will keep you
informed .

Regards, Oliver

 

[Saxo]

Hi Daniel, you are exactly right with this and I have also thought
about the problem with interference. What I want to do is a map
implementation that supports optimistic locking. I tried to describe
this in brief in my post from Dec 15, 8:25 am (or my 8th post in this
thread, I don't know whether the same time stamps are displayed for
you over there):

(1) BackingMap backingMap = new BackingMap();

(2) LocalMap map1 = new LocalMap(backingMap);
(3) map1.begin();
(4) Node node1 = map1.get(key1);
(5) node1.value = newValue;
(6) Node node2 = map1.putAndGet(key1, node1);
(7) map1.commit(); // or map1.mergeCommit();

You know what? Coming to think of it, the calling thread that issues
map1.commit() must not carry out the commit. Otherwise some potential
for a deadlock is created. For the commit a new thread has to be
spawned by the BackingMap...