I'll summaries the error I found in the original adaptive bag.
If the current state is Pure { thresh=10, current = [1,2,3]}, if the execution is in following order:
Thread t1 success in line 76
Thread t2 executing line 56~66
t2 will find the bag is empty and the remove will fail, so the set semantics breaks.
If the current state is Trans [1,2,3] sbag, assume there are two threads t1, t2 and the execution is in following order:
Thread t2 issue add bag 4 and execute line 42~47
Thread t1 execute line 78, which issue write 1,2 and 3 to sbag.
Thread t2 success in line 48
Thread t1 success in line 79
Now the 4 is lost in sbag forever, and thread t1 and t2 cannot get the 4 in subsequent remove.
The root reason is just the technique propose in the paper cannot solve the problem in bag datastructure, the remove operation of bag is much more complicated than remove in map(it involves get and write in one operation). I propose my solution in my adaptive bag.
I'll summaries the error I found in the original adaptive bag.
Pure { thresh=10, current = [1,2,3]}, if the execution is in following order: Thread t1 success in line 76 Thread t2 executing line 56~66 t2 will find the bag is empty and the remove will fail, so the set semantics breaks.Trans [1,2,3] sbag, assume there are two threads t1, t2 and the execution is in following order: Thread t2 issueadd bag 4and execute line 42~47 Thread t1 execute line 78, which issue write 1,2 and 3 tosbag. Thread t2 success in line 48 Thread t1 success in line 79 Now the4is lost insbagforever, and thread t1 and t2 cannot get the4in subsequentremove.The root reason is just the technique propose in the paper cannot solve the problem in bag datastructure, the remove operation of bag is much more complicated than remove in map(it involves get and write in one operation). I propose my solution in my adaptive bag.