External-Memory, Concurrent and Distributed Structures

Introduction and Context

Classical data-structure analysis often assumes that every memory access has approximately the same cost and that one thread executes an algorithm at a time. Modern AI and ML systems violate both assumptions. Training datasets, feature histories, embeddings, model checkpoints, and event streams commonly exceed main memory; storage is hierarchical; and many CPU cores, machines, and availability zones may access the same logical index concurrently.

This chapter studies data structures designed for these conditions. The central design question is not merely whether an operation is asymptotically fast, but where data resides, how many pages or messages are transferred, how operations interact under contention, and what happens when a process or machine fails. The principal structures considered are external-memory search trees, log-structured merge (LSM) trees, lock-free structures, concurrent maps, and distributed indexes.

A useful unifying perspective is that performance depends on four resources:

1. Transfer cost: movement between storage levels or across a network.
2. Computation cost: CPU work performed per operation.
3. Contention cost: delay caused by competing operations.
4. Coordination and recovery cost: communication, replication, logging, and repair after failure.

The best structure depends on workload, hardware, consistency requirements, and failure model rather than on a single universal asymptotic bound.

Learning Objectives

By the end of this chapter, a learner should be able to:

• formulate and apply the external-memory, or I/O, model;
• explain why B-trees and B⁺-trees are appropriate for block storage;
• analyze LSM-tree write, read, space-amplification, and compaction trade-offs;
• distinguish blocking, optimistic, and non-blocking concurrency techniques;
• reason about linearizability, serializability, snapshot isolation, and eventual consistency;
• design concurrent maps using sharding, fine-grained synchronization, or lock-free methods;
• compare distributed-index partitioning, replication, quorum, and failure-recovery strategies;
• select an appropriate structure for an AI/ML data-serving workload.

1. The External-Memory Model

1.1 Why RAM complexity is insufficient

In an in-memory model, an array access and a pointer dereference are often treated as constant-time operations. In a storage hierarchy, a request may involve an L1 cache, DRAM, a local SSD, a remote object store, or another machine. The dominant cost can be transferring a block rather than comparing keys.

The external-memory model, also called the I/O model, represents data as blocks of size B records or bytes transferred between a fast memory of capacity M and a slower external store. An algorithm is evaluated primarily by the number of block transfers, denoted IO, while internal computation is treated separately.

If a file contains N records and each block stores B records, a sequential scan requires approximately

block transfers, assuming contiguous storage and no cache benefit. A random access may require one or more transfers per request. Thus, an algorithm that performs Θ(N) random accesses can be dramatically slower than one that performs Θ(N/B) sequential transfers.

The parameter B is measured in records or bytes consistently with N. M is the fast-memory capacity in the same unit. The model assumes that transfers occur in blocks and that computation within fast memory is comparatively inexpensive. Real systems add latency variation, caching, prefetching, compression, and parallel I/O, but the model remains an effective first approximation.

1.2 B-trees and B⁺-trees

A B-tree is a height-balanced multiway search tree. A node is sized to fit one storage page, so a single node visit usually requires one block transfer. If the branching factor is approximately F, the height of a tree containing N keys is approximately

More precisely, the height is bounded by logarithms determined by minimum and maximum occupancy. If every internal node has between t and 2t children, except possibly the root, then the tree remains balanced and updates require splitting or merging only along one root-to-leaf path.

A B⁺-tree stores separator keys and child pointers in internal nodes, while records or record pointers reside in leaves. Leaf pages are commonly linked, making range scans efficient. Search, insertion, and deletion require O(log_F N) page transfers in the worst case, and a range query returning K records requires approximately

transfers, assuming records are stored in leaf order and the output occupies contiguous pages. The first term locates the range; the second reads the result.

Worked example. Suppose a B⁺-tree has fan-out F = 100, contains N = 10⁹ keys, and the root is cached. The number of non-root levels is approximately log₁₀₀(10⁹) = 4.5, so about five leaf-level decisions may be needed. A binary search tree over the same keys could require roughly 30 pointer decisions, and those decisions may touch unrelated pages. The B⁺-tree gains from both high fan-out and page locality.

