Lantern: Finding Committable Transactions via Back-Propagation on DAGs

summary

The gist

Lantern presents a deterministic concurrency control protocol tailored for high-performance transaction processing systems operating without prior knowledge of transaction read-write sets It achieves…

In short

Lantern is a deterministic concurrency control protocol for high-performance transaction systems that does not know read-write sets beforehand. It models dependencies as a directed graph and uses a novel Back-Propagation mechanism to find more transactions that can be safely committed. This approach ensures network-wide determinism while achieving up to 4.2x throughput speedup over Aria.

Key concepts

Dependency Graph Construction
Transactions are mapped onto a directed graph where an edge exists if one transaction conflicts with a preceding one. This structure is guaranteed to be acyclic, ensuring that the resulting graph is consistent and deterministic across all network nodes.
Back-Propagation Mechanism
This iterative process systematically searches for additional transactions that can be committed by propagating status markings from sink to source vertices in the dependency graph. It salvages more committable transactions while strictly maintaining network-wide determinism.
Conflict-Free Batch Selection (CFBS)
CFBS is a mechanism designed for read-modify-write intensive workloads. It ensures that no two transactions selected within the same batch will operate on overlapping accounts, proactively preventing conflicts during selection instead of waiting for them to occur.

Terminology used across episodes

This episode discusses

The paper

Lantern: Finding Committable Transactions via Back-Propagation on DAGs · Read on arXiv

Tsinghua University · Beijing Academy of Blockchain and Edge Computing

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Lantern: Finding Committable Transactions via Back-Propagation on DAGs".

Jane: Here's the gist of the paper. Lantern presents a deterministic concurrency control protocol tailored for high-performance transaction processing systems operating without prior knowledge of transaction read-write sets It achieves up to a 4.2x throughput speedup over Aria and improves ChainMaker’s execution-layer throughput by at least 2.2x Protocol Core Concepts Lantern is a deterministic concurrency control protocol tailored for high-performance transaction processing systems operating without prior knowledge of transaction read-write sets The key insight of Lantern is that all zero-out-degree transaction vertices in the local dependency graph can be safely committed in ascending order using an overwrite-permissive strategy It further introduces a novel Back-Propagation mechanism that iteratively propagates dependency states from sink to source vertices to identify additional committable transactions Additionally, Lantern integrates a Conflict-Free Batch Selection (CFBS) mechanism for read-modify-write intensive scenarios Dependency Graph Construction Lantern models transaction dependencies using a directed graph where a directed edge (TX i → TX j) is added if and only if TX i has a RAW conflict with a preceding transaction TX j (j < i) This construction guarantees that the generated dependency graph is inherently acyclic because the start vertex always has a larger index than the end vertex (i > j) The constructed DAG strictly guarantees determinism and consistency across all network nodes Commitment Strategy For all committable transactions, Lantern sorts them in ascending order of their indices and applies their write sets to the world state, preserving only the value written by the transaction with the highest index This commit rule is specified as Rule 2 (Commit) The commitment phase strictly guarantees network-wide determinism across iterative rounds because all nodes construct an identical DAG and deterministically derive the exact same set of zero-out-degree transactions for commitment Back-Propagation Mechanism The Back-Propagation mechanism systematically salvages additional committable transactions while strictly preserving network-wide determinism It operates according to four deterministic rules: Initialization (Red), Conflict Propagation (Gray), Salvage Propagation (Red), and Termination This iterative marking process increases the number of committable transactions while strictly preserving determinism across all participating nodes Performance Evaluation Extensive evaluations on YCSB and SmallBank benchmarks demonstrate that Lantern achieves up to a 4.2x throughput speedup over Aria Furthermore, Lantern establishes its serializability through a constructive proof, enabling empirical validation of both its serializability and determinism Under severe data contention (skew = 0.9), Lantern consistently outperforms Aria by 4.2x The Conflict-Free Batch Selection (CFBS) mechanism boosts throughput by up to 1.84x under high contention Scalability and Trade-offs Lantern demonstrates superior scalability, consistently outperforming Lantern-NoBP across all core configurations under severe contention When CFBS is enabled, the performance curves of Lantern and Lantern-NoBP virtually overlap For severe contention (skew = 0.9), a smaller batch size bounds the contention domain per execution round, maintaining a higher commit ratio and ensuring stable throughput The impact of batch size Bsize shows that for severe contention, a smaller batch size maintains higher throughput because large batches lead to low transaction commit ratios In this paper, Lantern presents a deterministic concurrency control protocol designed for high-performance transaction processing systems operating without prior read-write knowledge By combining an overwrite-permissive strategy on DAGs with a deterministic Back-Propagation mechanism, Lantern significantly expands the set of committable transactions per batch while maintaining cross-node state consistency Additionally, its Conflict-Free Batch Selection (CFBS) mechanism effectively eliminates contention under RMW-intensive scenarios The results demonstrate that Lantern achieves up to a 4.2x throughput speedup over Aria and improves ChainMaker’s execution-layer throughput by at least 2.2x References

