Abstract
When verifying computer systems we sometimes want to study their asymptotic behaviors, i.e., how they behave in the long run. In such cases, we need real analysis, the area of mathematics that deals with limits and the foundations of calculus. In a prior work, we used real analysis in ACL2s to study the asymptotic behavior of the RTO computation, commonly used in congestion control algorithms across the Internet. One key component in our RTO computation analysis was proving in ACL2s that for all alpha in [0, 1), the limit as n approaches infinity of alpha raised to n is zero. Whereas the most obvious proof strategy involves the logarithm, whose codomain includes irrationals, by default ACL2 only supports rationals, which forced us to take a non-standard approach. In this paper, we explore different approaches to proving the above result in ACL2(r) and ACL2s, from the perspective of a relatively new user to each. We also contextualize the theorem by showing how it allowed us to prove important asymptotic properties of the RTO computation. Finally, we discuss tradeoffs between the various proof strategies and directions for future research.
Introduction: The Challenge of Asymptotic Analysis
In formal verification, understanding the long-term or "asymptotic" behavior of a system is crucial for ensuring stability. This requires real analysis—the study of limits and calculus. However, a technical rift exists within the ACL2 ecosystem. Standard ACL2s, optimized for computer system verification, operates on rational numbers and cannot represent irrationals or logarithms. Conversely, ACL2(r) supports real numbers but is theoretically incompatible with standard ACL2s models. This paper explores how to bridge this gap by proving fundamental limits within a rational-only framework.
Case Study: TCP Retransmission TimeOut (RTO)
The authors use the TCP Retransmission TimeOut (RTO) calculation (RFC 6298) as a practical case study. To prove the protocol's stability, one must demonstrate that the RTO remains bounded over time. A core component of this proof involves showing that for any $\alpha \in [0, 1)$, the limit of $\alpha^n$ as $n \to \infty$ is 0.
Comparing Proof Strategies
The paper evaluates three distinct approaches to proving $\lim_{n \to \infty} \alpha^n = 0$:
- The "Real" Proof (ACL2(r)): This follows the standard textbook derivation using logarithms. While intuitive, it relies on irrational numbers, making it non-portable to standard ACL2s.
- The Ceiling Proof (ACL2s): A manual $\epsilon-\delta$ proof using the "ceiling" function to find a threshold $n$. This approach proved arduous due to the lack of pre-existing library support for ceiling function properties.
- The Binomial Proof (ACL2s): A semi-automatic approach using the binomial theorem to "squeeze" the value. The authors creatively leveraged ACL2s’s automated termination analysis to find the necessary $\delta$ threshold.
Key Results and Insights
The semi-automatic Binomial proof emerged as the most efficient method for ACL2s users, being shorter than the "natural" real-number proof and significantly faster than the manual rational proof.
| Proof Strategy | Lines of Code | Functions | Certification Time |
|---|---|---|---|
| Real (ACL2(r)) | 161 | 1 | 0.58s |
| Ceiling (Manual) | 408 | 3 | 64.17s |
| Binomial (Semi-Auto) | 122 | 2 | 3.84s |
A major insight was the "Portability Paradox": although rationals are dense in reals, the logical frameworks for the two are often mutually exclusive. The authors also demonstrated that "hacking" termination analysis can effectively automate the discovery of limit thresholds.
Conclusion and Future Work
The study highlights the need for better "bridges" between real and rational logic systems in formal methods. Future work includes developing a formal mechanism to translate proofs from ACL2(r) to ACL2s and extending analysis to dynamic network conditions using Lipschitz continuity.
Summary updated