B-trees are especially effective for mixed point and range workloads, in-place updates, and systems that need predictable read latency. Their disadvantages include write amplification from page splits, random page writes, and coordination around hot pages.

1.3 Buffering and external sorting

When updates can be delayed, a buffered tree can batch many operations before applying them to lower levels. Batching converts many small random transfers into fewer large sequential transfers. External sorting uses a related principle: sort chunks that fit in memory, write sorted runs, and merge them using sequential scans. If the memory holds M records and the block holds B records, a standard external merge sort has a transfer complexity near

under the assumptions of balanced multiway merging and sufficient buffering. The expression counts the number of full-file passes, measured in blocks; constants depend on merge fan-in and implementation.

2. Log-Structured Merge Trees

2.1 Design principle

An LSM tree separates writes from immediate in-place index modification. New records are first appended to a write-ahead log and inserted into an in-memory sorted structure, often called a memtable. When the memtable reaches a threshold, it is flushed as an immutable sorted-string table (SSTable). Background compaction merges SSTables into larger sorted files.

Figure: An LSM tree converts random updates into sequential flushes and background compactions.

A key lookup checks the mutable memtable and relevant SSTables, usually from newest to oldest. Bloom filters can identify SSTables that definitely do not contain a key, reducing unnecessary reads. An SSTable typically contains sorted key-value entries, an index, checksums, and metadata such as minimum and maximum keys.

2.2 Levels, size ratios, and compaction

In a leveled LSM tree, level L₀ contains newly flushed files and deeper levels contain progressively larger, non-overlapping files. A size ratio T means that the target capacity of one level is approximately T times that of the preceding level. In a tiered policy, several files may accumulate at a level before being merged, reducing immediate write cost but increasing read uncertainty and space usage.

LSM performance is best understood through amplification factors:

• Write amplification: physical bytes written divided by logical user bytes written.
• Read amplification: number of files or structures examined for a lookup.
• Space amplification: physical bytes occupied divided by live logical bytes.

A simplified total-write relation is

where all terms refer to bytes written over a selected interval. The write-amplification factor is

This is an accounting identity, not a universal prediction. Its value depends on compaction policy, level ratio, overwrites, compression, tombstones, and workload. It must not be confused with a formula that applies identically to every implementation.

Compaction improves read performance by merging files, removing obsolete versions, and consolidating key ranges. It consumes I/O bandwidth and CPU, can create latency spikes, and may temporarily require additional disk space. A production design therefore schedules compaction with awareness of foreground latency, available bandwidth, and recovery requirements.

2.3 Deletes, snapshots, and correctness

An LSM tree normally represents deletion using a tombstone. The tombstone must survive until compaction has passed every older version that it supersedes; otherwise an obsolete value could reappear. For snapshots, entries are tagged with sequence numbers or timestamps. A read at snapshot sequence s returns the newest entry whose sequence is at most s, subject to transaction semantics.

The write-ahead log provides durability: after a crash, committed log records can rebuild the memtable before acknowledging service. However, a log alone does not guarantee distributed durability; replicas, durable media, and a defined acknowledgement policy are also required.

2.4 B-tree versus LSM selection

The choice is workload-dependent. Hybrid systems may use B-trees for metadata and LSM trees for high-volume values.

3. Concurrent Data Structures

3.1 Correctness before speed

Concurrency introduces interleavings. A data structure is correct only if every permitted interleaving preserves its abstract data-type behavior. A linearizable operation appears to take effect at one instant between invocation and response. Linearizability is compositional and closely matches programmer intuition, but it may require synchronization and can reduce scalability.

Sequential consistency requires that operations appear in one order consistent with each thread’s program order, but does not necessarily preserve real-time order between threads. Serializability is a transaction-level property: a concurrent execution has the same effect as some serial execution. Snapshot isolation allows transactions to read a consistent snapshot and generally prevents many write-write conflicts, but it does not eliminate all anomalies, such as certain write-skew patterns.

