Wait-free concurrent memory management by Create and Read until Deletion (CaRuD)

The acronym CaRuD represents an interface specification and an algorithm fo r the management of memory shared by concurrent processes. The memory cells form a directed acyclic graph. This graph is only modified by adding a new node with a list of reachable children, and by removing unreachable nodes. If memory is not full, the algorithm ensures wait-fi ee redistribution of free nodes. It uses atomic counters for reference counting and consensus va riables to ensure exclusive access. Performance is enhanced by using nondet erminacy guided by insecure knowledge. Experiments indicate that the algori thm is very suitable for multiprocessing.