1: J.

Tom: Kwon, “Tendermint: Consensus without mining,” https://tendermint.com/static/docs/tendermint.pdf, 2014

2: M.

Jane: Yin, D.

Tom: Malkhi, M.

Title and authors: Tom: So, we're talking about this paper called "Lantern: Finding Committable Transactions via Back-Propagation on DAGs." It sounds like they're tackling the problem of getting multiple nodes to run transactions at the same time without having to know all the read and write sets beforehand.

Jane: That makes sense because in blockchain systems, you can't really know what data a transaction will touch until it runs, which is why prior knowledge is often impossible for these protocols <ref:2609.03315#pg2>. What do you think the core idea of Lantern actually is?

Tom: The key insight they have seems to be focusing only on those transactions that have zero out degree in the local dependency graph and committing them in order, using an overwrite permissive strategy <ref:2609.03315#pg1>. It's about finding a safe subset of transactions for commitment within a batch without needing that big prior knowledge we discussed.

Lu: What's really interesting is how they build that dependency graph; they draw an edge between transaction i and preceding transaction j if there’s a raw conflict, which guarantees the resulting directed graph is acyclic because the start index is always larger than the end index <ref:2609.03315#pg2>. That structure ensures determinism across all network nodes.

Meng: But then they introduce this novel Back-Propagation mechanism, which seems to be an iterative process that propagates dependency states from sink to source vertices to find even more committable transactions <ref:2609.03315#pg1>. From a deployment standpoint, how does that iterative propagation actually translate into something tangible when we’re running at scale?

Jane: Well, the summary says this mechanism systematically salvages additional committable transactions while strictly preserving network-wide determinism by operating through four deterministic rules: Initialization Red, Conflict Propagation Gray, Salvage Propagation Red, and Termination <ref:2609.03315#pg1>. It’s a structured way to keep expanding that set of safe transactions without losing consistency across the whole system.

Tom: And they also propose something called Conflict-Free Batch Selection or CFBS for those read-modify-write intensive scenarios <ref:2609.03315#pg1>. That sounds like they are trying to solve a specific type of contention issue proactively instead of just reacting when things go wrong.

Lu: CFBS is designed specifically for read-modify-write intensive scenarios, so it ensures that no two transactions selected within the same batch operate on overlapping accounts, which avoids conflicts during the selection phase itself <ref:2609.03315#pg1>. That proactive avoidance is a big deal in high contention environments.

Meng: If we're talking about what this means for production, we need to know how this affects the operational cost and stability of our systems <ref:2609.03315#pg1>. Does this complexity translate into a significant overhead when we run it on real traffic?

Title and authors: Jane: The evaluation on YCSB and SmallBank benchmarks shows that Lantern outperforms Aria by up to four point two times in throughput, which is a huge number <ref:2609.03315#pg3>. Plus, they also boost ChainMaker’s execution layer throughput by at least two point two times <ref:2609.03315#pg3>. That’s a lot of speedup for transaction processing systems that don't have prior knowledge of read and write sets.

Tom: A four point two times speedup over Aria is substantial, especially under severe data contention where the skew is zero point nine, where Lantern consistently outperforms Aria by four point two times <ref:2609.03315#pg3>. That suggests it handles the hard cases much better than the baseline protocol we were comparing against.