These are distinct properties. A replicated map might provide linearizable single-key operations while offering only eventual convergence for some multi-key views.

3.2 Blocking and optimistic techniques

A mutex provides mutual exclusion: only one thread enters a critical section at a time. Reader-writer locks allow concurrent readers but may delay writers or readers depending on policy. Fine-grained locking assigns locks to buckets, nodes, or segments rather than to the whole structure. Lock striping is common in concurrent hash maps because unrelated buckets can proceed independently.

Optimistic concurrency reads without holding a long-duration lock, validates that relevant state has not changed, and retries if validation fails. It can perform well when conflicts are rare, but repeated retries may be costly under contention. Version counters, sequence locks, and transactional memory are examples of optimistic mechanisms.

3.3 Atomic primitives and lock-free progress

Compare-and-swap (CAS) has the conceptual form:

It atomically replaces the value at address with replacement only if the current value equals expected. A successful CAS is often used as the linearization point of a lock-free operation.

Progress guarantees are important:

• Obstruction-free: a thread completes if it eventually runs alone.
• Lock-free: some thread completes after a finite number of steps, even if others are delayed.
• Wait-free: every thread completes within a bounded number of its own steps.

Lock-free does not mean starvation-free. One thread may repeatedly lose CAS races while other threads make progress.

A classic lock-free stack uses an immutable node containing a value and a next pointer. The push operation reads the head, sets the new node’s next pointer to that head, and CASes the head from the old value to the new node. Pop reads the head and its successor, then CASes the head to the successor. The algorithm requires safe memory reclamation; otherwise a removed node may be freed and reused while another thread still holds a pointer.

3.4 The ABA problem and reclamation

The ABA problem occurs when a thread reads pointer value A, is delayed, and later observes A again after another thread changed A to B and back to A. The pointer comparison succeeds even though the intervening history matters. Tagged pointers, version counters, hazard pointers, epoch-based reclamation, and garbage collection can address this issue, each with costs and assumptions.

Hazard pointers let a thread publish the nodes it may dereference; retired nodes are reclaimed only when no hazard pointer protects them. Epoch-based reclamation delays freeing until all participating threads have advanced beyond the relevant epoch. Garbage-collected languages remove explicit deallocation hazards but do not automatically solve logical ABA, contention, or memory retention.

4. Concurrent Maps

A concurrent map supports operations such as get, put, remove, and conditional update while multiple threads operate simultaneously. A practical design usually combines a hash function, buckets or segments, synchronization, resizing, and a specified visibility contract.

4.1 Sharded and striped maps

Let S be the number of shards and let a key hash to shard h(k) mod S. Each shard may have its own lock and local table. If requests are independently distributed and no key is disproportionately hot, the probability that two randomly selected operations target the same shard is approximately 1/S. This estimate assumes uniform hashing and independent selection; real workloads often violate both assumptions.

Sharding reduces contention but creates trade-offs. Resizing may require shard-level migration, global coordination, or an indirection layer. Operations over multiple keys may need a stable lock order to avoid deadlock. Hot keys remain hot even with many shards and may require replication, caching, or specialized aggregation.

4.2 Linearizable compound operations

A sequence such as “read the current value, increment it, and write it back” is not atomic if implemented as separate get and put calls. A concurrent map should expose an atomic increment, compare-and-update, or transaction-like operation when the invariant requires it. Otherwise, lost updates can occur:

1. Thread A reads 10.
2. Thread B reads 10.
3. A writes 11.
4. B writes 11.

The final value is 11 rather than the intended 12. CAS loops or bucket locks can implement an atomic update, but the API must state whether the operation is linearizable and what happens during retries or failures.

5. Distributed Indexes

5.1 Partitioning and placement

