Scalable FIFO channels for programming via communicating sequential processes

N. Koval, D.-A. Alistarh, R. Elizarov, in:, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Nature, 2019, pp. 317–333.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English
Department
Series Title
LNCS
Abstract
Traditional concurrent programming involves manipulating shared mutable state. Alternatives to this programming style are communicating sequential processes (CSP) and actor models, which share data via explicit communication. These models have been known for almost half a century, and have recently had started to gain significant traction among modern programming languages. The common abstraction for communication between several processes is the channel. Although channels are similar to producer-consumer data structures, they have different semantics and support additional operations, such as the select expression. Despite their growing popularity, most known implementations of channels use lock-based data structures and can be rather inefficient. In this paper, we present the first efficient lock-free algorithm for implementing a communication channel for CSP programming. We provide implementations and experimental results in the Kotlin and Go programming languages. Our new algorithm outperforms existing implementations on many workloads, while providing non-blocking progress guarantee. Our design can serve as an example of how to construct general communication data structures for CSP and actor models.
Publishing Year
Date Published
2019-08-13
Proceedings Title
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume
11725
Page
317-333
Conference
Euro-Par: European Conference on Parallel Processing
Conference Location
Göttingen, Germany
Conference Date
2019-08-26 – 2019-08-30
ISSN
eISSN
IST-REx-ID

Cite this

Koval N, Alistarh D-A, Elizarov R. Scalable FIFO channels for programming via communicating sequential processes. In: Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol 11725. Springer Nature; 2019:317-333. doi:10.1007/978-3-030-29400-7_23
Koval, N., Alistarh, D.-A., & Elizarov, R. (2019). Scalable FIFO channels for programming via communicating sequential processes. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 11725, pp. 317–333). Göttingen, Germany: Springer Nature. https://doi.org/10.1007/978-3-030-29400-7_23
Koval, Nikita, Dan-Adrian Alistarh, and Roman Elizarov. “Scalable FIFO Channels for Programming via Communicating Sequential Processes.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 11725:317–33. Springer Nature, 2019. https://doi.org/10.1007/978-3-030-29400-7_23.
N. Koval, D.-A. Alistarh, and R. Elizarov, “Scalable FIFO channels for programming via communicating sequential processes,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Göttingen, Germany, 2019, vol. 11725, pp. 317–333.
Koval N, Alistarh D-A, Elizarov R. 2019. Scalable FIFO channels for programming via communicating sequential processes. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Euro-Par: European Conference on Parallel Processing, LNCS, vol. 11725. 317–333.
Koval, Nikita, et al. “Scalable FIFO Channels for Programming via Communicating Sequential Processes.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11725, Springer Nature, 2019, pp. 317–33, doi:10.1007/978-3-030-29400-7_23.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search