The Proceedings of the ACM on Measurement and Analysis of Computing Systems (POMACS) focuses on the measurement and performance evaluation of computer systems and operates in close collaboration with the ACM Special Interest Group SIGMETRICS. All papers in this issue of POMACS will be presented at the ACM SIGMETRICS 2025 conference on June 9-13, 2025, in Stony Brook, New York, USA.
The papers in this issue were selected during the summer submission round by the 93 members of the ACM SIGMETRICS 2025 program committee via a rigorous review process. Each paper was conditionally accepted (and shepherded), or allowed to be resubmitted to one of the subsequent two SIGMETRICS deadlines, or rejected (with resubmission allowed only after a year).
POMACS is publishing 20 papers out of 110 submissions in this issue, of which 3 had previously received a one-shot revision decision. Submissions typically receive at least three reviews. While most papers were decided in the online discussion phase, borderline cases were extensively discussed during the online program committee meeting. Based on the indicated track(s), roughly 18% of the submissions were in the Theory track, 39% were in the Measurement & Applied Modeling track, 27% were in the Systems track, and 16% were in the Learning track.
Many individuals contributed to the success of this issue of POMACS. We thank the authors, who submitted their best work to SIGMETRICS/POMACS. We would also like to thank the program committee members who provided constructive feedback in their reviews to authors and participated in the online discussions and program committee meeting. Further, we thank the several external reviewers who provided their expert opinions on specific submissions that required additional input. Finally, we are also grateful to the ACM SIGMETRICS Chair, Mor Harchol-Balter, to the SIGMETRICS Organization Committee and to the SIGMETRICS Executive Committee for their ongoing efforts and initiatives for creating an exciting program for ACM SIGMETRICS 2025.
This study presents the first global analysis of on-demand video streaming over Low Earth Orbit (LEO) satellite networks, using data from over one million households across 85 countries. We highlight Starlink's role as a major LEO provider, enhancing connectivity in underserved regions. Our findings reveal that while overall video quality on Starlink matches that of traditional networks, the inherent variability in LEO conditions---such as throughput fluctuations and packet loss---leads to an increase in bitrate switches and rebuffers. To further improve the quality of experience for the LEO community, we manipulate existing congestion control and adaptive bitrate streaming algorithms using simulation and real A/B tests deployed on over one million households. Our results underscore the need for video streaming and congestion control algorithms to adapt to rapidly evolving network landscapes, ensuring high-quality service across diverse and dynamic network types.
Stochastic Network Optimization (SNO) concerns scheduling in stochastic queueing systems and has been widely studied in network theory. Classical SNO algorithms require network conditions to be stationary w.r.t. time, which fails to capture the non-stationary components in increasingly many real-world scenarios. Moreover, most existing algorithms in network optimization assume perfect knowledge of network conditions before decision, which again rules out applications where unpredictability in network conditions presents.
Motivated by these issues, this paper considers Adversarial Network Optimization (ANO) under bandit feedback. Specifically, we consider the task of i) maximizing some unknown and time-varying utility function associated with scheduler's actions, where ii) the underlying network topology is a non-stationary multi-hop network whose conditions change arbitrarily with time, and iii) only bandit feedback (the effect of actually deployed actions) is revealed after decision-making. We propose the UMO2 algorithm, which does not require any pre-decision knowledge or counterfactual feedback, ensures network stability, and also matches the utility maximization performance of any "mildly varying" reference policy up to a polynomially decaying gap. To our knowledge, no previous algorithm can handle multi-hop networks or achieve utility maximization guarantees in ANO problems with bandit feedback, whereas ours is able to do both.
Technically, our method builds upon a novel integration of online learning techniques into the Lyapunov drift-plus-penalty method. Specifically, we propose meticulous analytical techniques to jointly balance online learning and Lyapunov arguments, which is used to handle the complex inter-dependency among queues in multi-hop networks. To tackle the learning obstacles due to potentially unbounded queue sizes and negative queue differences, we design a new online linear optimization algorithm that automatically adapts to the unknown (potentially negative) loss magnitudes. Finally, we also propose a bandit convex optimization algorithm with novel queue-dependent learning rate scheduling that suites drastically varying queue lengths in utility maximization. Our new insights and techniques in online learning can also be of independent interest.
The in-memory cache layer is crucial in building a file system. Crash-consistency is highly desirable for applications running on the file system, ensuring that data is written in an all-or-none fashion during unexpected system failures or crashes. However, existing works fail to achieve both high read and write performance in constructing a crash-consistent cache layer.
In this paper, we propose Beaver, a new in-memory file system cache that achieves both crash-consistency and high read/write performance. Beaver exploits a read/write distinguishable memory hierarchy involving both PM and DRAM. Beaver uses the PM to serve write operations for crash-consistency and high write performance, and uses the DRAM to serve read operations for high read performance. We also introduce a kprefetcher to asynchronously move data from PM to DRAM off the critical path of write operations. We extensively evaluated Beaver with the latest file system cache using real-world applications and popular benchmarks. Application evaluation results show that Beaver outperformed other file system caches by up to 16.1% and 11.0% on RocksDB and MinIO, respectively. Beaver's source code is available at https://github.com/PanQL/Beaver.
The thriving mobile app ecosystem encompasses a wide range of functionalities. However, within this ecosystem, a subset of apps provides illicit services such as gambling and pornography to pursue economic gains, collectively referred to as "underground economy apps". While previous studies have examined these apps' characteristics and identification methods, investigations into their distribution via platforms beyond app markets (like Telegram) remain scarce, which has emerged as a crucial channel for underground activities and cybercrime due to the robust encryption and user anonymity.
This study provides the first comprehensive exploration of the underground mobile app ecosystem on Telegram. Overcoming the complexities of the Telegram environment, we build a novel dataset and analyze the prevalence, promotional strategies, and characteristics of these apps. Our findings reveal the significant prevalence of these apps on Telegram, with the total sum of subscription user numbers across channels promoting these apps equivalent to 1% of Telegram's user base. We find these apps primarily cater to gambling and pornography services. We uncover sophisticated promotional strategies involving complex networks of apps, websites, users, and channels, and identify significant gaps in Telegram's content moderation capabilities. Our analysis also exposes the misuse of iOS features for app distribution and the prevalence of malicious behaviors in these apps. This research not only enhances our understanding of the underground app ecosystem but also provides valuable insights for developing effective regulatory measures and protecting users from potential risks associated with these covert operations. Our findings provide implications for platform regulators, app market operators, law enforcement agencies, and cybersecurity professionals in combating the proliferation of underground apps on encrypted messaging platforms.
Despite significant investments in access network infrastructure, universal access to high-quality Internet connectivity remains a challenge. Policymakers often rely on large-scale, crowdsourced measurement datasets to assess the distribution of access network performance across geographic areas. These decisions typically rest on the assumption that Internet performance is uniformly distributed within predefined social boundaries, such as zip codes, census tracts, or neighborhood units. However, this assumption may not be valid for two reasons: (1) crowdsourced measurements often exhibit non-uniform sampling densities within geographic areas; and (2) predefined social boundaries may not align with the actual boundaries of Internet infrastructure.
In this paper, we present a spatial analysis on crowdsourced datasets for constructing stable boundaries for sampling Internet performance. We hypothesize that greater stability in sampling boundaries will reflect the true nature of Internet performance disparities than misleading patterns observed as a result of data sampling variations. We apply and evaluate a series of statistical techniques to: (1) aggregate Internet performance over geographic regions; (2) overlay interpolated maps with various sampling unit choices; and (3) spatially cluster boundary units to identify contiguous areas with similar performance characteristics. We assess the effectiveness of the techniques we apply by comparing the similarity of the resulting boundaries for monthly samples drawn from the dataset. Our evaluation shows that the combination of techniques we apply achieves higher similarity compared to directly calculating central measures of network metrics over census tracts or neighborhood boundaries. These findings underscore the important role of spatial modeling in accurately assessing and optimizing the distribution of Internet performance, which can better inform policy, network operations, and long-term planning decisions.
Confidential computing is gaining traction in the cloud, driven by the increasing security and privacy concerns across various industries. Recent trusted hardware advancements introduce Confidential Virtual Machines (CVMs) to alleviate the programmability and usability challenges of the previously proposed enclave-based trusted computing technologies. CVM hardware extensions facilitate secure, hardware-isolated encrypted VMs, promoting programmability and easier deployment in cloud infrastructures. However, differing microarchitectural features, interfaces, and security properties among hardware vendors complicate the evaluation of CVMs for different use cases. Understanding the performance implications, functional limitations, and security guarantees of CVMs is a crucial step toward their adoption.
This paper presents a detailed empirical analysis of two leading CVM technologies: AMD Secure Encrypted Virtualization-Secure Nested Paging (SEV-SNP) and Intel Trust Domain Extensions (TDX). We review their microarchitectural components and conduct a thorough performance evaluation across various aspects, including memory management, computational performance, storage and network stacks, and attestation primitives. We further present a security analysis through a trusted computing base (TCB) evaluation and Common Vulnerabilities and Exposures (CVE) analysis. Our key findings demonstrate, among others, the effect of CVMs on boot time, memory management and I/O, and identify inefficiencies in their context switch mechanisms. We further provide insights into the performance implications of CVMs and highlight potential room for improvement.
In-band Network Telemetry (INT) enhances real-time, high-resolution network monitoring capabilities by incorporating fine-grained internal state information into packets. Utilizing INT for network-wide visualization can significantly bolster network management and operation. Although existing studies have made significant contributions, they have not been able to simultaneously meet the following two objectives: 1) Comprehensive visibility of the network's internal state, which refers to obtaining information on all switch ports and their corresponding link states; 2) Low measurement overhead, which involves reducing measurement bandwidth overhead and minimizing the impact of the measurement process on the network. We designed INT-MC to meet both of these objectives. INT-MC is an efficient and cost-effective network-wide telemetry solution based on matrix completion. By modeling link metadata as a matrix and leveraging its low-rank property, INT-MC selectively measures certain links. It then employs matrix completion algorithms to infer information about unmeasured links, thereby achieving low-overhead network-wide telemetry. Designing paths to cover the target links involves an NP-complete problem, and the high computational complexity may delay the measurement tasks. To circumvent this, we propose an improved scheme based on Eulerian digraph decomposition, transforming the path calculation problem into a high-information path selection problem, significantly reducing computational costs.
We have implemented an INT-MC prototype within the NSFNet topology, consisting of 14 Tofino switches and 10 end-hosts, and conducted extensive experiments and evaluations. The results indicate that INT-MC incurs only 16% of the measurement overhead compared to existing network-wide telemetry solutions, while achieving nearly identical accuracy. Even under high-frequency measurements of 20 times per second, the bandwidth overhead of INT-MC is approximately 0.075% of the total bandwidth, exerting minimal impact on the network.
This paper studies learning-augmented decentralized online convex optimization in a networked multi-agent system, a challenging setting that has remained under-explored. We first consider a linear learning-augmented decentralized online algorithm (LADO-Lin) that combines a machine learning (ML) policy with a baseline expert policy in a linear manner. We show that, while LADO-Lin can exploit the potential of ML predictions to improve the average cost performance, it cannot have guaranteed worst-case performance. To address this limitation, we propose a novel online algorithm (LADO) that adaptively combines the ML policy and expert policy to safeguard the ML predictions to achieve strong competitiveness guarantees. We also prove the average cost bound for LADO, revealing the tradeoff between average performance and worst-case robustness and demonstrating the advantage of training the ML policy by explicitly considering the robustness requirement. Finally, we run an experiment on decentralized battery management. Our results highlight the potential of ML augmentation to improve the average performance as well as the guaranteed worst-case performance of LADO.
Quantum computing has the potential to accelerate various domains: scientific computation, machine learning, and optimization. Recently, Rydberg atom quantum computing has emerged as a promising quantum computing technology, especially with the demonstration of the zonal addressing architecture. However, this demonstration is only compatible with one type of quantum algorithm, and extending it to compile and execute general quantum algorithms is a challenge. To address it, we propose PachinQo, a framework to co-design the architecture and compilation for zonal addressing systems for any given quantum algorithm. PachinQo's evaluation demonstrates its ability to improve a quantum algorithm's estimated probability of success by 45% on average in error-prone quantum environments.
Byzantine-robust Federated Learning (FL) aims to counter malicious clients and train an accurate global model while maintaining an extremely low attack success rate. Most existing systems, however, are only robust when most of the clients are honest. FLTrust (NDSS '21) and Zeno++ (ICML '20) do not make such an honest majority assumption but can only be applied to scenarios where the server is provided with an auxiliary dataset used to filter malicious updates. FLAME (USENIX '22) and EIFFeL (CCS '22) maintain the semi-honest majority assumption to guarantee robustness and the confidentiality of updates. It is therefore currently impossible to ensure Byzantine robustness and confidentiality of updates without assuming a semi-honest majority. To tackle this problem, we propose a novel Byzantine-robust and privacy-preserving FL system, called MUDGUARD, to capture malicious minority and majority for server and client sides, respectively. Our experimental results demonstrate that the accuracy of MUDGUARD is practically close to the FL baseline using FedAvg without attacks (approximate 0.8% gap on average). Meanwhile, the attack success rate is around 0%-5% even under an adaptive attack tailored to MUDGUARD. We further optimize our design by using binary secret sharing and polynomial transformation leading to communication overhead and runtime decreases of 67%-89.17% and 66.05%-68.75%, respectively.
Many applications, e.g., federated learning, require the aggregation of information across a large number of distributed nodes. In this paper, we explore efficient schemes to do this at scale leveraging aggregation at intermediate nodes across overlay trees. Files/updates are split into chunks which are in turn simultaneously aggregated over different trees. For a synchronous setting with homogeneous communications capabilities and deterministic link delays, we develop a delay optimal aggregation schedule. In the asynchronous setting, where delays are stochastic but i.i.d., across links, we show that for an asynchronous implementation of the above schedule, the expected aggregation delay is near-optimal. We then consider the impact that failures in the network have on the resulting Mean Square Error (MSE) for the estimated aggregates and how it can be controlled through the addition of redundancy, reattempts, and optimal failure-aware estimates for the desired aggregate. Based on the analysis of a natural model of failures, we show how to choose parameters to optimize the trade-off between aggregation delay and MSE. We present simulation results exhibiting the above mentioned tradeoffs. We also consider a more general class of correlated failures and demonstrate via simulation the applicability of our techniques in those settings as well.
The Web3 ecosystem is increasingly evolving to multi-chain, with decentralized applications (dApps) distributing across different blockchains, which drives the need for cross-chain bridges for blockchain interoperability. However, it further opens new attack surfaces, and media outlets have reported serious attacks related to cross-chain bridges. Nevertheless, few prior research studies have studied cross-chain bridges and their related transactions, especially from a security perspective. To fill the void, this paper presents the first comprehensive analysis of cross-chain transactions. We first make efforts to create by far the largest cross-chain transaction dataset based on semantic analysis of popular cross-chain bridges, covering 13 decentralized bridges and 7 representative blockchains, with over 80 million transactions in total. Based on this comprehensive dataset, we present the landscape of cross-chain transactions from angles including token usage, user profile and the purposes of transactions, etc. We further observe that cross-chain bridges can be abused for malicious/aggressive purposes, thus we design an automated detector and deploy it in the wild to flag misbehaviors from millions of cross-chain transactions. We have identified hundreds of abnormal transactions related to exploits and arbitrages, etc. Our research underscores the prevalence of cross-chain ecosystems, unveils their characteristics, and proposes an effective detector for pinpointing security threats.
Graph Neural Networks (GNNs) are emerging models to analyze graph-structure data. GNN execution involves both compute-intensive and memory-intensive kernels. The latter kernels dominate execution time, because they are significantly bottlenecked by data movement between memory and processors. Processing-In-Memory (PIM) systems can alleviate this data movement bottleneck by placing simple processors near or inside to memory arrays. This work investigates the potential of PIM systems to alleviate the data movement bottleneck in GNNs, and introduces PyGim, an efficient and easy-to-use GNN library for real PIM systems. We propose intelligent parallelization techniques for memory-intensive kernels of GNNs tailored for real PIM systems, and develop an easy-to-use Python API for them. PyGim employs a cooperative GNN execution, in which the compute- and memory-intensive kernels are executed in processor-centric and memory-centric computing systems, respectively, to fully exploit the hardware capabilities. PyGim integrates a lightweight autotuner to tune the parallelization strategy of the memory-intensive kernel of GNNs and enable high programming ease. We extensively evaluate PyGim on a real-world PIM system that has 16 PIM DIMMs with 1992 PIM cores connected to a Host CPU. In GNN inference, we demonstrate that it outperforms prior state-of-the-art PIM works by on average 4.38× (up to 7.20×), and state-of-the-art PyTorch running on Host by on average 3.04× (up to 3.44×). PyGim improves energy efficiency by 2.86× (up to 3.68×) and 1.55× (up to 1.75×) over prior PIM and PyTorch Host schemes, respectively. In memory-intensive kernel of GNNs, PyGim provides 11.6× higher resource utilization in PIM system than that of PyTorch library (optimized CUDA implementation) in GPU systems. Our work provides useful recommendations for software, system and hardware designers. PyGim is publicly and freely available at https://github.com/CMU-SAFARI/PyGim facilitate the widespread use of PIM systems in GNNs.
This paper proposes a scalable optimal page replacement policy (OPT) simulator called ScaleOPT to scale the OPT simulation by leveraging multi-core parallelism. Specifically, we first propose AccessMap which collects the future references of pages in parallel before the OPT simulation. It enables calculating the next reference time of the accessed page in a constant time. Second, we introduce Pipelined-Tree consisting of multiple trees which organize caches based on min-max reference times. It enables traverse and update operations of each cache to be performed in a partially parallel manner (i.e., pipelined), thereby scaling out the OPT simulation on multi-cores. Finally, we implement ScaleOPT with two techniques and evaluate it on a 72-core machine. The experimental results demonstrate that ScaleOPT improves the simulation time by up to 6.3×, 7.7×, 20.5×, and 13.9× compared with the long-established standard algorithm-based simulator along with our AccessMap, a variable-size cache scheme, and two widely-used cache simulators (webcachesim and libCacheSim), respectively.
In the Dynamic Bin Packing problem, n items arrive and depart the system in an online manner, and the goal is to maintain a good packing throughout. We consider the objective of minimizing the total active time, i.e., the sum of the number of open bins over all times. An important tool for maintaining an efficient packing in many applications is the use of migrations ; e.g., transferring computing jobs across different machines. However, there are large gaps in our understanding of the approximability of dynamic bin packing with migrations. Prior work has covered the power of no migrations and > n migrations, but we ask the question: What is the power of limited (≤ n) migrations?
Our first result is a dichotomy between no migrations and linear migrations: Using a sublinear number of migrations is asymptotically equivalent to doing zero migrations, where the competitive ratio grows with μ, the ratio of the largest to smallest item duration. On the other hand, we prove that for every α ∈ (0,1], there is an algorithm that does ≈ α n migrations and achieves competitive ratio ≈ 1/α (in particular, independent of μ); we also show that this tradeoff is essentially best possible. This fills in the gap between zero migrations and > n migrations in Dynamic Bin Packing.
Finally, in light of the above impossibility results, we introduce a new model that more directly captures the impact of migrations. Instead of limiting the number of migrations, each migration adds a delay of C time units to the item's duration; this commonly appears in settings where a blackout or set-up time is required before the item can restart its execution in the new bin. In this new model, we prove a O(min(√C, μ))-approximation, and an almost matching lower bound. We also present preliminary experiments that indicate that our theoretical results are predictive of the practical performance of our algorithms.
Microservice architecture is the computing paradigm of choice for large, service-oriented software catering to real-time requests. Individual programs in such a system perform Remote Procedure Calls (RPCs) to other microservices to accomplish sub-tasks. Microservices are designed to be robust; top-level requests can succeed despite errors returned from RPC sub-tasks, referred to as non-fatal errors. Because of this design, the top-level microservices tend to ''live with'' non-fatal errors. Hence, a natural question to ask is ''how prevalent are non-fatal errors and what impact do they have on the exposed latency of top-level requests?''
In this paper, we present a large-scale study of errors in microservices. We answer the aforementioned question by analyzing 11 Billion RPCs covering 1,900 user-facing endpoints at the Uber serving requests of hundreds of millions of active users. To assess the latency impact of non-fatal errors, we develop a methodology that projects potential latency savings for a given request as if the time spent on failing APIs were eliminated. This estimator allows ranking and bubbling up those APIs that are worthy of further investigations, where the non-fatal errors likely resulted in operational inefficiencies. Finally, we employ our error detection and impact estimation techniques to pinpoint operational inefficiencies, which a) result in a tail latency reduction of a critical endpoint by 30% and b) offer insights into common inefficiency-introducing patterns.
MinUsageTime DBP is a variant of the Dynamic Bin Packing (DBP) problem that seeks to minimize the accumulated length of time for which bins are used in packing a sequence of items. This DBP variant models job dispatching for optimizing the busy time of machines, which finds applications in cloud computing and energy-efficient computing. This paper studies the MinUsageTime DBP problem with predictions about item durations (job lengths). We establish tight competitiveness bounds over the entire spectrum of prediction errors. First, we give a lower bound Ω(min {max{ε ⋅ √ log μ, ε2}, μ}) on the competitive ratio of any deterministic online algorithm, where μ is the max/min duration ratio of all items and ε is the maximum multiplicative prediction error. Then, we show that the competitive ratio of a recent algorithm has strictly higher asymptotic order than the above lower bound when ε = ω(1) ∧ ε = o(√ μ). Finally, we present an enhanced algorithm and prove that it achieves a competitive ratio matching the above lower bound, closing the gap for this problem.
In this paper, we examine a novel category of services in the blockchain ecosystem termed Instant Cryptocurrency Exchange (ICE) services. Originally conceived to facilitate cross-chain asset transfers, ICE services have, unfortunately, been abused for money laundering activities due to two key features: the absence of a strict Know Your Customer (KYC) policy and incomplete on-chain data of user requests. As centralized and non-transparent services, ICE services pose considerable challenges in the tracing of illicit fund flows laundered through them. Our comprehensive study of ICE services begins with an analysis of their features and workflow. We classify ICE services into two distinct types: Standalone and Delegated. We then perform a measurement analysis of ICE services, paying particular attention to their usage in illicit activities. Our findings indicate that a total of 12,473,290 illegal funds have been laundered through ICE services, and 432 malicious addresses were initially funded by ICE services. Based on the insights from measurement analysis, we propose a matching algorithm designed to evaluate the effectiveness of ICE services in terms of efficiency and prevention of traceability. Our evaluation reveals that 92% of the user requests analyzed were completed in less than three minutes, underscoring the efficiency of ICE services. In addition, we demonstrate that the algorithm is effective in tracing illicit funds in situations where ICE services are used in malicious activities. To engage the community, the entire dataset used in this study is open-source.
The Border Gateway Protocol (BGP) offers several "knobs" to control routing decisions, but they are coarse-grained and only affect routes received from neighboring Autonomous Systems (AS). To enhance policy expressiveness, BGP was extended with the communities attribute, allowing an AS to attach metadata to routes and influence the routing decisions of a remote AS. The metadata can carry information to (e.g., where a route was received) or request an action from a remote AS (e.g., not to export a route to one of its neighbors). Unfortunately, the semantics of BGP communities are not standardized, lack universal rules, and are poorly documented. In this work, we design and evaluate algorithms to automatically uncover BGP action communities and ASes that violate standard practices by consistently using the information communities of other ASes, revealing undocumented relationships between them (e.g., siblings). Our experimental evaluation with billions of route announcements from public BGP route collectors from 2018 to 2023 uncovers previously unknown AS relationships and shows that our algorithm for identifying action communities achieves average precision and recall of 92.5% and 86.5%, respectively.