A distributed index divides a key space among nodes. Range partitioning assigns contiguous key intervals and supports efficient range queries, but a monotonically increasing key can overload the final range. Hash partitioning spreads point lookups more evenly but makes global range scans expensive. Consistent hashing reduces remapping when nodes join or leave, though virtual nodes, hot partitions, and replica placement still require careful management.

A distributed query may contact one node for a point lookup or many nodes for a range query. If p independent partitions must respond and each has success probability r, the probability that all respond is

This formula assumes independence, which is often unrealistic because racks, networks, and power domains can fail together. It nevertheless illustrates why fan-out harms availability and latency.

5.2 Replication and quorum

For a replication factor N, a system may require W acknowledgements for a write and R replicas for a read. A common overlap condition is

which guarantees that the read and write replica sets intersect if selections are from the same replica group. This condition alone does not guarantee linearizability: replica freshness, conflict resolution, leader behavior, clock assumptions, and failure handling also matter.

Leader-based replication routes writes through a primary and orders them before shipping to followers. It simplifies ordering but can make the leader a bottleneck. Leaderless quorum systems can improve availability but require version vectors, timestamps, read repair, anti-entropy, or another conflict-resolution scheme. Multi-leader replication supports local writes but creates conflict-management complexity.

5.3 Consistency and fault tolerance

A distributed index must specify its behavior during partitions. Strong consistency may reject or delay operations when a quorum is unavailable. Eventual consistency may accept writes locally and converge later. Causal consistency preserves cause-and-effect order without imposing one total order on unrelated operations.

Fault tolerance has several layers:

• Durability: acknowledged data survives specified failures.
• Availability: requests receive responses under specified failures.
• Recoverability: a failed node can reconstruct state.
• Operational correctness: repair does not violate ordering or visibility guarantees.

Write-ahead logs, immutable SSTables, checksums, snapshots, replica repair, and membership protocols support these goals. A checksum detects corruption but does not repair it; a replica can repair only if it contains a trusted version; and a snapshot is useful only when its consistency point is defined.

5.4 Distributed secondary indexes

A secondary index maps an attribute to primary-record locations. If the index and primary data are partitioned differently, one update may require a distributed transaction. Alternatives include denormalized index records, asynchronous index maintenance, co-partitioning, or accepting temporary inconsistency.

For AI systems, examples include indexes over tenant, timestamp, embedding identifier, model version, and feature freshness. Vector indexes introduce additional challenges: approximate nearest-neighbor structures may be partitioned by vector space, replicated for latency, and rebuilt when embeddings or distance metrics change. Approximation quality, freshness, and distributed recall must be measured together rather than treated as independent properties.

6. Integrated Design Method

A disciplined design process is more reliable than choosing a fashionable structure.

Step 1: Characterize operations. Measure point reads, range reads, inserts, updates, deletes, scans, and multi-key transactions. Record key distribution, item size, burstiness, and read/write ratio.

Step 2: Identify the bottleneck resource. Is the system constrained by random I/O, sequential bandwidth, CPU hashing, network fan-out, lock contention, or compaction?

Step 3: Define correctness. State whether operations require linearizability, serializability, snapshot isolation, causal ordering, or eventual convergence. Define acknowledged durability and acceptable stale-read intervals.

Step 4: Select physical organization. Choose B⁺-trees for predictable indexed access and ranges, LSM trees for write-heavy ingestion, or a hybrid where different datasets have different behavior.

Step 5: Select concurrency control. Use coarse locks for simplicity when contention is low, striping or fine-grained locks for independent regions, and lock-free methods only when their complexity and reclamation costs are justified.

Step 6: Select distribution and recovery. Choose partitioning, replication factor, quorum policy, placement domains, logging, snapshots, and repair protocols. Test correlated failures rather than only independent node failures.

Step 7: Benchmark realistic tails. Average latency can hide compaction pauses, retries, garbage-collection stalls, and network partitions. Measure p95 and p99 latency, throughput, amplification, recovery time, stale-read rate, and hotspot behavior.

