Philippas Tsigas
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Philippas Tsigas has a total of 170 co-authors. Here are the top co-authors by number of shared publications:
- Marina Papatriantafilou
Chalmers University of Technology, Gothenburg, Sweden
57 shared publications - Phuong Hoai Ha
UiT The Arctic University of Norway
17 shared publications Daniel Cederman
Department of Computer Science and Engineering, Chalmers University of Technology, SE-412 96 Göteborg, Sweden
13 shared publicationsAnders Gidenstam
School of Business and Informatics, Högskolan I Borås, S-50190 Borås, Sweden
11 shared publicationsYiannis Nikolakopoulos
Chalmers University of Technology
11 shared publicationsVincenzo Gulisano
10 shared publications
Latest Publications
- Open Access
- 5 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 1-5
Invited Paper: Relaxed Data Structures for Practical Parallelism: Survey and Design Recommendations
Relaxed data structures offer a systematic approach for improving scalability in highly concurrent systems by weakening restrictive data ordering constraints that limit parallelism. By relaxing semantics such as exact FIFO ordering in queues, threads can access the data structure through multiple disjoint access points, reducing contention and significantly improving throughput. Prior work has extensively studied relaxed data structures, primarily focusing on concurrent FIFO, LIFO, and priority queues, demonstrating that substantial scalability gains can be achieved while preserving useful ordering guarantees. In particular, relaxed priority queues have emerged as effective scheduling primitives, enabling state-of-the-art performance in applications such as parallel Single-Source Shortest Paths. This paper surveys the design space of relaxed data structures, identifying key relaxation models and implementation techniques, systematically comparing the strengths and weaknesses of existing algorithms. The survey highlights fundamental trade-offs between ordering guarantees and performance, aiming to provide guidance for both designers and users of relaxed concurrent data structures.
- 5 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 1-5
Open AccessInvited Paper: Relaxed Data Structures for Practical Parallelism: Survey and Design Recommendations
Relaxed data structures offer a systematic approach for improving scalability in highly concurrent systems by weakening restrictive data ordering constraints that limit parallelism. By relaxing semantics such as exact FIFO ordering in queues, threads can access the data structure through multiple disjoint access points, reducing contention and significantly improving throughput. Prior work has extensively studied relaxed data structures, primarily focusing on concurrent FIFO, LIFO, and priority queues, demonstrating that substantial scalability gains can be achieved while preserving useful ordering guarantees. In particular, relaxed priority queues have emerged as effective scheduling primitives, enabling state-of-the-art performance in applications such as parallel Single-Source Shortest Paths. This paper surveys the design space of relaxed data structures, identifying key relaxation models and implementation techniques, systematically comparing the strengths and weaknesses of existing algorithms. The survey highlights fundamental trade-offs between ordering guarantees and performance, aiming to provide guidance for both designers and users of relaxed concurrent data structures.
- Open Access
- 15 November 2025
- Published by Association for Computing Machinery (ACM)
- p. 2109-2125
Wasp: Efficient Asynchronous Single-Source Shortest Path on Multicore Systems via Work Stealing
- 15 November 2025
- Published by Association for Computing Machinery (ACM)
- p. 2109-2125
Open AccessWasp: Efficient Asynchronous Single-Source Shortest Path on Multicore Systems via Work Stealing
- 23 August 2025
- Published by Springer Nature
- p. 236-249
Interval-Asynchrony: Delimited Intervals of Localised Asynchrony for Fast Parallel SGD
- 23 August 2025
- Published by Springer Nature
- p. 236-249
Interval-Asynchrony: Delimited Intervals of Localised Asynchrony for Fast Parallel SGD
- Open Access
- 1 March 2025
- Published by Association for Computing Machinery (ACM)
- p. 43-47
Relax and don't Stop: Graph-aware Asynchronous SSSP
- 1 March 2025
- Published by Association for Computing Machinery (ACM)
- p. 43-47
Open AccessRelax and don't Stop: Graph-aware Asynchronous SSSP
- Open Access
- 28 February 2025
- Published by Association for Computing Machinery (ACM)
- p. 382-395
Balanced Allocations over Efficient Queues: A Fast Relaxed FIFO Queue
Relaxed semantics have been introduced to increase the achievable parallelism of concurrent data structures in exchange for weakening their ordering semantics. In this paper, we revisit the balanced allocations d-choice load balancing scheme in the context of relaxed FIFO queues. Our novel load balancing approach distributes operations evenly across n sub-queues based on operation counts, achieving low relaxation errors independent on the queues size, as opposed to similar earlier designs. We prove its relaxation errors to be of O(n log log n/log d) with high probability for a collection of possible executions. Furthermore, our scheme, contrary to previous ones, manages to interface and integrate the most performant linearizable queue designs from the literature as components. Our resulting relaxed FIFO queue is experimentally shown to outperform the previously best design using balanced allocations by more than four times in throughput, while simultaneously incurring less than a thousandth of its relaxation errors. In a concurrent breadth-first-search benchmark, our queue consistently outperforms both relaxed and strict state-of-the-art FIFO queues.
- 28 February 2025
- Published by Association for Computing Machinery (ACM)
- p. 382-395
Open AccessBalanced Allocations over Efficient Queues: A Fast Relaxed FIFO Queue
Relaxed semantics have been introduced to increase the achievable parallelism of concurrent data structures in exchange for weakening their ordering semantics. In this paper, we revisit the balanced allocations d-choice load balancing scheme in the context of relaxed FIFO queues. Our novel load balancing approach distributes operations evenly across n sub-queues based on operation counts, achieving low relaxation errors independent on the queues size, as opposed to similar earlier designs. We prove its relaxation errors to be of O(n log log n/log d) with high probability for a collection of possible executions. Furthermore, our scheme, contrary to previous ones, manages to interface and integrate the most performant linearizable queue designs from the literature as components. Our resulting relaxed FIFO queue is experimentally shown to outperform the previously best design using balanced allocations by more than four times in throughput, while simultaneously incurring less than a thousandth of its relaxation errors. In a concurrent breadth-first-search benchmark, our queue consistently outperforms both relaxed and strict state-of-the-art FIFO queues.
- 26 August 2024
- Published by Springer Nature
- p. 119-133
How to Relax Instantly: Elastic Relaxation of Concurrent Data Structures
- 26 August 2024
- Published by Springer Nature
- p. 119-133
How to Relax Instantly: Elastic Relaxation of Concurrent Data Structures
- Open Access
- 20 February 2023
- Published by Elsevier in Journal of Parallel and Distributed Computing
- Vol. 177, 68-88
PARMA-CC: A family of parallel multiphase approximate cluster combining algorithms
- 20 February 2023
- Published by Elsevier in Journal of Parallel and Distributed Computing
- Vol. 177, 68-88
Open AccessPARMA-CC: A family of parallel multiphase approximate cluster combining algorithms
- Open Access
Relaxing Concurrent Data-structure Semantics for Increasing Performance: A Multi-structure 2D Design Framework
There has been a significant amount of work in the literature proposing semantic relaxation of concurrent data structures for improving scalability and performance. By relaxing the semantics of a data structure, a bigger design space, that allows weaker synchronization and more useful parallelism, is unveiled. Investigating new data structure designs, capable of trading semantics for achieving better performance in a monotonic way, is a major challenge in the area. We algorithmically address this challenge in this paper.To address this challenge, we present an efficient lock-free, concurrent data structure design framework for out-of-order semantic relaxation. Our framework introduces a new two dimensional algorithmic design, that uses multiple instances of an implementation of the given data structure. The first dimension of our design is the number of data structure instances onto which operations are spread to, in order to achieve increased parallelism through disjoint memory accesses. The second dimension is the number of consecutive operations of a single thread that can stay at the same data structure instance in order to benefit from data locality. Our design can flexibly explore this two-dimensional space to achieve the property of monotonically increasing throughput performance via relaxing concurrent data structure semantics within a tight deterministic relaxation bound, as we prove in the paper. We show how our framework can instantiate lock-free out-of-order queues, stacks, counters and dequeues. The experimental evaluation shows that our two-dimensional data structures: i) significantly outperform the respected previous proposed ones with respect to scalability and throughput performance and ii) monotonically increase throughput as relaxation increases.
Open AccessRelaxing Concurrent Data-structure Semantics for Increasing Performance: A Multi-structure 2D Design Framework
There has been a significant amount of work in the literature proposing semantic relaxation of concurrent data structures for improving scalability and performance. By relaxing the semantics of a data structure, a bigger design space, that allows weaker synchronization and more useful parallelism, is unveiled. Investigating new data structure designs, capable of trading semantics for achieving better performance in a monotonic way, is a major challenge in the area. We algorithmically address this challenge in this paper.To address this challenge, we present an efficient lock-free, concurrent data structure design framework for out-of-order semantic relaxation. Our framework introduces a new two dimensional algorithmic design, that uses multiple instances of an implementation of the given data structure. The first dimension of our design is the number of data structure instances onto which operations are spread to, in order to achieve increased parallelism through disjoint memory accesses. The second dimension is the number of consecutive operations of a single thread that can stay at the same data structure instance in order to benefit from data locality. Our design can flexibly explore this two-dimensional space to achieve the property of monotonically increasing throughput performance via relaxing concurrent data structure semantics within a tight deterministic relaxation bound, as we prove in the paper. We show how our framework can instantiate lock-free out-of-order queues, stacks, counters and dequeues. The experimental evaluation shows that our two-dimensional data structures: i) significantly outperform the respected previous proposed ones with respect to scalability and throughput performance and ii) monotonically increase throughput as relaxation increases.
- 1 August 2022
- Published by Springer Nature
- p. 268-284
$\mathtt {IP.LSH.DBSCAN}$: Integrated Parallel Density-Based Clustering Through Locality-Sensitive Hashing- 1 August 2022
- Published by Springer Nature
- p. 268-284
$\mathtt {IP.LSH.DBSCAN}$: Integrated Parallel Density-Based Clustering Through Locality-Sensitive Hashing- Open Access
STRETCH: Virtual Shared-Nothing Parallelism for Scalable and Elastic Stream Processing
Stream processing applications extract value from raw data through Directed Acyclic Graphs of data analysis tasks. Shared-nothing (SN) parallelism is the de-facto standard to scale stream processing applications. Given an application, SN parallelism instantiates several copies of each analysis task, making each instance responsible for a dedicated portion of the overall analysis, and relies on dedicated queues to exchange data among connected instances. On the one hand, SN parallelism can scale the execution of applications both up and out since threads can run task instances within and across processes/nodes. On the other hand, its lack of sharing can cause unnecessary overheads and hinder the scaling up when threads operate on data that could be jointly accessed in shared memory. This trade-off motivated us in studying a way for stream processing applications to leverage shared memory and boost the scale up (before the scale out) while adhering to the widely-adopted and SN-based APIs for stream processing applications. We introduce STRETCH, a framework that maximizes the scale up and offers instantaneous elastic reconfigurations (without state transfer) for stream processing applications. We propose the concept of Virtual Shared-Nothing (VSN) parallelism and elasticity and provide formal definitions and correctness proofs for the semantics of the analysis tasks supported by STRETCH, showing they extend the ones found in common Stream Processing Engines. We also provide a fully implemented prototype and show that STRETCH's performance exceeds that of state-of-the-art frameworks such as Apache Flink and offers, to the best of our knowledge, unprecedented ultra-fast reconfigurations, taking less than 40 ms even when provisioning tens of new task instances.
Open AccessSTRETCH: Virtual Shared-Nothing Parallelism for Scalable and Elastic Stream Processing
Stream processing applications extract value from raw data through Directed Acyclic Graphs of data analysis tasks. Shared-nothing (SN) parallelism is the de-facto standard to scale stream processing applications. Given an application, SN parallelism instantiates several copies of each analysis task, making each instance responsible for a dedicated portion of the overall analysis, and relies on dedicated queues to exchange data among connected instances. On the one hand, SN parallelism can scale the execution of applications both up and out since threads can run task instances within and across processes/nodes. On the other hand, its lack of sharing can cause unnecessary overheads and hinder the scaling up when threads operate on data that could be jointly accessed in shared memory. This trade-off motivated us in studying a way for stream processing applications to leverage shared memory and boost the scale up (before the scale out) while adhering to the widely-adopted and SN-based APIs for stream processing applications. We introduce STRETCH, a framework that maximizes the scale up and offers instantaneous elastic reconfigurations (without state transfer) for stream processing applications. We propose the concept of Virtual Shared-Nothing (VSN) parallelism and elasticity and provide formal definitions and correctness proofs for the semantics of the analysis tasks supported by STRETCH, showing they extend the ones found in common Stream Processing Engines. We also provide a fully implemented prototype and show that STRETCH's performance exceeds that of state-of-the-art frameworks such as Apache Flink and offers, to the best of our knowledge, unprecedented ultra-fast reconfigurations, taking less than 40 ms even when provisioning tens of new task instances.