Lu: And they established serializability through a constructive proof, which allows for empirical validation of both its serializability and determinism <ref:2609.03315#pg3>. The paper shows that the read and write sets of each transaction perfectly match those from concurrent execution and the final state remains identical between the serial and concurrent executions <ref:2609.03315#pg2>.

Meng: I worry about the batch size choice, though. The paper mentions that for severe contention, a smaller batch size actually maintains higher throughput because it bounds the contention domain per execution round

Paper text implies this under 'Impact of Batch Size Bsize': . If we set a big batch size, things get messy quickly.

Jane: That makes sense; the paper notes that for low to moderate contention, larger batch sizes are better because they expose more intra-batch parallelism Paper text implies this. But when the contention is severe, you need smaller batches to keep the commit ratio high and throughput stable Paper text implies this. It’s a trade-off based on how much conflict you expect.

Tom: The latency breakdown shows that under low contention, execution time dominates at about forty-eight point nine milliseconds, but under high contention with a skew of zero point nine, the execution phase latency jumps up to one hundred fifty point eight milliseconds Paper text implies this. That's a significant hit when conflicts are bad.

Lu: And they also show how the batch size Bsize impacts performance across different contention levels; for severe contention, a smaller batch size bounds the contention domain per execution round, maintaining a higher commit ratio and ensuring stable throughput Paper text implies this. This shows the mechanism is tuned to handle those specific stress points.

Meng: So, if we take what they did with CFBS—the Conflict-Free Batch Selection—under high contention, it boosts throughput by up to one point eight four times Paper text implies this. That seems like a very practical win for RMW intensive workloads where conflicts are common.

Title and authors: Jane: It means that even in those difficult RMW scenarios, we can get a boost without sacrificing the deterministic nature of the protocol, which is what matters most for distributed systems <ref:2609.03315#pg1>. It keeps things consistent while pushing performance higher than our old Aria comparison.

Tom: Overall, this paper "Lantern: Finding Committable Transactions via Back-Propagation on DAGs" presents a deterministic concurrency control protocol that doesn't require prior knowledge of read and write sets <ref:2609.03315#pg1>. It combines the overwrite permissive strategy on dependency graphs with that deterministic back-propagation mechanism to expand the set of committable transactions <ref:2609.03315#pg1>.

Lu: The implication here is that we can build systems where nodes execute transactions independently and concurrently without needing coordination between them, as Lantern is an independent protocol integrated into systems like ChainMaker <ref:2609.03315#pg3>.

Meng: For deployment, what this means for us at the startup level is that if we can use this structure to handle RMW workloads with CFBS enabled, we might be able to run our models with higher effective throughput and less risk of state divergence across nodes <ref:2609.03315#pg1>.

Jane: So, to wrap up, Lantern achieves a four point two times throughput speedup over Aria and improves ChainMaker’s execution layer throughput by at least two point two times <ref:2609.03315#pg3>. It’s a deterministic way to handle concurrency when you don't know the read and write sets in advance.

Tom: Yeah, it's a lot of speedup for what it achieves, especially when we look at how it handles severe data contention with that four point two times performance gain over Aria <ref:2609.03315#pg3>. It really shows the power of using deterministic methods to handle uncertainty in transaction execution.

Lu: The constructive proof they used to establish serializability is a strong part of this work, showing that the resulting order is truly correct against concurrent executions <ref:2609.03315#pg2>. That mathematical rigor underpins the entire system.

Meng: I just keep thinking about how difficult it would be to tune the batch size Bsize perfectly across different real-world workloads, but seeing that the paper suggests a smaller batch size is better for high contention environments gives us a clear direction on where we need to focus our implementation efforts <ref:2609.03315#pg1>.

Jane: It’s definitely complex, but it gives us a much clearer picture of how to design protocols that can run concurrently and independently while guaranteeing identical results across the network <ref:2609.03315#pg3>. That's what I think is most important for understanding this paper.

Tom: Exactly, so we’ve looked at "Lantern: Finding Committable Transactions via Back-Propagation on DAGs." It’s a deterministic concurrency control protocol designed to eliminate the need for knowing read and write sets beforehand <ref:2609.03315#pg1>. The results show it can give you up to a four point two times throughput speedup over Aria in tough conditions <ref:2609.03315#pg3>.