7. Illustrative Case: A Multi-Tenant Feature-Serving Platform

Background

Consider an illustrative platform serving online ML features for 50,000 tenants. Training pipelines append feature versions continuously, while prediction services issue point lookups by (tenant, entity, feature). Some users also request time-windowed historical ranges. Prediction traffic is latency-sensitive, whereas ingestion is high-volume and bursty.

Problem

A single relational B⁺-tree experiences random update pressure and page contention. A single global lock on a cache-backed map produces unacceptable tail latency. During a node failure, recovery replays updates slowly, and stale secondary indexes occasionally return features from an obsolete model version.

Analysis

The workload is write-heavy during feature ingestion but read-sensitive during prediction. Tenant isolation is important because one large tenant must not consume all compaction or cache resources. Point reads dominate online serving, while range reads are mainly offline or administrative. The system therefore needs partition isolation, durable ordered writes, bounded read amplification, and explicit version visibility.

Approach and solution

1. Partitioning: Hash-partition (tenant, entity) across storage groups, with virtual partitions that can be moved independently. This spreads point traffic while preserving tenant-level routing metadata.
2. Storage: Use an LSM engine for append-heavy feature versions. Keep a small B⁺-tree or in-memory directory for partition metadata and model-version manifests.
3. Concurrency: Use per-partition striped locks for mutable memtables and atomic compare-and-update for feature-version publication. Avoid a global lock.
4. Reads: Use Bloom filters and block caches to reduce SSTable probes. A read specifies a model-version fence, so entries newer than the permitted version are not returned accidentally.
5. Durability: Append to a local log, replicate to a second failure domain, and acknowledge according to a documented quorum policy. Periodic snapshots shorten recovery time.
6. Compaction: Schedule per-partition compaction with bandwidth limits. Detect tenants whose write rate creates disproportionate compaction debt.
7. Repair: Use checksums, replica comparison, and throttled anti-entropy. Record whether a response came from a current or stale replica.

Outcome

The design trades some write amplification for sequential ingestion and isolates hot tenants. Point-read latency becomes more predictable because filters, caches, and bounded level counts reduce unnecessary I/O. The version fence prevents a logically inconsistent mixture of feature versions. The system remains operationally complex: compaction, replica repair, and partition movement must be monitored and tested.

Learning points

The case illustrates that a data structure is part of a larger contract. LSM organization solves one bottleneck but introduces compaction management. Sharding reduces contention but does not remove hot keys. Replication improves fault tolerance but requires a precise consistency policy. Correctness metadata, such as version fences, can be as important as the index itself.

8. Challenges, Governance, and Contemporary Directions

8.1 Limitations and failure modes

External-memory analyses may underestimate latency variance and parallelism. B-tree performance depends on cache residency and fill factor. LSM performance depends on compaction scheduling and tombstone retention. Lock-free code is difficult to verify and may consume substantial memory through delayed reclamation. Distributed indexes suffer from correlated failures, network partitions, clock uncertainty, and operational misconfiguration.

A benchmark that reports only throughput is inadequate. It should report workload distribution, item sizes, cache state, compaction state, concurrency level, failure injections, and percentile latency. Reproducibility requires recording versions, hardware, configuration, and data-generation methods.

8.2 Governance and responsible operation

Indexes often expose sensitive attributes and can make personal data easy to retrieve. Access control must apply to both primary data and secondary indexes; otherwise the index can become a side channel. Encryption in transit and at rest, tenant isolation, retention limits, audit logs, and deletion verification are governance requirements, not optional optimizations.

For ML systems, feature stores and embedding indexes can encode personal or protected information. Approximate similarity search may reveal membership or sensitive associations. Data lineage should identify source, transformation, model version, and retention status. Deletion requests must propagate through logs, replicas, caches, snapshots, and compacted files according to applicable policy.

8.3 Contemporary developments

