Implementing and Evaluating the Performance of CRDTs in Encore

Sammanfattning: The majority of CPUs used in general purpose computers have multiple cores. Manyof the programming languages in use today have only added support for multi-corecomputers as an afterthought. This have made it unnecessarily hard and error proneto develop programs for modern CPUs. The object oriented programming languageEncore in development at Uppsala University have been designed from the ground upwith support for multi-core CPUs in mind. Encore is designed for shared memorymachines and uses actors which communicate asynchronously with each other. Thismakes it similar to a distributed system on a conceptual level, where the actors couldbe seen as the nodes in a distributed system.Convergent or Commutative Replicated Data Types (CRDTs) are a type of datastructure used in distributed systems to achieve strong eventual consistency betweenthe nodes of the system. Each node of the system will have its own local replica of thedata on which it will operate on.The goal of this thesis is to evaluate if CRDTs can be implemented and used in Encorein an performance efficient way. They could then potentially become a reusablecomponent of programs written in Encore. The evaluation is performed byimplementing two set and map designs based on CRDTs in the Encore programminglanguage. One which is based directly on the Observed Remove CRDT and anotherone which uses ideas from the Last Writer Wins CRDT. In these designs Encoreactors are used to perform operations on different replicas in parallel. Theirperformance is then evaluated using several different benchmarks. One sequentialimplementation as well as a parallel design unrelated to CRDTs is used asperformance references in the benchmarks.The similarities between Encore and a distributed system makes it easy to implementCRDTs in Encore. The results show that the overall performance of the implementeddesigns based on CRDTs is bad when compared to other concurrent data structures.There are however specific use cases where their performance is good.