@inproceedings{12735,
  abstract     = {Asynchronous programming has gained significant popularity over the last decade: support for this programming pattern is available in many popular languages via libraries and native language implementations, typically in the form of coroutines or the async/await construct. Instead of programming via shared memory, this concept assumes implicit synchronization through message passing. The key data structure enabling such communication is the rendezvous channel. Roughly, a rendezvous channel is a blocking queue of size zero, so both send(e) and receive() operations wait for each other, performing a rendezvous when they meet. To optimize the message passing pattern, channels are usually equipped with a fixed-size buffer, so sends do not suspend and put elements into the buffer until its capacity is exceeded. This primitive is known as a buffered channel.

This paper presents a fast and scalable algorithm for both rendezvous and buffered channels. Similarly to modern queues, our solution is based on an infinite array with two positional counters for send(e) and receive() operations, leveraging the unconditional Fetch-And-Add instruction to update them. Yet, the algorithm requires non-trivial modifications of this classic pattern, in order to support the full channel semantics, such as buffering and cancellation of waiting requests. We compare the performance of our solution to that of the Kotlin implementation, as well as against other academic proposals, showing up to 9.8× speedup. To showcase its expressiveness and performance, we also integrated the proposed algorithm into the standard Kotlin Coroutines library, replacing the previous channel implementations.},
  author       = {Koval, Nikita and Alistarh, Dan-Adrian and Elizarov, Roman},
  booktitle    = {Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming},
  isbn         = {9798400700156},
  location     = {Montreal, QC, Canada},
  pages        = {107--118},
  publisher    = {Association for Computing Machinery},
  title        = {{Fast and scalable channels in Kotlin Coroutines}},
  doi          = {10.1145/3572848.3577481},
  year         = {2023},
}

@misc{12736,
  abstract     = {Although a wide variety of handcrafted concurrent data structures have been proposed, there is considerable interest in universal approaches (Universal Constructions or UCs) for building concurrent data structures. UCs (semi-)automatically convert a sequential data structure into a concurrent one. The simplest approach uses locks [3, 6] that protect a sequential data structure and allow only one process to access it at a time. However, the resulting data structure is blocking. Most work on UCs instead focuses on obtaining non-blocking progress guarantees such as obstruction-freedom, lock-freedom or wait-freedom. Many non-blocking UCs have appeared. Key examples include the seminal wait-free UC [2] by Herlihy, a NUMA-aware UC [10] by Yi et al., and an efficient UC for large objects [1] by Fatourou et al.},
  author       = {Aksenov, Vitaly and Brown, Trevor A and Fedorov, Alexander and Kokorin, Ilya},
  booktitle    = {Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming},
  isbn         = {9798400700156},
  location     = {Montreal, QB, Canada},
  pages        = {438--440},
  publisher    = {Association for Computing Machinery},
  title        = {{Unexpected scaling in path copying trees}},
  doi          = {10.1145/3572848.3577512},
  year         = {2023},
}