Modern systems increasingly combine persistent memory, NVMe devices, programmable storage, disaggregated storage, and serverless or cloud-native execution. Learned indexes use a model to predict key positions, potentially reducing index size, but they require bounded error handling, distribution-shift monitoring, and a fallback search structure. GPU and SIMD acceleration can speed filtering and compaction, while hardware transactional memory may simplify some short critical sections.

These developments do not eliminate fundamental questions. Designers must still quantify transfer cost, contention, consistency, failure domains, and recovery. A learned index that performs well on a stationary key distribution may degrade after a tenant migration; a fast remote store may still fail under correlated network congestion; and a lock-free algorithm may be slower than a simple lock under low contention.

Best-Practice Checklist

• Model pages, cache lines, network messages, and failure domains explicitly.
• Keep node and record layouts aligned with physical block sizes.
• Measure amplification rather than inferring it from a name or paper.
• Define linearization points and memory-reclamation rules for non-blocking code.
• Prevent deadlock through a documented lock order or avoid nested locks.
• Treat hot keys, hot partitions, and skew as first-class test cases.
• State acknowledgement, freshness, and recovery guarantees in operational terms.
• Use checksums, versioning, snapshots, and repair procedures together.
• Test crashes during flush, compaction, replication, and partition movement.
• Protect indexes with the same privacy and access-control policies as base data.

Chapter Summary

External-memory structures optimize transfers rather than abstract pointer operations. B⁺-trees exploit high fan-out, page locality, and linked leaves to support predictable point and range access. LSM trees turn random updates into log and sequential writes, but incur read, write, and space amplification through multiple levels and compaction.

Concurrent structures require explicit correctness and progress definitions. Locks are often appropriate and can be scaled through sharding or striping. Optimistic and lock-free methods use validation and atomic primitives such as CAS, but they demand careful treatment of ABA and memory reclamation. A concurrent map must make compound operations atomic when application invariants require it.

Distributed indexes add partitioning, replication, quorum, network delay, correlated failure, and repair. The condition R + W > N can guarantee replica-set overlap under stated assumptions, but it does not alone establish linearizability. Sound design begins with workload and consistency requirements, then selects physical organization, synchronization, placement, and recovery mechanisms. AI and ML systems make these issues especially visible because they combine high ingestion rates, latency-sensitive serving, large historical datasets, and sensitive data.

Key Terms

External-memory model: Model in which data moves between fast memory and slower storage in blocks.

Block transfer or I/O: Movement of one storage block between memory levels.

B-tree: Balanced multiway search tree designed to reduce block transfers.

B⁺-tree: B-tree variant with records in leaves and linked leaves for range scans.

Fan-out: Number of child pointers or entries supported by an internal node.

LSM tree: Log-structured merge tree that buffers writes and merges sorted immutable files.

Memtable: In-memory mutable sorted structure in an LSM implementation.

SSTable: Immutable sorted-string table written by an LSM flush or compaction.

Compaction: Merging sorted files and removing obsolete versions or tombstones.

Write amplification: Physical bytes written divided by logical user bytes written.

Read amplification: Amount of physical lookup work relative to one logical read.

Linearizability: Semantics in which each operation appears instantaneous between invocation and response.

Lock-free: Progress property in which some operation completes despite thread delays.

CAS: Atomic compare-and-swap primitive.

ABA problem: Erroneous CAS success after a value changes away from and back to its original value.

Memory reclamation: Safe recovery of storage no longer reachable by concurrent threads.

Sharding: Dividing a data structure into independently managed regions.

Quorum: Required number of replicas participating in a read or write.

Anti-entropy: Background process that compares and repairs divergent replicas.

Hotspot: Key, partition, node, or resource receiving disproportionate traffic.

Review Questions

Short Answer Questions

1. Why does a B⁺-tree generally require fewer external-memory transfers than a binary search tree for the same number of keys?
2. Define write amplification in an LSM tree and identify two factors that can increase it.
3. Distinguish linearizability from sequential consistency.
4. What is the ABA problem, and name one technique that can mitigate it.
5. Why does the condition R + W > N imply replica-set overlap under its stated assumptions?