The paper's summary: Tom: So, we've talked about how Lantern uses that dependency graph and back-propagation to find transactions that are safe to commit without knowing all their read and write sets up front <ref:2609.03315#pg1>. Now, let's look at what the authors actually claim in this summary.

Jane: Okay, so they're basically saying that by looking only at transactions with zero out degree in that graph and committing them in order using an overwrite permissive strategy, you get a consistent result across all nodes <ref:2609.03315#pg1>. That's the core commitment rule.

Lu: Right, they also introduce this novel Back-Propagation mechanism which systematically salvages more committable transactions by propagating status markings from sink to source vertices, and it keeps the network wide determinism intact <ref:2609.03315#pg1>. That iterative process is what expands the set of safe transactions.

Meng: It sounds like they're trying to be smarter about which transactions get committed in a single batch, not just sticking to the first set they find <ref:2609.03315#pg1>. But what's really interesting for us at Scale is the Conflict-Free Batch Selection mechanism, CFBS, which handles those read-modify-write intensive workloads by making sure no two selected transactions overlap on accounts during selection itself <ref:2609.03315#pg1>.

Tom: That CFBS part sounds like it’s a direct solution for the messy real-world scenarios where you've got a lot of concurrent updates fighting over the same data, and it proactively avoids conflicts instead of just aborting them later <ref:2609.03315#pg1>.

Jane: And they claim this whole setup gives them a four point two times throughput speedup over Aria on severe data contention, and at least two point two times execution layer throughput improvement for ChainMaker <ref:2609.03315#pg3>. That’s a big jump for performance in transaction processing systems without prior knowledge of the data sets.

Lu: And they proved it's correct by showing that the read and write sets of each transaction match what happens during concurrent execution, so the final state is identical between serial and concurrent runs <ref:2609.03315#pg2>. That constructive proof for serializability is a solid piece of evidence.

Meng: I still have my concerns about the batch size Bsize, though. The paper says that under severe contention, you need to use a smaller batch size because it bounds the conflict domain per execution round, keeping the commit ratio high and throughput stable <ref:2609.03315#pg1>. If we set it too big, things get messy fast.

Tom: So what they're telling us is that this protocol is deterministic—it always gives you the same result regardless of how many nodes are running it—and even though it's complex with the back-propagation, the performance metrics against Aria show a real advantage when contention is high, especially when CFBS is turned on <ref:2609.03315#pg3>.

Jane: It really changes how we think about concurrency control without knowing everything in advance. It suggests we can build systems where nodes execute transactions simultaneously and independently while deterministically reaching identical serializable results <ref:2609.03315#pg1>. Next up, let's look at those specific performance numbers on the YCSB and SmallBank benchmarks.

The paper's improvements: Tom: So, we've been talking about how Lantern uses that dependency graph and back-propagation to find transactions that are safe to commit without knowing all their read and write sets up front <ref:2609.03315#pg1>. Now, let's look at the specific improvements the authors suggest for this protocol.

Jane: What's the big idea here? They aren't just adding features; they’re tweaking how it works to be more effective in real systems <ref:2609.03315#pg1>. They focus on making sure that even if you don't know the data beforehand, the system still behaves predictably and correctly across all nodes.

Lu: One key improvement they push is the systematic refinement of the Back-Propagation mechanism itself—they describe a four-step process: Initialization Red, Conflict Propagation Gray, Salvage Propagation Red, and Termination <ref:2609.03315#pg1>. That iterative marking process is what makes it smarter at finding those extra committable transactions.

Meng: So instead of just one pass to find safe stuff, they're adding this systematic refinement layer to keep expanding the set of committable transactions while strictly preserving network wide determinism <ref:2609.03315#pg1>. That sounds like it adds complexity on the execution side, which I always worry about at scale.

Jane: It is complex, but they argue that this structured iterative process is what allows them to salvage additional committable transactions without compromising state consistency across the whole system <ref:2609.03315#pg1>. They are essentially making the system more robust against uncertainty in the transaction sets.

Tom: And then there's the Conflict-Free Batch Selection mechanism, CFBS, which they introduce for those read-modify-write intensive scenarios <ref:2609.03315#pg1>. This is supposed to be a proactive way to handle contention during batch selection by ensuring no two selected transactions overlap on accounts <ref:2609.03315#pg1>.

