counting – Shared memory – Wait-free – Consensus – Terms

Summary. TheacronymCaRuDrepresents an interface spec-ification and an algorithm for the management of memory shared by concurrent processes. The memory cells form a di-rected acyclic graph. This graph is only modified by adding a new node with a list of reachable children, and by remov-ing unreachable nodes. If memory is not full, the algorithm ensures wait-free redistribution of free nodes. It uses atomic counters for reference counting and consensus variables to ensure exclusive access. Performance is enhanced by using nondeterminacy guided by insecure knowledge. Experiments indicate that the algorithm is very suitable formultiprocessing