Long Answer Questions

1. Explain the architecture of an LSM tree from client write to memtable flush and compaction. Discuss its effects on read, write, and space amplification.
2. Compare B⁺-trees and LSM trees for a system containing point reads, range scans, high-rate updates, and deletes.
3. Describe blocking, optimistic, and lock-free concurrency control. Include progress guarantees and memory-reclamation concerns.
4. Analyze range partitioning, hash partitioning, and consistent hashing for a distributed index with skewed AI feature traffic.
5. Develop a failure and recovery design for a replicated distributed index, including logs, snapshots, checksums, repair, and consistency guarantees.

Analytical / Application Questions

1. A system stores N = 10⁸ records in blocks of B = 100 records. Estimate the number of block transfers for a sequential scan using Θ(N/B), and explain why random access may be much more expensive.
2. A concurrent map uses 64 uniformly selected shards. Under the simplifying assumption of independent shard selection, estimate the probability that two randomly selected operations target the same shard. State why real workloads may differ.
3. Design a storage architecture for an online feature-serving platform with append-heavy writes, point reads, historical range queries, tenant isolation, and machine failures. Justify choices of tree organization, partitioning, synchronization, replication, and repair.

Multiple Choice Questions with Answers

Question 1

In the external-memory model, what is the approximate transfer complexity of scanning N records stored B records per block?

A. Θ(N)

B. Θ(log_B N)

C. Θ(N/B)

D. Θ(B/N)

Correct Answer: C. Θ(N/B)

Question 2

Which B⁺-tree feature most directly supports efficient range scans?

A. Records are stored only in the root

B. Linked leaf pages in sorted-key order

C. Randomized internal-node placement

D. A separate lock for every comparison

Correct Answer: B. Linked leaf pages in sorted-key order

Question 3

What is the primary purpose of compaction in an LSM tree?

A. Convert sorted files into unsorted files

B. Merge files and remove obsolete versions when safe

C. Eliminate the write-ahead log immediately

D. Guarantee linearizability across all replicas

Correct Answer: B. Merge files and remove obsolete versions when safe

Question 4

Which statement about lock-free progress is correct?

A. Every thread completes within a fixed bound

B. No thread can ever be delayed

C. Some thread completes despite other threads being delayed

D. All operations are protected by one global mutex

Correct Answer: C. Some thread completes despite other threads being delayed

Question 5

Which issue occurs when a pointer changes from A to B and back to A before a delayed CAS?

A. Dirty-read problem

B. ABA problem

C. Compaction debt

D. Range-partition problem

Correct Answer: B. ABA problem

Question 6

A concurrent map exposes separate get and put operations. Why can incrementing a value with those two calls lose updates?

A. Hash functions cannot handle integers

B. The read-modify-write sequence is not atomic

C. B⁺-trees cannot store numeric values

D. Replication always reverses increments

Correct Answer: B. The read-modify-write sequence is not atomic

Question 7

Which partitioning strategy generally spreads point lookups evenly but makes global range scans more difficult?

A. Hash partitioning

B. Range partitioning

C. Leaf linking

D. Sequential buffering

Correct Answer: A. Hash partitioning

Question 8

For replication factor N = 3, which read/write quorum pair satisfies R + W > N?

A. R = 1, W = 1

B. R = 1, W = 2

C. R = 0, W = 2

D. R = 1, W = 0

Correct Answer: B. R = 1, W = 2

Question 9

Which statement about R + W > N is accurate?

A. It alone guarantees linearizability

B. It guarantees replica-set overlap under the stated replica-selection assumptions

C. It eliminates the need for conflict resolution

D. It means every read contacts every replica

Correct Answer: B. It guarantees replica-set overlap under the stated replica-selection assumptions

Question 10

A system has 64 uniformly selected shards. What is the probability that two independent operations select the same shard?

A. 1/2

B. 1/64

C. 2/64

D. 64/2

Correct Answer: B. 1/64