Parsec: Fast, Scalable, and Secure Design with Wait-Free Parallelism

In this paper, we look at the problem of concurrent progress from an unconventional perspective and find new benefits for practical wait-freedom by considering security and reliability implications of concurrent data structures. Although lock-free data structures are increasingly used in many system applications, they can be prone to denial-of-service (DoS) attacks and pose some dilemmas for a user. For example, when can we safely conclude that one side of a communication channel is buggy or malicious? What should we do about temporary slowdowns due to scheduling peculiarities? We observe that when using wait-free approaches, these questions can be fully resolved due to strict theoretical upper bounds of wait-free algorithms; e.g., all loops are finite and the worst-case number of iterations is known beforehand. This discussion is crucial since other existing mechanisms, such as read-copy-update (RCU), are also quite problematic from the security standpoint. Moreover, even some well-known hardware primitives are less resilient to DoS attacks. We show that with recent advancements in lock- and wait-free algorithm design, many past challenges can now be fully overcome, potentially making such data structures more appealing and easier to use than present RCU equivalents. We present real-life examples that show benefits of wait-free synchronization using Go-like channels. Our overheads with respect to lock-free synchronization remain fairly low while advantages with respect to more traditional fine-grained locking are visible even under fairly moderate contention due to a reduction of synchronization system calls.