Relaxed consistency semantics data structures on multi-core systems with shared memory

When developing a software program, various data structures are used to store and organize data which makes it easy and efficient to implement an application. In a multi-core system with shared memory, threads share these data structures, thus, to keep the data structures consistent synchronisation is needed. However, in the recent years the shift occurred towards relaxing consistency semantics for shared data structures. While relaxed consistency semantics data structures are more prominent in the distributed systems with the use of Conflict-free Replicated Data Types, their use in shared memory multi-core systems is still scarce. We found that the approaches to achieve relaxed consistency in the existing work is either closely tied to a specific application/domain/implementation or is not suitable to apply to complex data structures. Thus, in this work we explore existing approaches and extract common features which allows us create a systematic way to relax consistency semantics for shared data structures. Our solution involves three patterns which can be applied to various data structures to relax their consistency. We implemented our solution on top of the Read Log Update framework and coded two data structures with it. Although we were unable to identify complex applications that could be built on top of our implementation, having the implementation available will enable domain experts to easily experiment with relaxed consistency semantics on multi-core systems should they become interested.