Architectural Decoupling in Concurrent Data Structures

{"value":"

\\todo[inline]{This abstract feels a bit ``ai generated'', but it is clear and does a good job of summarizing the main contributions. See below for a few small suggestions.}

Concurrent programming has long been constrained by false dichotomies: programmability versus performance, generality versus efficiency, and composition versus specialization.%
Practitioners\\todo{I'd say ``Often, programmers must choose...''} must choose between easy-to-use abstractions with poor performance (software transactional memory, coarse-grained locking) or high-performance implementations requiring heroic effort (hand-tuned lock-free algorithms\\todo{I thought that you'd say ``hand-tuned fine-grained locking protocols, specialized non-blocking code'', so that you don't imply that all locks are bad}, specialized non-blocking code).
%
This dissertation challenges this conventional wisdom by demonstrating that these tradeoffs are not fundamental but rather artifacts of inadequate information exposure at layer boundaries.

The core insight is that by identifying and exposing the right semantic invariants—not just APIs, but the exact theoretical properties that enable safe optimization (consistency guarantees, conflict rules, object-metadata mappings)—through stable, architectural\\todo{what do you mean by ``architectural''?} contracts, systems can separate what must be correct (synchronization semantics) from what must be efficient (implementation strategies) while enabling incremental optimization.\\todo{This is a very long sentence. Can you split it and make sure it is easy for the reader to appreciate?}%
This principle is validated through three systems spanning shared memory, multi-structure composition, and distributed RDMA.

\\textbf{exoTM/STMCAS} (shared memory) exposes orec\\todo{``orec values'' is undefined. Consider ``low-level details of synchronization metadata''?} values as proofs of immutability, enabling programmers to checkpoint read-only traversals and safely transition to write steps\\todo{``safely...steps'' is undefined. ``execute consistent, atomic writes''?} without maintaining full transaction logs.%
Two policies coexist: STM for complex, uncommon paths and STMCAS for performance-critical operations.\\todo{Avoid ``policies''? ``Multiple APIs can coexist atop the synchronization layer''?}
%
Evaluation shows STMCAS-based data structures usually outperform hand-tuned baselines, reaching up to 1.35$\\times$ their throughput while preserving STM programmability where needed.

\\textbf{Harmony} (composition) exposes co-located but distinct metadata—operation-level synchronization (temporal ownership, versioning) and transaction-level conflict detection (transactional ownership, semantic/structural versions)—avoiding false conflicts when structural changes are mistaken for semantic conflicts.\\todo{This sentence is too long and has too many clauses for me to easily understand it}%
Three compatible techniques for expressing non-existence enable range queries.\\todo{Not a sentence?}
%
Evaluation on TPC-C shows Harmony matches or exceeds Medley, the state-of-the-art transactional data structure library, while supporting complex operations uncommon in prior systems.

\\textbf{RDMASTM} (RDMA-based) presents a layered architecture that separates data-structure logic, synchronization semantics, and hardware access through an Access \\& Placement Substrate (APS).%
APS sits between data structures and the synchronization layer, exposing pluggable policies—object-level caching, validation optimization, batching, clock management, and placement control—while hiding hardware-specific details.
%
Programmers structure objects to exploit spatial locality: fields placed in the same object benefit from single-operation cache fetch and validation-skip optimization, where the framework internally elides redundant orec checks when accessing multiple co-located fields within cached objects.
%
The readset trimming API (\\texttt{trim(n)}) provides orthogonal optimization—reducing commit-time validation overhead by 16--30\\% when data-structure semantics permit safe pruning—by leveraging structure-specific invariants.
%
On CloudLab deployments (1--8 nodes, four data structures, three workloads), object-level caching delivers the largest gains (nearly 2$\\times$ throughput, 50--80\\% RDMA reduction) by collapsing pointer-chasing and skipping redundant validations.
%
Clock and batching optimizations show workload-dependent effects: clock variants differ by $<$20\\%; batching helps (5--10\\%) only when memory concentrates and workloads are write-heavy, showing minimal benefit (within $\\pm$2--3\\%) when memory is distributed.
%
The stable field-level API (transactional operations) keeps data-structure algorithm logic unchanged—programmers add structural optimizations like anchors for hot metadata or cache-aware layouts for spatial locality—enabling systematic policy exploration while preserving STM correctness.

Across all three projects, stable contracts enable incremental refinement:%
Programmers start with correct-by-default implementations and selectively optimize performance-critical layers without rewriting data-structure logic.
%
The overarching contribution is establishing that right-sized architectural decoupling—exposing semantic invariants without leaking implementation details—achieves both programmability and performance across diverse synchronization domains, challenging decades of accepted tradeoffs in concurrent programming.

","attr0":"abstract"}