Lu: CFBS is designed specifically for those RMW intensive workloads, so it avoids conflicts during the selection phase instead of just reacting when things go wrong later <ref:2609.03315#pg1>. It’s a way to manage contention upfront within the batch itself.

Meng: If we can use CFBS to handle those RMW workloads, it could mean our models don't have to constantly abort and re-execute transactions just because two things tried to touch the same account at the same time <ref:2609.03315#pg1>. That would definitely reduce the operational load on our production environment.

Jane: And overall, they're showing that this combination of deterministic graph ordering and intelligent conflict handling is what lets them achieve that significant throughput speedup over Aria <ref:2609.03315#pg3>. It's not just about one trick; it’s a whole system tweak <ref:2609.03315#pg1>.

Tom: So the implication here is that for systems without prior read and write knowledge, we can build protocols that execute transactions concurrently and independently while guaranteeing identical results across the network <ref:2609.03315#pg1>.

Lu: Exactly. It suggests a new way to design concurrency control where you don't need strict serial dependency between the primary node and replica nodes because the protocol itself guarantees the order <ref:2609.03315#pg1>.

Meng: I still have my concerns about the batch size Bsize, though. The paper says that for severe contention, you need to use a smaller batch size because it bounds the conflict domain per execution round, keeping the commit ratio high and throughput stable <ref:2609.03315#pg1>. If we set it too big, things get messy fast.

Jane: That makes sense; for low to moderate contention, larger batch sizes are better because they expose more intra-batch parallelism Paper text implies this. But when the contention is severe, you need smaller batches to keep the commit ratio high and throughput stable Paper text implies this. It’s a trade-off based on how much conflict you expect.

Tom: The latency breakdown shows that under low contention, execution time dominates at about forty eight point nine milliseconds, but under high contention with a skew of zero point nine, the execution phase latency jumps up to one hundred fifty point eight milliseconds Paper text implies this. That's a big hit when conflicts are bad.

Lu: And they also show how the batch size Bsize impacts performance across different contention levels; for severe contention, a smaller batch size bounds the conflict domain per execution round, maintaining a higher commit ratio and ensuring stable throughput Paper text implies this. This shows the mechanism is tuned to handle those specific stress points.

Jane: So to wrap up, Lantern achieves that four point two times speedup over Aria and improves ChainMaker’s execution layer throughput by at least two point two times <ref:2609.03315#pg3>. It’s a deterministic way to handle concurrency when you don't know the read and write sets in advance.

Conclusion: Tom: So we've talked about how Lantern uses that dependency graph and back-propagation to find transactions that are safe to commit without knowing all their read and write sets up front <ref:2609.03315#pg1>. Now, let's look at the specific improvements the authors suggest for this protocol.

Jane: What's the big idea here? They aren't just adding features; they’re tweaking how it works to be more effective in real systems <ref:2609.03315#pg1>. They focus on making sure that even if you don't know the data beforehand, the system still behaves predictably and correctly across all nodes.

Lu: One key improvement they push is the systematic refinement of the Back-Propagation mechanism itself—they describe a four-step process: Initialization Red, Conflict Propagation Gray, Salvage Propagation Red, and Termination <ref:2609.03315#pg1>. That iterative marking process is what makes it smarter at finding those extra committable transactions.

Meng: So instead of just one pass to find safe stuff, they're adding this systematic refinement layer to keep expanding the set of committable transactions while strictly preserving network wide determinism <ref:2609.03315#pg1>. That sounds like it adds complexity on the execution side, which I always worry about at scale.

Jane: It is complex, but they argue that this structured iterative process is what allows them to salvage additional committable transactions without compromising state consistency across the whole system <ref:2609.03315#pg1>. They are essentially making the system more robust against uncertainty in the transaction sets.

Tom: And then there's the Conflict-Free Batch Selection mechanism, CFBS, which they introduce for those read-modify-write intensive scenarios <ref:2609.03315#pg1>. This is supposed to be a proactive way to handle contention during batch selection by ensuring no two selected transactions overlap on accounts <ref:2609.03315#pg1>.

