Interesting work! I should be fortunate to make time to read it.

I will point out, in case you'd not considered it, that you can support addition and removal indirectly by formulating it as a difference of sets. Similar to the collision-resistant replicated data types (CRDTs) concept. Checking for membership would simply become CheckMembershipInAdditionSet && !CheckMembershipInRemovalSet, assuming an item could only be added/removed once. You could also perhaps support multiple addition/removal by attaching a count of how many times it's been added though that might break some of the building blocks in the paper.
--