IEICE TRANS. ??, VOL.Exx–??, NO.xx XXXX 200x
1
PAPER
Efficient and Robust Lock-Free Multi-Word Compare-and-Swap via Contention-Aware Helping
arXiv:2607.06034v1 [cs.DB] 7 Jul 2026
Motoki UNNO† , Kento SUGIURA† , Nonmembers, and Yoshiharu ISHIKAWA† , Member
SUMMARY Efficient concurrent access to shared memory remains a central focus for researchers seeking to enhance data structure performance. Lock-based synchronization often limits scalability and introduces liveness issues such as deadlocks. In contrast, implementing non-blocking structures with single-word compare-and-swap (CAS) instructions increases algorithmic complexity because of unavoidable intermediate states. Multi-word compare-and-swap (MCAS) operations offer a practical primitive for atomically updating multiple discrete memory locations, thereby addressing these challenges. However, under high contention, helping mechanisms designed to guarantee lock-freedom may cause excessive cache invalidations and significant performance degradation. Furthermore, existing approaches are vulnerable to the ABA problem. Current lock-free MCAS algorithms may duplicate the execution of the same operation, leading to inconsistent states in certain edge cases. To address these challenges, this paper introduces a new lock-free MCAS algorithm that achieves both efficiency and consistency. First, we propose a contention-aware helping mechanism that dynamically regulates the number of concurrent helpers through exponential backoff and embedded entry counters. These counters also enable a fast garbage-collection path, significantly reducing memory management overhead. Second, we introduce a version embedding approach to suppress the ABA problem during MCAS operations. Although version embedding requires several bits per target memory region to store version information, embedded versions allow helpers to avoid duplicated MCAS executions. Experimental results show that the proposed method achieves up to three times the throughput of the state-of-the-art lock-free MCAS algorithm. Moreover, the results indicate that version embedding is sufficient to prevent the ABA problem in practical scenarios. key words: lock-free algorithm, multi-word compare-and-swap (MCAS), contention-aware optimization, ABA problem prevention
1.
Introduction
Efficient concurrent access to shared data structures is essential for achieving high performance in in-memory databases [1] and complex index structures [2]. Although many systems employ lock-based synchronization, this approach incurs performance overheads and liveness issues, such as deadlocks, which can constrain overall scalability. In contrast, algorithms utilizing the compare-and-swap (CAS) instruction can eliminate the need for locks and facilitate the construction of non-blocking data structures. Such algorithms and structures are considered lock-free if they guarantee system progress as long as at least one thread remains active [3]. For example, most lock-based structures possess the deadlock-free property, which requires that all threads remain active to guarantee progress; if a lock holder halts or terminates unexpectedly, other threads may be unable to proManuscript received January 1, 2024. Manuscript revised January 1, 2024. † Graduate School of Informatics, Nagoya University, Nagoyashi DOI: 10.1587/trans.E0.??.1
ceed because of an abandoned lock. Lock-free algorithms maintain progress even in the presence of inactive threads, thereby providing more robust processing. Although lock-freedom is a highly desirable property, designing correct lock-free algorithms remains a significant challenge. The CAS instruction atomically compares a single memory word with an expected value and, only if they match, stores the desired value in the target region. Additionally, because the CAS instruction returns the current (pre-swapped) value, a thread can determine whether the operation succeeded: if the returned value matches the expected value, the CAS succeeded. The CAS instruction is a powerful primitive with “universality” for synchronization in shared memory, enabling an unbounded number of threads to reach consensus [4]. Consequently, non-blocking algorithms and data structures using CAS have been the subject of extensive research for many years [5–7]. However, maintaining consistency across multiple memory locations using only single-word operations significantly complicates algorithm design and implementation. To address this challenge, prior work has proposed a multi-word compare-and-swap (MCAS) operation, which atomically swaps multiple words while guaranteeing disjoint-access-parallel execution [8, 9]. Because the CAS instruction operates on a single word, it can introduce unavoidable intermediate states within target data structures. In contrast, MCAS enables the simultaneous swapping of multiple words, thereby eliminating intermediate states and significantly reducing the implementation complexity of lockfree algorithms. As a result, several recent works, including BzTree [10] and the concurrent programming library kcas [11], employ MCAS as a core component. However, current lock-free MCAS implementations encounter two major challenges. First, the helping mechanism required to ensure lock-freedom can degrade performance. Lock-free MCAS relies on helper procedures to advance intermediate MCAS states; otherwise, abandoned intermediate states may compromise lock-freedom. Although this mechanism allows MCAS operations to progress even in the presence of slower or suspended threads, helpers may concurrently modify the same memory regions (i.e., MCAS target words) using CAS. This concurrent modification leads to mutual CPU cache invalidations, thereby degrading overall MCAS performance. Second, existing lock-free MCAS algorithms [9, 12] exhibit logical vulnerabilities related to the ABA problem [13]. Although the details of this issue are discussed in Section 5, briefly, the ABA problem among
Copyright © 200x The Institute of Electronics, Information and Communication Engineers
IEICE TRANS. ??, VOL.Exx–??, NO.xx XXXX 200x
2
helpers can result in redundant execution of the same MCAS operations. While this problem is rare due to the complexity of the required conditions, it can cause inconsistent behavior in specific edge cases. This paper proposes an efficient and robust lock-free MCAS algorithm to address these challenges. First, a contention-aware approach is introduced to control the helping mechanism. Unlike existing methods, the proposed approach does not immediately assist intermediate MCAS operations; instead, it verifies whether assistance is genuinely necessary. This reduces the number of concurrent helpers, thereby mitigating cache contention while preserving lockfreedom. Furthermore, version embedding [14] is introduced to practically mitigate the ABA problem. The fundamental cause of the ABA problem is that helpers cannot distinguish whether an expected value remains unchanged or has been modified and subsequently restored. Although version embedding does not entirely eliminate the ABA problem, experimental results demonstrate that this approach is sufficient to prevent specific edge cases. The core contributions of this work are summarized below. • The proposed method introduces a contention-aware helping mechanism to MCAS using an entry counter that provides helpers with the current contention state. This mechanism enables helpers to select helping or backing off to achieve efficient MCAS while maintaining lock-freedom. • This paper identifies a logical flaw in existing MCAS algorithms. Section 5 details how the CASN algorithm results in a duplicated MCAS operation due to its optimization for memory footprint. • The proposed algorithm introduces version embedding to avoid inconsistent MCAS operations. Although this approach requires all MCAS target regions to reserve several bits, embedded versions practically prevent the ABA problem in certain edge cases. • The effectiveness of the proposed approach is demonstrated through exhaustive experiments. Experimental results show that the proposed approach achieves up to three times the throughput of the state-of-the-art lockfree MCAS algorithm under high contention. This performance reaches that of a deadlock-free method that avoids mutual CPU cache invalidations by sacrificing lock-freedom. • We provide reference implementations, including the proposed method and other comparison methods, as a C++ library [15]. The remainder of this paper is organized as follows. Section 2 reviews related work, and Section 3 provides an overview of the proposed method. The details of the proposed method are presented in Sections 4 and 5: Section 4 discusses the contention-aware helping mechanism, and Section 5 addresses consistency through version embedding. Section 6 evaluates the proposed method through experiments, and Section 7 concludes the paper.
2.
Related Work
This section reviews existing methods for concurrent multiword modification. In addition to established MCAS algorithms, this section discusses alternative approaches for atomically reading and modifying disjoint memory regions. The following discussion assumes that all MCAS target regions can be ordered to prevent procedural deadlocks. If any MCAS algorithm attempts to swap words in an inconsistent order, it can cause deadlocks. For example, if one thread swaps target regions A and B, while another thread swaps them in the reverse order, B and A, a conflict arises. In this scenario, both threads encounter the other thread’s intermediate MCAS and are unable to complete both operations. Therefore, all MCAS operations must adhere to a specific order, such as the sequence of logical memory addresses. 2.1
Alternative Approaches to Multi-Word Modification
Several alternatives exist for multi-word modification, including k-compare-single-swap (k-CSS) [16] and the combination of load-link-extended (LLX) and store-conditionalextended (SCX) [17]. These methods demonstrate high efficiency for specific data structures but have limitations in general-purpose use. Although k-CSS can atomically compare multiple words, it swaps only a single word at a time. Consequently, k-CSS cannot prevent the emergence of intermediate states in lock-free data structures. LLX and SCX are extensions of the LL and SC instructions that can avoid the ABA problem. However, using LLX and SCX requires dedicated metadata within the target data structures. Transactional memory is another alternative for multiword modification. There are two approaches to transactional memory: hardware transactional memory (HTM) [18] and software transactional memory (STM) [19]. HTM is more efficient than STM but relies on specific hardware support. Although STM does not depend on specific hardware, accessing memory through STM introduces unavoidable overhead. Furthermore, transactional memory is subject to transaction aborts resulting from size limitations or opaque conflicts. Several methods, including the multiplecompare-multiple-swap (MCMS) operation [20], have been proposed to leverage transactional memory. However, fundamental limitations persist. 2.2
MCAS Algorithms
There are several algorithms to perform MCAS operations. These algorithms guarantee different types of progress: wait-freedom [21, 22], lock-freedom [9, 12], or deadlockfreedom [23]. However, the objective of this work is to achieve high-performance MCAS processing. Given the inherent complexity of wait-free MCAS algorithms, this section focuses on lock-free and deadlock-free algorithms. The CASN algorithm [9] is the first practical MCAS implementation without specific hardware limitations; thus,
UNNO et al.: EFFICIENT AND ROBUST LOCK-FREE MULTI-WORD COMPARE-AND-SWAP VIA CONTENTION-AWARE HELPING
3
most existing methods have followed this approach. For each operation, CASN prepares a descriptor containing all necessary information about the corresponding MCAS. CASN then embeds the descriptor’s address into every MCAS target region as a reservation. If all embeddings succeed, the MCAS operation also succeeds. If the MCAS succeeds, CASN updates the descriptor’s status to SUCCEEDED and replaces the embedded descriptors with the desired values. Descriptors also serve as the mechanism for ensuring lockfreedom. If a thread finds an embedded descriptor, indicating the presence of an intermediate MCAS, it can help complete the MCAS using that descriptor. Although CASN is applicable across various environments, including persistent memory [24], it requires nested descriptor embedding that involves both CASN and restricted-double-compare-singleswap (RDCSS) descriptors. This requirement results in a non-negligible number of CAS instructions per MCAS operation, leading to significant performance overhead. The AOPT algorithm reduces excessive CAS instructions in CASN to improve performance [12]. CASN replaces embedded descriptors with actual values for each MCAS operation, while AOPT retains descriptors within MCAS target regions. As described above, each descriptor contains all information about the MCAS, including its current status: UNDECIDED, FAILED, or SUCCEEDED. When a thread finds an UNDECIDED descriptor, it first helps the pending operation to complete. Otherwise, it can look up the actual value in the descriptor: the expected value for FAILED and the desired value for SUCCEEDED. This indirect reference eliminates the need for nested descriptor embedding and write-back CAS instructions. However, this approach introduces trade-offs in both read performance and memory footprint. Using indirect references incurs unavoidable overhead for each read operation. Furthermore, because embedded descriptors may remain throughout the process, additional garbage collection is necessary to prevent memory waste. Deadlock-free MCAS seeks to improve operational efficiency by sacrificing lock-freedom [23]. In lock-free MCAS, the overhead of helper mechanisms and garbage collection leads to performance bottlenecks under high contention. To address this issue, the deadlock-free MCAS omits the helping mechanism and waits for intermediate MCAS operations to complete. This approach does not guarantee lock-freedom, but it avoids mutual CPU cache invalidations and the need for descriptor garbage collection. As a result, the deadlockfree MCAS has achieved better performance than existing lock-free MCAS algorithms. The proposed method aims to reach this performance while achieving lock-freedom. 3.
caused by conflicts, and version embedding that prevents the ABA problem and ensures lock-freedom. Since the mechanisms and theoretical backgrounds of these optimizations are discussed in the subsequent sections, this section focuses solely on the basic components of the proposed method. 3.1
MCAS Descriptor Structure
Similar to existing methods, the proposed method prepares a descriptor for each MCAS operation. The descriptor reserves each target-word region by embedding its pointer into the regions, thereby linearizing concurrent MCAS operations. Because MCAS descriptors and their embeddings play a central role in MCAS algorithms, we first describe their data structures and layouts below. Each target-word region consists of 64 bits and retains either an actual value or a pointer to an MCAS descriptor. To distinguish between actual values and descriptor pointers, we use the most significant bit (MSB) as a control bit: 0 indicates a value, and 1 indicates a pointer. If the control bit is 0, the remaining bits contain actual data along with version information for ABA detection (details are described in Section 5). If the control bit is 1, the remaining bits contain the address of the corresponding descriptor with metadata used for the helper procedure (details are described in Section 4). Fig. 1 illustrates the data structure of MCAS descriptors in the proposed method. The status field indicates the progress of an MCAS operation and can take one of three states: UNDECIDED, SUCCEEDED, or FAILED. The n field indicates the number of target words for each MCAS operation. The targets field is an array that retains information for each target CAS operation. Each entry has three fields: • addr: The address of a target-word region, • expected: An expected (i.e., old) value in a target region, and • desired: A desired (i.e., new) value. In descriptors, the targets field is statically allocated to accommodate the maximum number of target words allowed per MCAS operation. The maximum number can be specified via CMake’s compile definitions, with 8 as the default value. Note that each descriptor is aligned to 64-byte addresses (i.e., cache lines) to prevent false sharing [25] in our implementation. Thus, regardless of the maximum number of targets, no descriptor shares a cache line.
Method Overview
This section describes the data structure and the basic procedures of our MCAS algorithm. The proposed method builds on the deadlock-free MCAS algorithm [23] and introduces two key mechanisms to achieve both efficiency and lockfreedom: helper control that reduces cache invalidations
targets[ ]
status n addr 1 expected 1 addr 2 expected 2 ... ... addr n expected n
desired 1 desired 2 ... desired n
Fig. 1: MCAS descriptor structure.
IEICE TRANS. ??, VOL.Exx–??, NO.xx XXXX 200x
4
3.2
Procedures of MCAS and Read Operations
Figs. 2 and 3 present the pseudocode for our MCAS and Read operations, respectively.† Similar to existing methods, we prepare the Read algorithm to load the current value from a target-word region. Since target-word regions may contain descriptor pointers, accessors could misinterpret these pointers as actual data without the Read algorithm. Then, updaters perform an MCAS operation with the loaded values to atomically swap multiple words. It is also worth noting that we expect a single CAS instruction to work as shown in Fig. 4. Besides, when embedding descriptors, we use test-and-test-and-set (TATAS) operations [26] instead of simple CAS instructions to avoid unnecessary CPU cache invalidation. However, for simplicity, we just use CAS to refer to TATAS here. 3.2.1
MCAS Operation
The proposed MCAS algorithm consists of two phases: the descriptor-embedding phase on lines 2–8 and the finalization phase on lines 10–14. Note that Fig. 2 alone does not guarantee consistency when helper procedures are executed concurrently; we explain how to ensure consistency in Section 5. Phase 1 (Embedding a descriptor pointer): A worker thread, which executes a certain MCAS operation, first embeds the pointer to the corresponding descriptor into every target-word region using CAS instructions. If every region contains the expected values or its own descriptor address, which may be embedded in advance by helpers, the embedding phase succeeds. Otherwise, if any target regions have been modified or are involved in other MCAS operations, the thread considers the embedding a failure. Note that our MCAS algorithm does not call a helper procedure for another descriptor because the target regions will be modified by other MCAS operations, which would cause the ongoing MCAS operation to fail. Thus, the thread just retries from reading the current values, and the Read algorithm will call a helper procedure if needed. After embedding, the thread updates the descriptor’s status (SUCCEEDED or FAILED) by a CAS instruction, which ensures all the threads (including helpers) can agree on the operation’s outcome. Phase 2 (Finalizing MCAS by swapping to values): In this phase, the worker thread replaces the embedded pointers with actual values to finalize its own MCAS operation. If the descriptor’s status is SUCCEEDED, the thread stores the desired (i.e., new) values and completes the MCAS operation. Otherwise, the thread returns to the expected (i.e., old) values to abort the MCAS operation. Since helpers may perform these replacements concurrently, using CAS instructions is mandatory to avoid redundant updates and concurrency issues. † In the algorithms, a period indicates a reference to a field
within a data structure.
Input: 𝑑𝑒𝑠𝑐 // MCAS descriptor Output: 𝑠𝑢𝑐𝑐𝑒𝑒𝑑𝑒𝑑 // True on success 1 if 𝑑𝑒𝑠𝑐.𝑠𝑡𝑎𝑡𝑢𝑠 = UNDECIDED then 2 𝑠𝑡𝑎𝑡𝑢𝑠 ← SUCCEEDED 3 foreach 𝑡 ∈ 𝑑𝑒𝑠𝑐.𝑡𝑎𝑟𝑔𝑒𝑡𝑠 do 4 𝑤𝑜𝑟𝑑 ← CAS(𝑡.𝑎𝑑𝑑𝑟, 𝑡.𝑒𝑥 𝑝𝑒𝑐𝑡𝑒𝑑, 𝑑𝑒𝑠𝑐) 5 if 𝑤𝑜𝑟𝑑 ≠ 𝑡.𝑒𝑥 𝑝𝑒𝑐𝑡𝑒𝑑 ∧ 𝑤𝑜𝑟𝑑 ≠ 𝑑𝑒𝑠𝑐 then 6 𝑠𝑡𝑎𝑡𝑢𝑠 ← FAILED 7 break 8
CAS(𝑑𝑒𝑠𝑐.𝑠𝑡𝑎𝑡𝑢𝑠, UNDECIDED, 𝑠𝑡𝑎𝑡𝑢𝑠)
9 𝑠𝑢𝑐𝑐𝑒𝑒𝑑𝑒𝑑 ← (𝑑𝑒𝑠𝑐.𝑠𝑡𝑎𝑡𝑢𝑠 = SUCCEEDED) 10 foreach 𝑡 ∈ 𝑑𝑒𝑠𝑐.𝑡𝑎𝑟𝑔𝑒𝑡𝑠 do 11 if 𝑠𝑢𝑐𝑐𝑒𝑒𝑑𝑒𝑑 then 12 CAS(𝑡.𝑎𝑑𝑑𝑟, 𝑑𝑒𝑠𝑐, 𝑡.𝑑𝑒𝑠𝑖𝑟𝑒𝑑) 13 else 14 CAS(𝑡.𝑎𝑑𝑑𝑟, 𝑑𝑒𝑠𝑐, 𝑡.𝑒𝑥 𝑝𝑒𝑐𝑡𝑒𝑑)
Fig. 2: Proposed lock-free MCAS algorithm.
Input: 𝑎𝑑𝑑𝑟𝑒𝑠𝑠 // Target location Output: 𝑣 // Actual value in address Output: 𝑤𝑜𝑟𝑑 // Current state of address 1 while true do 2 𝑤𝑜𝑟𝑑 ← load a value from 𝑎𝑑𝑑𝑟𝑒𝑠𝑠 3 if 𝑤𝑜𝑟𝑑 contains an actual value then break 4 Wait briefly before helping the found MCAS 5 𝑤𝑜𝑟𝑑+ ← increment the entry counter of 𝑤𝑜𝑟𝑑 6 𝑤𝑜𝑟𝑑 ′ ← CAS(𝑎𝑑𝑑𝑟𝑒𝑠𝑠, 𝑤𝑜𝑟𝑑, 𝑤𝑜𝑟𝑑+ ) 7 if 𝑤𝑜𝑟𝑑 ′ = 𝑤𝑜𝑟𝑑 then 8 MCAS(𝑤𝑜𝑟𝑑) // Help found MCAS 9
𝑣 ← remove a version counter from 𝑤𝑜𝑟𝑑
Fig. 3: Read algorithm for MCAS target regions.
Input: 𝑎𝑑𝑑𝑟 𝑒𝑠𝑠 // Target location Input: 𝑒𝑥 𝑝𝑒𝑐𝑡𝑒𝑑 // Expected old value Input: 𝑑𝑒𝑠𝑖𝑟 𝑒𝑑 // Desired new value Output: 𝑤𝑜𝑟 𝑑 // Original value at the target location 1 𝑤𝑜𝑟 𝑑 ← load a word from 𝑎𝑑𝑑𝑟 𝑒𝑠𝑠 2 if 𝑤𝑜𝑟 𝑑 = 𝑒𝑥 𝑝𝑒𝑐𝑡𝑒𝑑 then 3 store 𝑑𝑒𝑠𝑖𝑟 𝑒𝑑 into 𝑎𝑑𝑑𝑟 𝑒𝑠𝑠
Fig. 4: Expected CAS behavior.
3.2.2
Read Operation
The Read algorithm may call a helper procedure to ensure lock-freedom. However, we avoid helping as much as possible because frequent (and redundant) helping can worsen the entire performance. We detail helper controls in Section 4 and only explain the basic procedure here. Besides, although the Read algorithm returns the current state of a target region (𝑤𝑜𝑟 𝑑), we explain its usage in Section 5. Our algorithm waits for other threads to complete their MCAS operations, if any exist. Because MCAS operations finish quickly (at most several microseconds) in most
UNNO et al.: EFFICIENT AND ROBUST LOCK-FREE MULTI-WORD COMPARE-AND-SWAP VIA CONTENTION-AWARE HELPING
5
cases, we use a momentary sleep call or give an occasion for rescheduling CPU resources to await a found MCAS. If the same pointer to the descriptor has remained after waiting, we help to complete it. This procedure continues until an actual value is found and returned. 4.
Table 1: Bit fields for embedding descriptor addresses. Bit Range
Content
63 62–50 49–47 46–0
Control bit (value is 1) Entry counter Target index Descriptor address
Contention-Aware Helping for CPU Efficiency
Executing the helping procedure to guarantee lock-freedom can cause conflicts over the same MCAS operation, potentially leading to excessive cache invalidation. Deadlock-free MCAS algorithms do not require any help and simply wait for other MCAS operations to complete, if any are found. However, lock-free MCAS algorithms require helpers to ensure progressiveness, and the helpers try to modify the same memory regions to complete the same MCAS. Because this invalidates the CPU cache for each helper, excessive cache synchronization reduces overall performance. To avoid such cache invalidation, we control the frequency of helping procedure calls using exponential backoff [26]. In contrast to existing lock-free data structures, such as lock-free queues [14], the helping procedure for MCAS operations involves complex steps and multiple CAS instructions. This means that failing to help results in both excessive cache invalidation and wasted CPU cycles. Thus, after short spinning with NOP instructions [26], we make a helper sleep for exponential backoff, as shown in Fig. 3.† When the same MCAS descriptor remains at the target region after backoff, the helper calls the helping procedure. Furthermore, helping can be managed more effectively by introducing entry counters. An entry counter is embedded into each target region along with the corresponding descriptor pointer, as shown in Table 1, and indicates the number of threads that have joined to help the MCAS operation. That is, even if multiple threads find the descriptor in the same region, they can detect the existence of preceding helpers after backoff. Thus, threads do not begin helping if a preceding helper exists, and use the number of helpers as the exponent for exponential backoff. After backoff, if no new helper arrives, threads try to increment the entry counter using CAS and begin helping if it succeeds. Note that the target index field indicates its index in the MCAS target regions. Because other threads have already embedded the descriptor pointer in previous target regions, helpers use this field to begin helping from the next target region. Fig. 5 illustrates how to control the execution of helper procedure calls using an entry counter. In the example, two threads access the same target region and find the descriptor pointer with the corresponding entry counter. Since the counter is 0, after backoff, Thread 1 performs a CAS instruction to increment the counter and successfully enters helping. On the other hand, Thread 2 detects that the counter † Because the optimal settings for the number of spin-loops and
sleep duration depend on the execution environment, we provide compile-time options to set them. By default, helpers loop 10 times for spinning and sleep 10 microseconds as the base of exponential backoff.
( The subscript of "desc" is the entry counter. ) target
desc0 load
Thread 1
load Backoff
load
Thread 2
desc2
desc1 CAS load Backoff
load
CAS
Backoff
Fig. 5: Example of contention-aware helping in execution. has been modified and that a new helper has joined to complete this MCAS operation. Thus, Thread 2 waits again and tries to enter helping after backoff. In this way, the proposed method limits the number of concurrent helpers, preventing numerous threads from helping the same MCAS operation. Note that we also use entry counters for efficient memory management. When there are helpers for a certain MCAS operation, the MCAS descriptor must be freed via any garbage collection (e.g., epoch-based memory reclamation [27]) to prevent incorrect memory reuse. However, the owner of the MCAS descriptor can detect the existence of helpers from the entry counters in every target region. If there is no helper, the owner can store the descriptor in its threadlocal storage and safely reuse it for future MCAS operations. In low-contention (conflicts seldom occur) environments, this approach significantly reduces garbage collection costs and improves CPU and memory efficiency. 5.
Ensuring Consistency Through Version Embedding
Ensuring consistency is a critical challenge in implementing lock-free MCAS algorithms. In lock-free MCAS algorithms, worker threads may call helper functions and perform the same MCAS operation concurrently. The existing MCAS algorithms work correctly in most situations, but can lead to inconsistent results due to these helpers. In this section, we first introduce an example in which the CASN algorithm may redundantly perform the same MCAS operation due to an incorrect combination of its helper function and memory optimization. Then, we explain how the proposed method ensures consistency using version embedding. 5.1
Inconsistent MCAS Executions in Existing Methods
The root cause of inconsistent MCAS executions is the ABA problem. The ABA problem is a well-known issue in programming with CAS instructions: when a thread attempts
IEICE TRANS. ??, VOL.Exx–??, NO.xx XXXX 200x
6
to perform a CAS instruction with a certain expected value (A), it cannot distinguish whether the current memory state is unchanged (A) or has been modified and restored (ABA). In MCAS algorithms, the ABA problem arises in descriptor embedding and removal. For example, when a thread helps an MCAS operation using a found descriptor, it first tries to replace the expected value in the target region with the descriptor pointer. However, the thread cannot determine whether the target region has been restored to the same value after this MCAS operation completes, or whether it remains truly unchanged. The thread also cannot determine whether the embedded descriptor is correct if descriptor regions can be reused: another thread may reuse the same descriptor and embed it into the same target region. The existing algorithms avoid the ABA problem by leveraging the irreversibility of the progress states on descriptors and epoch-based memory reclamation. The status of a descriptor must be SUCCEEDED or FAILED after completion and must never revert to UNDECIDED. Even if a helper incorrectly embeds a descriptor, it can recognize the completion of the corresponding MCAS and can stop helping. Besides, epoch-based memory reclamation prevents other threads from reusing descriptor regions until it ensures that no one is referring to them. That is, embedded descriptors must not be reused by others, which prevents incorrect descriptor removal from target-word regions. However, the CASN algorithm may cause the ABA problem due to its memory optimization.† We introduce an example in Fig. 6 to show redundant MCAS executions in the CASN algorithm. In the example, three worker threads perform the same 2wCAS operation. Thread T1 is the owner of this 2wCAS and embeds the descriptors into the target regions (Step 1). Note that the CASN algorithm uses two types of descriptors to ensure consistency: CASN (cd) and RDCSS (rd). Then, T2 finds the RDCSS descriptor in the second target region and confirms that the 2wCAS’s status is UNDECIDED (Step 2). T3 similarly finds the incomplete CASN descriptor in the first target region (Step 3). Here, suppose that T2 and T3 begin helping but then fall asleep for any reason (e.g., CPU overuse). T1 embeds the CASN descriptor into the second region and continues until completion during this sleep (Step 4). After the 2wCAS’s completion, other threads can modify the second region and restore the expected (A) value (Step 5). T2 and T3 may awaken here, but they cannot recognize the completion of the 2wCAS operation because they have already confirmed its status in Steps 2 and 3. Thus, T3 continues helping by swapping the expected value with the RDCSS descriptor (Step 6), and T2 also swaps the RDCSS and CASN descriptors (Step 7). As a result, the CASN descriptor is embedded in the second region twice, leading to redundant execution of the 2wCAS operation. The CASN algorithm can avoid the ABA problem by excluding its memory optimization, but this solution will worsen execution performance and memory efficiency. In † The AOPT algorithm has a similar issue, but we omit its
explanation here due to the page limit.
T1
T2
words
T3
(1) CAS(old→rd) (2)
read read
(3)
cd
A
cd
rd
status Undecided
read read
(4) T1 advances MwCAS Operation B
B
Succeeded
(5) Another MwCAS reverts the 2nd word to old (6) CAS(old→rd) (7)
*
A
*
rd
*
cd
CAS(rd→cd)
Fig. 6: Inconsistency caused by CASN algorithm.
the CASN algorithm, CASN and RDCSS descriptors share the same memory region to use memory efficiently: a CASN descriptor holds RDCSS descriptors for each target in its region. However, this sharing makes it impossible to determine whether the embedded RDCSS descriptors are correct or are redundantly restored, as they share the same addresses. If every helper prepares different (i.e., dynamically allocated) RDCSS descriptors, the first and second embedded descriptors into the same region can have different addresses. This leads to CAS failures in Step 7 in Fig. 6, but excessive memory allocation and reclamation will decrease overall MCAS performance. 5.2
Avoiding the ABA Problem via Version Management
As described above, it is challenging to strictly avoid the ABA problem while achieving high-performance MCAS. Although the ABA problem can be solved by using massive memory or by sacrificing MCAS performance, we propose a more practical solution by relaxing the restriction. Inconsistent MCAS executions almost never occur because they require extremely stringent conditions, as shown in Fig. 6. However, the existing methods cannot provide information on their safety, so users cannot fully rely on the execution results. Thus, our approach aims to provide a mechanism for controlling safety rather than ensuring strict ABA avoidance. In the proposed method, we avoid the ABA problem by embedding a version counter [13] into each target region. As shown in Step 5 of Fig. 6, the ABA problem occurs when any thread reverts a target region to its corresponding expected value. Helper threads cannot determine whether a target region is unchanged without additional information, such as the unique addresses of dynamically allocated RDCSS descriptors in CASN. Thus, the proposed method maintains
UNNO et al.: EFFICIENT AND ROBUST LOCK-FREE MULTI-WORD COMPARE-AND-SWAP VIA CONTENTION-AWARE HELPING
7
the version for each target region as additional information, as shown in Table 2. Version counters are incremented when the corresponding MCAS operations successfully update their target regions. These version changes allow helpers to recognize the corresponding MCAS completions, thereby avoiding the ABA problem. Note that version counters are only combined with actual values. Since we can avoid the ABA problem in descriptor removal using descriptor status and epoch-based memory reclamation, embedded descriptor pointers do not have versions and only maintain their metadata, as shown in Table 1. Our approach may also lead to inconsistency if the version bit fields overflow and wrap around, but the likelihood can be controlled by changing the number of version bits. In our implementation, users can specify the number of version bits at compile time. We use 15 bits as the default setting, as shown in Table 2, because common OSes provide 48 bits of user-space memory. We evaluate this setting in Section 6 and show that 15 bits are sufficient to prevent the ABA problem while supporting the implementation of lock-free data structures. Below, we explain how versions are managed during the proposed MCAS algorithm. Descriptor Preparation: Our Read algorithm fetches both the actual value and the embedded version counter from a target region. While existing methods do not embed metadata and directly use actual values as expected ones, our approach requires entire words—including version counters— for future MCAS operations. Thus, our Read algorithm returns the actual value and the entire word, as shown in Fig. 3, to compute a desired value from the actual value and use the entire word as the expected state. Descriptor Embedding: When each thread embeds a descriptor into the target regions, it uses the expected word states—including version counters—for CAS instructions. Thus, even if a certain target region is modified and reverted to its expected value, the corresponding version counter will detect it and safely ensure consistency. Note that if a thread finds other MCAS descriptors in its target regions, our MCAS algorithm immediately fails and does not help those operations, as shown in Fig. 2. Although the found MCAS operations may fail and keep the target regions unchanged, in most cases, they will modify the actual values or the version counters. Therefore, to eliminate wasteful processing, our MCAS algorithm fails early and prompts the thread to retry from reading the target regions. Descriptor Removal: When an MCAS operation succeeds, the version counters of the corresponding target re-
gions are incremented by 1 during descriptor removal. Otherwise, the version counters remain unchanged during MCAS aborts. The ABA problem occurs only when the target regions are swapped and reverted; it first requires that MCAS operations succeed. Thus, it is sufficient to update the version counters upon MCAS success. Note that the version counters are embedded within the expected word states in a descriptor, allowing helper threads to reference and increment them as well.
Table 2: Bit fields for embedding version counters alongside actual values.
Table 3: Experimental environment.
Bit Range
Content
63 62–48 47–0
Control bit (value is 0) Version Actual value
6.
Evaluation
This section evaluates the performance and robustness of the proposed method. First, the experimental setup and methodology are described. Next, the proposed method is compared to existing MCAS algorithms in terms of throughput and latency. Furthermore, the effectiveness of the consistency guarantee provided by the version counter embedding is evaluated. 6.1
Experimental Setup
The server specifications used for the experiments are presented in Table 3. All related artifacts, including the proposed method and comparison methods, were implemented in C++ [15]. The proposed method (denoted as Ours) is compared against three implementations: CASN, AOPT, and the deadlock-free MCAS (denoted as DLF). Our benchmark program repeatedly executes MCAS operations until a 10-second timeout is reached. MCAS target regions consist of an array of one million words, initially set to zero. The logical address of each word is aligned with the cache line size (64 bytes) to prevent false sharing [25]. Each MCAS operation randomly selects a specified number of words and atomically increments their values by one. The selection probability for each word follows a Zipf distribution with parameter 𝛼, defined as: 1/𝑘 𝛼 𝑓 (𝑘; 𝛼, |𝑊 |) = Í |𝑊 | , 𝛼 1/𝑛 𝑛=1
(1)
where |𝑊 | is the size of the target regions (106 ). When 𝛼 = 0, the selection probability is uniform, which is referred to as low contention. When 𝛼 = 1, the access probability to specific words (the 𝑘-th region) is concentrated in proportion to 1/𝑘, which is referred to as high contention. The experiments were conducted five times per condition, and the average values for throughput and latency were
Item
Value
CPU RAM OS Compiler
Intel(R) Xeon(R) Gold 6258R (two sockets) DIMM DDR4 (Registered) 2933 MHz (16GB × 12) Ubuntu 22.04.5 LTS GNU C++ ver. 11.4.0
IEICE TRANS. ??, VOL.Exx–??, NO.xx XXXX 200x
8
Performance Scaling with Thread Count
Figure 7 shows the throughput and latency of CAS2 under low contention as the number of threads increases. Vertical dashed lines indicate the boundaries between conditions with and without oversubscription. The proposed method consistently achieves higher throughput than the existing lockfree MCAS algorithms, reaching approximately twice the throughput at 112 threads. This performance is close to that of DLF. Furthermore, while CASN and AOPT’s throughput decreases with oversubscription (1,024 threads) due to their complexity and memory management, the proposed method maintains its efficiency. Regarding latency, the proposed method is also consistently lower; at 112 threads, its latency is about one-fourth that of CASN. While CASN and AOPT show increased latency as the thread count grows, the proposed method remains nearly constant and close to DLF. Figure 8 shows the results for CAS2 under high contention. Without oversubscription, the proposed method reaches the performance of DLF. When using 112 threads,
6.3
Figure 9 shows experimental results for CAS2 with 112 threads (i.e., without oversubscription) over different skew parameters. Similar to existing methods, the proposed method performs well at low contention but deteriorates rapidly as contention increases. However, the proposed method consistently outperforms the existing lockfree MCAS algorithms and achieves performance close to that of DLF. This indicates that the contention-aware helping mechanism effectively alleviates contention and performance drops. Figure 10 shows experimental results for CAS2 with 1,024 threads (i.e., with oversubscription). With some skew parameters, such as around 0.75, the proposed method achieved slightly higher throughput than DLF. Although
1.E+00
1.E+01 AOPT Ours
CASN DLF 1.E-01
2 2 2 2 2 2 2 2 2 2 2 # of threads
AOPT Ours
2 2 2 2 2 2 2 2 2 2 2 # of threads
1.E+02
1.E+03
1.E+00 1.E-01 1.E-02
1.E+00 CASN
AOPT
DLF
Ours
1.E+03 1.E+02
2 2 2 2 2 2 2 2 2 2 2 # of threads
1.E+02 1.E+01 1.E-01 1.E-02
CASN DLF
CASN Ours
AOPT Ours
2 2 2 2 2 2 2 2 2 2 2 # of threads
(b) Latency
Fig. 8: Performance comparison of CAS2 across different thread counts under high contention (𝛼 = 1.0).
AOPT CASN DLF Ours
1.E+01 1.E+00 1.E-01
0 0.25 0.5 0.75 1 1.25 1.5 1.75 2 Skew parameter: 𝛼
(b) Latency
Fig. 9: Performance comparison of CAS2 across different skew parameters without oversubscription (112 threads).
1.E+04
1.E+00
AOPT DLF
1.E+02
0 0.25 0.5 0.75 1 1.25 1.5 1.75 2 Skew parameter: 𝛼
1.E+05 1.E+03
1.E+01
Latency [μs]
Throughput [M Ops/s]
1.E+04
1.E+01
(a) Throughput
Fig. 7: Performance comparison of CAS2 across different thread counts under low contention (𝛼 = 0).
(a) Throughput
1.E+05
1.E+02
(b) Latency
(a) Throughput
1.E-01
1.E+03
1.E-03
Throughput [M Ops/s]
1.E+00
CASN DLF
Throughput [M Ops/s]
1.E+02
Latency [μs]
Throughput [M Ops/s]
1.E+03
1.E+01
Robustness against Contention Skew
1.E+01 1.E+00 1.E-01 1.E-02
AOPT DLF
CASN Ours
1.E-03 0 0.25 0.5 0.75 1 1.25 1.5 1.75 2 Skew parameter: 𝛼
(a) Throughput
Latency [μs]
6.2
the proposed method achieves 12- and 3-times higher throughput than CASN and AOPT, respectively. Additionally, the proposed method’s latency is approximately one-tenth that of CASN and slightly lower than that of AOPT. These results suggest that the contention-aware helping mechanism successfully mitigates performance degradation during contention. With oversubscription, the proposed method’s performance decreases because it assists with backoff, which can delay MCAS completions. Even if helpers complete a given MCAS, its owner may continue assisting other MCAS operations and may sleep due to conflict. However, the proposed method maintains comparable or higher throughput than the existing lock-free MCAS algorithms under oversubscription.
Latency [μs]
calculated. Error bars represent the minimum and maximum values of the five measurements, respectively. Unless otherwise specified, the 99th percentile latency is used as the latency metric to compare the effect of tail latency. Hereafter, an MCAS operation targeting 𝑛 words is referred to as CAS𝑛; for example, a 2-word CAS is CAS2. Although experiments were performed with different word counts between CAS1 and CAS8, the results exhibit similar behavior and are thus omitted. Therefore, only results with CAS2 are presented below.
1.E+08 1.E+07 1.E+06 1.E+05 1.E+04 1.E+03 1.E+02 1.E+01 1.E+00 1.E-01
AOPT CASN DLF Ours 0 0.25 0.5 0.75 1 1.25 1.5 1.75 2 Skew parameter: 𝛼
(b) Latency
Fig. 10: Performance comparison of CAS2 across different skew parameters with oversubscription (1,024 threads).
UNNO et al.: EFFICIENT AND ROBUST LOCK-FREE MULTI-WORD COMPARE-AND-SWAP VIA CONTENTION-AWARE HELPING
1.E+07
1.E+06
1.E+06
1.E+05
1.E+05
1.E+04 1.E+03
helping-latency wraparound-interval
1.E+02
• Helping Latency (helping_latency): The average of the maximum times required for the helping process. • Wraparound Interval (wraparound_interval): The average time required for the version counter to wrap around. Each metric is not displayed if there is no helping process or wraparound. If helping_latency > wraparound_interval, an inconsistency can potentially occur because a helper may encounter a wraparound version. Otherwise, since no inconsistency can occur, the version embedding can ensure consistency in practice. Fifteen bits were used for version counters in this experiment, as a pessimistic estimate of the number of bits required to guarantee consistency. Although the optimal number of version bits depends on the application, this setting will demonstrate that 15 bits are sufficient to ensure consistency even under excessive MCAS operations. Note that while every thread performs MCAS operations continuously in the benchmark, real applications use them only when necessary. This results in fewer MCAS operations, preventing version counters from wrapping around in most use cases. First, the changes in these metrics as the skew parameter varies are discussed. Figure 11 shows measurements with 112 and 1,024 threads. These results show that the consistency is guaranteed across all skew parameters with 112 threads, but the ABA problem may occur with 𝛼 = 0.75 when using 1,024 threads. With 1,024 threads, wraparound_interval drops sharply while helping_latency maintains large values regardless of skew parameters. As a result, although helping_latency slightly decreases as the
helping-latency wraparound-interval
1.E+01 0 0.25 0.5 0.75 1 1.25 1.5 1.75 2 Skew parameter: 𝛼
0 0.25 0.5 0.75 1 1.25 1.5 1.75 2 Skew parameter: 𝛼
(a) 112 threads
(b) 1024 threads
Fig. 11: Measurements of helping latency and wraparound interval across different skew parameters. 1.E+7
1.E+7
1.E+6
1.E+6
1.E+5
1.E+5
1.E+1 1.E+0
wraparound-interval helping-latency
1.E+4 1.E+3
1.E+3 1.E+2
Finally, the effectiveness of the consistency guarantee provided by version counters is evaluated. While version counters mitigate the ABA problem, inconsistencies may arise when the counter wraps around. Thus, experiments were conducted to identify environments where such inconsistencies might occur. Two metrics were measured in each environment:
1.E+03
Duration [μs]
Empirical Safety Analysis of Version Embedding
1.E+04
1.E+02
1.E+01
1.E+4
6.4
Duration [μs]
1.E+07
Duration [μs]
DLF avoids excessive cache invalidations by eliminating the helping mechanism, under oversubscription, it allows incomplete MCAS descriptors to remain indefinitely and obstruct other operations. In contrast, the proposed method mitigates excessive cache invalidations through backoff while allowing the helping mechanism to remove those obstructing descriptors, thereby improving performance. Although DLF is superior to the proposed method under higher-contention settings, the performance difference is slight. Furthermore, the latency results show the robustness of the proposed method. CASN and AOPT exhibit unstable behavior due to their memory management, such as descriptor allocation and garbage collection. In contrast, the proposed method avoids unnecessary allocation and reclamation, resulting in robust tail latency.
Duration [μs]
9
wraparound-interval helping-latency 2 2 2 2 2 2 2 2 2 2 2 # of threads
(a) 𝛼 = 0.75
1.E+2 1.E+1 1.E+0 2 2 2 2 2 2 2 2 2 2 2 # of threads
(b) 𝛼 = 1.0
Fig. 12: Measurements of helping latency and wraparound interval across different thread counts. skew parameter increases, the two metrics invert at 𝛼 = 0.75. However, since such excessive oversubscription is unrealistic, we also investigate metric changes across thread counts under specific skew parameters. Figure 12 shows results with 𝛼 = 0.75 and 𝛼 = 1.0. As shown above, while the ABA problem may occur at 1,024 threads, the proposed method guarantees consistency at lower thread counts, even under oversubscription. These results suggest that allocating 15 bits is reasonable for sufficient safety and practicality; the remaining bits are available for pointers to construct any data structures. With respect to bit width, wraparound_interval scales exponentially, while helping_latency remains constant, ensuring greater safety predictability than existing lock-free algorithms. Users can adjust the bit width based on their MCAS frequency. 7.
Conclusion
In this paper, we propose a new lock-free MCAS algorithm. The proposed method enhances efficiency by controlling the helping mechanism based on contention states. Experimental results demonstrate that this contention-aware approach achieves up to three times the throughput of the state-ofthe-art lock-free MCAS algorithm in high-contention environments. Furthermore, this paper reveals logical flaws in existing MCAS algorithms that can lead to the ABA problem. To address this vulnerability, we introduce version embedding and demonstrate its practicality through experiments. However, version embedding does not completely eliminate the ABA problem. Therefore, our future work includes exploring performance optimizations for lock-free
IEICE TRANS. ??, VOL.Exx–??, NO.xx XXXX 200x
10
MCAS while guaranteeing strict consistency. Acknowledgments This work was partly supported by JSPS KAKENHI Grant Numbers JP23K24850, JP25K00161, JP25K21206, and JP26K02916. References [1] S. Tu, W. Zheng, E. Kohler, B. Liskov, and S. Madden, “Speedy transactions in multicore in-memory databases,” Proc. SOSP, pp.18– 32, 2013. [2] V. Leis, A. Kemper, and T. Neumann, “The adaptive radix tree: Artful indexing for main-memory databases,” Proc. ICDE, pp.38–49, 2013. [3] M. Herlihy, N. Shavit, V. Luchangco, and M. Spear, The Art of Multiprocessor Programming, second edition ed., ch. 3 Concurrent objects, Morgan Kaufmann, 2020. [4] M. Herlihy, “Wait-free synchronization,” ACM Transactions on Programming Languages and Systems, vol.13, no.1, pp.124–149, 1991. [5] M.P. Herlihy and J.M. Wing, “Linearizability: A correctness condition for concurrent objects,” ACM Transactions on Programming Languages and Systems, vol.12, no.3, pp.463–492, 1990. [6] G. Barnes, “A method for implementing lock-free shared-data structures,” Proc. SPAA, pp.261–270, 1993. [7] M. Moir, “Practical implementations of non-blocking synchronization primitives,” Proc. PODC, pp.219–228, 1997. [8] A. Israeli and L. Rappoport, “Disjoint-access-parallel implementations of strong shared memory primitives,” Proc. PODC, pp.151– 160, 1994. [9] T.L. Harris, K. Fraser, and I.A. Pratt, “A practical multi-word compare-and-swap operation,” Proc. DISC, pp.265–279, 2002. [10] J. Arulraj, J. Levandoski, U.F. Minhas, and P.A. Larson, “BzTree: A high-performance latch-free range index for non-volatile memory,” PVLDB, vol.11, no.5, pp.553–565, 2018. [11] V. Karvonen, B. Modelski, C. Morel, T. Leonard, K. Sivaramakrishnan, Y.N. Naidu, and S. Parimala, “Building a lock-free STM for OCaml,” Proceedings of the OCaml Workshop (ICFP), 2023. [12] R. Guerraoui, A. Kogan, V.J. Marathe, and I. Zablotchi, “Efficient multi-word compare and swap,” Proc. DISC, pp.4:1–4:19, 2020. [13] M. Herlihy, N. Shavit, V. Luchangco, and M. Spear, The Art of Multiprocessor Programming, second edition ed., ch. 10 Queues, memory management, and the ABA problem, Morgan Kaufmann, 2020. [14] M.M. Michael and M.L. Scott, “Simple, fast, and practical nonblocking and blocking concurrent queue algorithms,” Proc. PODC, pp.267–275, 1996. [15] M. Unno and K. Sugiura, “MwCAS.” available from https:// github.com/dbgroup-nagoya-u/mwcas. [16] V. Luchangco, M. Moir, and N. Shavit, “Nonblocking k-comparesingle-swap,” Proc. SPAA, pp.314–323, 2003. [17] T. Brown, F. Ellen, and E. Ruppert, “Pragmatic primitives for nonblocking data structures,” Proc. PODC, pp.13–22, 2013. [18] M. Herlihy and J.E.B. Moss, “Transactional memory: Architectural support for lock-free data structures,” Proc. ISCA, pp.289–300, 1993. [19] N. Shavit and D. Touitou, “Software transactional memory,” Proc. PODC, pp.204–213, 1995. [20] S. Timnat, M. Herlihy, and E. Petrank, “A practical transactional memory interface,” Proc. Euro-Par, pp.387–401, 2015. [21] H. Sundell, “Wait-free multi-word compare-and-swap using greedy helping and grabbing,” International Journal of Parallel Programming, vol.39, no.6, pp.694–716, 2011. [22] S. Feldman, P. LaBorde, and D. Dechev, “A wait-free multi-word compare-and-swap operation,” International Journal of Parallel Programming, vol.43, no.4, pp.572–596, 2015. [23] K. Sugiura and Y. Ishikawa, “Implementation of a multi-word
compare-and-swap operation without garbage collection,” IEICE Transactions on Information and Systems, vol.E105-D, no.5, pp.946– 954, 2022. [24] T. Wang, J. Levandoski, and P.Å. Larson, “Easy lock-free indexing in non-volatile memory,” Proc. ICDE, pp.461–472, 2018. [25] M. Herlihy, N. Shavit, V. Luchangco, and M. Spear, The Art of Multiprocessor Programming, second edition ed., ch. APPENDIX B Hardware basics, Morgan Kaufmann, 2020. [26] M. Herlihy, N. Shavit, V. Luchangco, and M. Spear, The Art of Multiprocessor Programming, second edition ed., ch. 7 Spinlocks and contention, Morgan Kaufmann, 2020. [27] K. Fraser, Practical Lock-Freedom, Ph.D. thesis, University of Cambridge, 2004.
Motoki Unno is a Master’s student in the Graduate School of Informatics, Nagoya University. He received his Bachelor of Informatics degree from Nagoya University in 2025. His research interests include concurrent programming, non-blocking data structures, and parallel computing.
Kento Sugiura is an Assistant Professor in the Graduate School of Informatics, Nagoya University. He received B.S., M.S., and Ph.D. degrees from Nagoya University in 2013, 2015, and 2018, respectively. His research interests include indexing techniques, data stream processing, and uncertain data management.
Yoshiharu Ishikawa is a Professor in the Graduate School of Informatics, Nagoya University. He received B.E., M.E., and Dr. Eng. degrees from University of Tsukuba in 1989, 1991, and 1995, respectively. His research interests include database system technologies such as indexing and query processing, spatio-temporal databases and data streams, and the integration of AI and DB technologies. He is a member of the Database Society of Japan, IPSJ, IEICE, JSAI, ACM, and the IEEE Computer Society.