Lu: CFBS is designed specifically for those RMW intensive workloads, so it avoids conflicts during the selection phase instead of just reacting when things go wrong later <ref:2609.03315#pg1>. It’s a way to manage contention upfront within the batch itself.

Meng: If we can use CFBS to handle those RMW workloads, it could mean our models don't have to constantly abort and re-execute transactions just because two things tried to touch the same account at the same time <ref:2609.03315#pg1>. That would definitely reduce the operational load on our production environment.

Wrap-up: Jane: And overall, they're showing that this combination of deterministic graph ordering and intelligent conflict handling is what lets them achieve that significant throughput speedup over Aria <ref:2609.03315#pg3>. It's not just about one trick; it’s a whole system tweak <ref:2609.03315#pg1>.

Tom: So the implication here is that for systems without prior read and write knowledge, we can build protocols that execute transactions concurrently and independently while guaranteeing identical results across the network <ref:2609.03315#pg1>.

Lu: Exactly. It suggests a new way to design concurrency control where you don't need strict serial dependency between the primary node and replica nodes because the protocol itself guarantees the order <ref:2609.03315#pg1>.

Meng: I still have my concerns about the batch size Bsize, though. The paper says that for severe contention, you need to use a smaller batch size because it bounds the conflict domain per execution round, keeping the commit ratio high and throughput stable <ref:2609.03315#pg1>. If we set it too big, things get messy fast.

Jane: That makes sense; for low to moderate contention, larger batch sizes are better because they expose more intra-batch parallelism Paper text implies this. But when the contention is severe, you need smaller batches to keep the commit ratio high and throughput stable Paper text implies this. It’s a trade-off based on how much conflict you expect.

Tom: The latency breakdown shows that under low contention, execution time dominates at about forty eight point nine milliseconds, but under high contention with a skew of zero point nine, the execution phase latency jumps up to one hundred fifty point eight milliseconds Paper text implies this. That's a big hit when conflicts are bad.

Lu: And they also show how the batch size Bsize impacts performance across different contention levels; for severe contention, a smaller batch size bounds the conflict domain per execution round, maintaining a higher commit ratio and ensuring stable throughput Paper text implies this. This shows the mechanism is tuned to handle those specific stress points.

Wrap-up: Jane: So to wrap up, Lantern achieves that four point two times speedup over Aria and improves ChainMaker’s execution layer throughput by at least two point two times <ref:2609.03315#pg3>. It’s a deterministic way to handle concurrency when you don't know the read and write sets in advance.

Tom: Yeah, it's a lot of speedup for what it achieves, especially when we look at how it handles severe data contention with that four point two times performance gain over Aria <ref:2609.03315#pg3>. It really shows the power of using deterministic methods to handle uncertainty in transaction execution.

Lu: The constructive proof they used to establish serializability is a strong piece of evidence, showing that the resulting order is truly correct against concurrent executions <ref:2609.03315#pg2>. That mathematical rigor underpins the entire system.

Meng: I just keep thinking about how difficult it would be to tune the batch size Bsize perfectly across different real-world workloads, but seeing that the paper suggests a smaller batch size is better for high contention environments gives us a clear direction on where we need to focus our implementation efforts <ref:2609.03315#pg1>.

Jane: It’s definitely complex, but it gives us a much clearer picture of how to design protocols that can run concurrently and independently while guaranteeing identical results across the network <ref:2609.03315#pg3>. That's what I think is most important for understanding this paper.

Tom: Exactly, so we’ve looked at Lantern: Finding Committable Transactions via Back-Propagation on DAGs. It’s a deterministic concurrency control protocol designed to eliminate the need for knowing read and write sets beforehand <ref:2609.03315#pg1>. The results show it can give you up to a four point two times throughput speedup over Aria in tough conditions <ref:2609.03315#pg3>.

Lu: And the authors flag that the method's effectiveness really depends on how well you tune those batch sizes for different workloads <ref:2609.03315#pg1>.

Meng: Yeah, so if you're building something with high contention RMW workloads, keep an eye on that batch size tuning; it’s the main lever they identified for performance stability <ref:2609.03315#pg1>.

Jane: We'll be looking at how this deterministic approach compares to the other methods we've discussed later in the show, so stay tuned.

More episodes

← Home