The NavTalks are a series of informal talks given by Navigators members or some special guests.
Title: Consensual Data Structures
Speaker: Inês Gouveia (Citrix)
When: Thursday, March 26 2020, at 13:00 (14:00 CET)
Abstract: “Inês Pinto Gouveia will share our work in progress about the pitfalls and solutions for constructing consensually updated, shared data structures. When we compare how multithreaded applications are built today, we observe an immense difference to the patterns commonly found in resilient applications, leveraging for example triple-modular redundancy (TMR) or BFT-SMR. While multithreaded applications retain a large degree of autonomy over data structure they share, even if some threads are isolated from each other to prevent faults in one subsystem from spreading to the threads of other subsystems, TMR or BFT-SMR systems are quite rigit. Threads use locks to coordinate update sequences, utilize lock-free data structures or even more advanced synchronization schemes. Replicating threads in multi- and manycore systems, rather than the system as a whole, we obtain fine granular, configurable and adjustable resilience. However, as long as each replica retains write access for shared data, faults cannot be confined. Reverting to the other extreme, we could of course install a mututally trusted BFT-SMR service, whose replicas implement the data structure on behalf of the replicated threads, reaching consensus on all accesses and executing them in the replicas’ local state. However, much of the autonomy of the multithreaded application is lost in the process. In this talk, we therefore investigate how threads may retain autonomy while protecting the data they share from faulty replicas. We show that consensus is not enough and that many pitfalls must be taken into account and present solutions to avoid them.”
Short Bio: Inês was a former member of the Navigators group, where she did (brilliantly) her Master thesis, and then she went to Luxembourg, to do her PhD in the Critix group led by Prof. Paulo Veríssimo under the supervision of Prof. Marcus Volp.