This content originally appeared on HackerNoon and was authored by EScholar: Electronic Academic Papers for Scholars
Table of Links
3 The Deterministic Case
In this section, we focus on the discount model with miner ratio α ̸= 0 and some discount rate λ. Missing proofs are given in Appendix A.
3.1 Deterministic Upper Bound
\
\
\
\
\
\ By combining Eqs. (5) and (6), the proof is concluded:
\
\
3.2 The Immediacy-Biased Class Of Allocation Function
We proceed by introducing the immediacy-biased ratio class of allocation functions, and identify a regime of discount rates λ which we call the “semi-myopic” regime where it achieves the optimal deterministic competitive ratio. Given a parameter ℓ ∈ R, we denote the corresponding instance of this class as ρℓ and define it in the following manner
\ Definition 3.3 (The ℓ-immediacy-biased ratio allocation function ρℓ). For a set S, let
\
\
\ \ Before providing the lower and upper bound analysis, we comment on how our algorithm stands in comparison with another algorithm, MG [LSS05]. While the ℓ-immediacy-biased considers only the highest T T L = 1 transaction as a possible candidate to be scheduled instead of the highest-fee transaction, MG considers any earliest-deadline transaction. I.e., the algorithms differ in their behavior when no T T L = 1 transactions are available. However, in terms of competitive analysis, ℓ-immediacy-biased dominates ℓ-MG. That is because at any case that the ℓ-immediacy-biased allocation chooses a T T L = 1 transaction, ℓ-MG would do the same. But any case that ℓ-immediacy-biased allocation chooses the highest-fee transaction; we can force ℓ-MG to do the same by adding a (1, ϵ) with small enough ϵ to the adversary’s schedule at that step. Therefore, we can force ℓ-MG to make the same choices as ℓ-immediacy-biased allocation, without changing the optimal allocation performance.
\ We bound the allocation function’s competitive ratio from below in Lemma 3.4.
\
\
\
\
\
\ \
4 The Randomized Case
Next, Theorem 4.1 obtains an upper bound on the competitive ratio of any allocation function.
4.1 Randomized Upper Bound
Theorem 4.1. Given α ̸= 0, for any (possibly randomized) allocation function ALG:
\
\
\ \ Similarly to the deterministic upper bound, the proof uses a recursive construction of adversaries where the transaction fees grow exponentially. The main technical choice is how to decide the base of the exponent. We guess it by the following equation:
\
\
\
4.2 The RMIXλ Randomized Allocation Function
Next, we show that the best-known randomized allocation function known for the undiscounted case [CCFJST06], extends to the more general discount model.
\
\
\
\
\
![Figure 5: Bounds for the competitive ratios of Section 3 and Section 4’s various allocation functions, for miners with a mining ratio α ̸= 0 and discount rates λ ∈ [0, 1].](https://cdn.hackernoon.com/images/fWZa4tUiBGemnqQfBGgCPf9594N2-xqb324x.png)
\
\
\
\ \ Notably, in the semi-myopic range that we identify in Section 3.2, our simple deterministic allocation achieves very similar performance to the above randomized allocation function.
\ Our competitive ratio results are summarized in Fig. 5.
\
:::info Authors:
(1) Yotam Gafni, Weizmann Institute (yotam.gafni@gmail.com);
(2) Aviv Yaish, The Hebrew University, Jerusalem (aviv.yaish@mail.huji.ac.il).
:::
:::info This paper is available on arxiv under CC BY 4.0 DEED license.
:::
\
This content originally appeared on HackerNoon and was authored by EScholar: Electronic Academic Papers for Scholars
EScholar: Electronic Academic Papers for Scholars | Sciencx (2025-10-13T19:54:21+00:00) Why “Immediacy Bias” Might Be the Secret to Faster, Smarter Blockchain Transactions. Retrieved from https://www.scien.cx/2025/10/13/why-immediacy-bias-might-be-the-secret-to-faster-smarter-blockchain-transactions/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.