SEMINAR: Read/Write Implementations of Queues and Stacks with Relaxed...

Guest: Armando Castañeda

Title:  Read/Write Implementations of Queues and Stacks with Relaxed Semantics

Date/Time: October 14, 2024, 13:40

Location: FENS L055

Abstract: Linearizability is the standard correctness criteria for implementations of concurrent objects. Roughly speaking, a linearizable implementation of an object gives the illusion that all operations happen sequentially, in some order that respects real-time. Unfortunately, it has been shown that linearizability is expensive to achieve for some concurrent objects, which include useful objects like queues and stacks. Concretely, any linearizable implementation for such objects requires expensive synchronization mechanisms. This negative result limits the scalability of linearizable implementations for some concurrent objects. One way to evade the impossibility result is to relax the semantics of the object to be implemented in order to use only lighter synchronization mechanisms, with the aim of achieving scalability. This talk is about a recently introduced relaxation for queues and stacks called multiplicity. Roughly speaking, multiplicity allows distinct dequeue/pop operations to take the same item only if they are concurrent. It will be shown that queues and stacks with multiplicity can be implemented using only the simplest read/write operations. A variant of multiplicity allows us to develop the fastest relaxed single-enqueuer queue implementations known so far, which has implications for work-stealing, a popular dynamic load balancing technique. This is a joint work with Miguel A Piña, Sergio Rajsbaum and Michel Raynal.

Bio: Armando Castañeda is a Full Professor at the Institute of Mathematics of the National Autonomous University of Mexico (UNAM). He received a degree in Computer Engineering from the National Polytechnic Institute (IPN) of Mexico in 2002 and the M.Sc. and Ph.D. degrees in Computer Science from UNAM in 2007 and 2010 supervised by Sergio Rajsbaum. Before joining UNAM, he was a postdoctoral associate at the Institut National de Recherche en Informatique et en Automatique (INRIA), Rennes, and at the Department of Computer Science of the Technion, Israel Institute of Technology, hosted by Michel Raynal and Hagit Attiya, respectively. His main research area is the theory of distributed and concurrent computing.