Offline reinforcement learning (RL) methods aim to learn optimal policies with access only to trajectories in a fixed dataset. Policy constraint methods formulate policy learning as an optimization problem that balances maximizing reward with minimizing deviation from the behavior policy. Closed form solutions to this problem can be derived as weighted behavioral cloning objectives that, in theory, must compute an intractable partition function. Reinforcement learning has gained popularity in language modeling to align models with human preferences; some recent works consider paired completions that are ranked by a preference model following which the likelihood of the preferred completion is directly increased. We adapt this approach of paired comparison. By reformulating the paired-sample optimization problem, we fit the maximum-mode of the Q function while maximizing behavioral consistency of policy actions. This yields our algorithm, Behavior Preference Regression for offline RL (BPR). We empirically evaluate BPR on the widely used D4RL Locomotion and Antmaze datasets, as well as the more challenging V-D4RL suite, which operates in image-based state spaces. BPR demonstrates state-of-the-art performance over all domains. Our on-policy experiments suggest that BPR takes advantage of the stability of on-policy value functions with minimal performance degradation on Locomotion datasets.

Blockchain’s potential for both financial and societal benefits is affected by regulatory ambiguities and enforcement actions against blockchain entities. Evolving regulatory frameworks emphasize the need for insights to protect users, small investors, and ensure equitable participation. Currently, the lack of systematic analysis creates barriers to understanding trends and making informed decisions about participation. This study proposes methods to analyze litigation drivers by the U.S. Securities and Exchange Commission (SEC), to facilitate regular users’ understanding of regulatory trends to make informed decisions about blockchain participation. Utilizing pretrained language models and large language models, we systematically map all SEC complaints against blockchain companies from 2012 to 2024 to thematic factors conceptualized to delineate the factors that drive SEC actions. We quantify the thematic factors and assess their influence on the legal Acts cited within the complaints on an annual basis, allowing us to discern the regulatory emphasis, patterns and conduct trend analysis.

Decentralized communication is becoming an important use case within Web3. On Ethereum, users can repurpose the transaction input data field to embed natural-language messages, commonly known as Input Data Messages (IDMs). However, as IDMs gain wider adoption, there has been a growing volume of toxic content on-chain. This trend is concerning, as Ethereum provides no protocol-level support for content moderation.We propose two moderation frameworks for Ethereum IDMs: (i) BUILDERMOD, where builders perform semantic checks during block construction; and (ii) USERMOD, where users proactively obtain moderation proofs from external classifiers and embed them in transactions. Our evaluation reveals that BUILDERMOD incurs high block-time overhead, which limits its practicality. In contrast, USERMOD enables lower-latency validation and scales more effectively, making it a more practical approach in moderation-aware Ethereum environments.Our study lays the groundwork for protocol-level content governance in decentralized systems, and we hope it contributes to the development of a decentralized communication environment that is safe, trustworthy, and socially responsible.

MOTIVATION: Survival analysis is a branch of statistics that is crucial in medicine for modeling the time to critical events such as death or relapse, in order to improve treatment strategies and patient outcomes. Selecting survival models often involves a trade-off between performance and interpretability; deep learning models offer high performance but lack the transparency of more traditional approaches. This poses a significant issue in medicine, where practitioners are reluctant to use black-box models for critical patient decisions. RESULTS: We introduce CoxKAN, a Cox proportional hazards Kolmogorov-Arnold Network for interpretable, high-performance survival analysis. Kolmogorov-Arnold Networks (KANs) were recently proposed as an interpretable and accurate alternative to multi-layer perceptrons. We evaluated CoxKAN on four synthetic and nine real datasets, including five cohorts with clinical data and four with genomics biomarkers. In synthetic experiments, CoxKAN accurately recovered interpretable hazard function formulae and excelled in automatic feature selection. Evaluations on real datasets showed that CoxKAN consistently outperformed the traditional Cox proportional hazards model (by up to 4% in C-index) and matched or surpassed the performance of deep learning-based models. Importantly, CoxKAN revealed complex interactions between predictor variables and uncovered symbolic formulae, which are key capabilities that other survival analysis methods lack, to provide clear insights into the impact of key biomarkers on patient risk. AVAILABILITY AND IMPLEMENTATION: CoxKAN is available at GitHub and Zenodo.

Federated learning (FL) is a machine learning paradigm, which enables multiple and decentralized clients to collaboratively train a model under the orchestration of a central aggregator. FL can be a scalable machine learning solution inbig datascenarios. Traditional FL relies on the trust assumption of the central aggregator, which forms cohorts of clients honestly. However, a malicious aggregator, in reality, could abandon and replace the client's training models, or insert fake clients, to manipulate the final training results. In this work, we introducezkFL, which leverages zero-knowledge proofs to tackle the issue of a malicious aggregator during the training model aggregation process. To guarantee the correct aggregation results, the aggregator provides a proof per round, demonstrating to the clients that the aggregator executes the intended behavior faithfully. To further reduce the verification cost of clients, we use blockchain to handle the proof in a zero-knowledge way, where miners (i.e., the participants validating and maintaining the blockchain data) can verify the proof without knowing the clients' local and aggregated models. The theoretical analysis and empirical results show thatzkFLachieves better security and privacy than traditional FL, without modifying the underlying FL network structure or heavily compromising the training speed.

Model-based reinforcement learning (MBRL) algorithms learn a dynamics model from collected data and apply it to generate synthetic trajectories to enable faster learning. This is an especially promising paradigm in offline reinforcement learning (RL) where data may be limited in quantity, in addition to being deficient in coverage and quality. Practical approaches to offline MBRL usually rely on ensembles of dynamics models to prevent exploitation of any individual model and to extract uncertainty estimates that penalize values in states far from the dataset support. Uncertainty estimates from ensembles can vary greatly in scale, making it challenging to generalize hyperparameters well across even similar tasks. In this paper, we present Morse Model-based offline RL (MoMo), which extends the anti-exploration paradigm found in offline model-free RL to the model-based space. We develop model-free and model-based variants of MoMo and show how the model-free version can be extended to detect and deal with out-of-distribution (OOD) states using explicit uncertainty estimation without the need for large ensembles. MoMo performs offline MBRL using an anti-exploration bonus to counteract value overestimation in combination with a policy constraint, as well as a truncation function to terminate synthetic rollouts that are excessively OOD. Experimentally, we find that both model-free and model-based MoMo perform well, and the latter outperforms prior model-based and model-free baselines on the majority of D4RL datasets tested.

In 2016, BitMEX introduced a novel type of crypto derivates – Perpetual Swaps, i.e., futures with an infinite term. Perpetual swaps provide a new strategic risk management tool for cryptocurrencies due to their custody-free nature, high leverage, and funding mechanism, but there has been little quantitative analysis on the their benefits. In this paper, we introduce a trading strategy that combines a Quanto Perpetual Swap with a spot position to benefit from the funding mechanism. We compare our strategy with a long-only investment in the underlying cryptocurrency and a similar strategy based on Linear Perpetual Swaps to evaluate their performances in a large-scale backtest covering the years 2021 and 2022. Our analysis shows that our strategy generates positive returns in bullish market phases of the underlying with lower volatility.

The Proposal for a Regulation of the European Parliament and of the Council on Markets in Crypto-assets or in short – MiCA - aims to establish a regulatory framework for crypto-assets, including cryptocurrencies, security tokens, and stablecoins, in the European Union. The present paper provides a brief overview of the history and development of cryptocurrency regulations in the European Union. The study also examines the MiCA proposals, which seek to establish a standardized regulatory framework for crypto-assets and the possible implications of the proposed regulation for the cryptoasset industry, including the impact on innovation and consumer protection. Additionally, the paper discusses the challenges associated with the implementation of the proposed regulation, including the need for coordination and cooperation between authorities and the potential for regulatory arbitrage.

This paper investigates the implied volatility spillovers of three commodities (bitcoin, gold and oil) onto the stock market (VIX) to determine if bitcoin behaves differently from other commodities in terms of its effect on stock market behaviour. To capture any asymmetry in terms of the change in implied volatility of these commodity markets, we apply a time-lagged asymmetric quantile regression (QR), a nonlinear and heterogeneity-consistent model. Through the data analysis with daily implied volatility data from January 2019 to November 2023 we find an asymmetric relation: impacts of positive changes in gold and oil implied volatility on changes in VIX are stronger than impacts of negative changes, particularly at upper quantiles. This finding supports the intuition that the increase in volatility has a stronger spillover effect than an equivalent magnitude decrease in volatility. We also confirm that gold and oil have tail risk in contrast to bitcoin. We further find that implied volatility in the bitcoin market has less explanatory power with respect to implied volatility of the stock market compared to gold and oil. Taken together, these results can support policy makers and market participants by informing them that bitcoin differs in nature to traditional commodities and works as an effective diversification tool.

Permutation equivariant neural networks are typically used to learn from data that lives on a graph. However, for any graph $G$ that has $n$ vertices, using the symmetric group $S_n$ as its group of symmetries does not take into account the relations that exist between the vertices. Given that the actual group of symmetries is the automorphism group Aut$(G)$, we show how to construct neural networks that are equivariant to Aut$(G)$ by obtaining a full characterisation of the learnable, linear, Aut$(G)$-equivariant functions between layers that are some tensor power of $\mathbb{R}^{n}$. In particular, we find a spanning set of matrices for these layer functions in the standard basis of $\mathbb{R}^{n}$. This result has important consequences for learning from data whose group of symmetries is a finite group because a theorem by Frucht (1938) showed that any finite group is isomorphic to the automorphism group of a graph.

Introduction to the Special Issue on Mathematical Research for Blockchain EconomyBlockchain Technology has been considered as the most revolutionizing invention since the Internet.Because of its immutable nature and the associated security and privacy benefits, it has widely attracted the attention of banks, governments, techno-corporations and venture investors.Blockchain applications range from finance to healthcare, from education and media to logistics, NFTs and many more.However, the theoretical limitations and technical barriers to the adoption of blockchain such as scalability, latency, privacy and security need to be further studied and addressed in high-quality research.This special issue of the ACM Distributed Ledger Technologies: Research and Practice (ACM DLT) journals contains selected and refereed papers on the topic of Mathematical Research in Blockchain Economies.Preliminary versions of some of the papers appeared in the 2022 edition of the International Conference on Mathematical Research for Blockchain Economy (MARBLE'22), which took place in Vilamoura, Portugal, from July 12 to 24, 2022.Following the paradigm of the conference, the current special issue provides a high-profile, cutting-edge platform for mathematicians, computer scientists and economists, from both industry and practice, to present the latest advances and innovations in key theories of blockchain.Having a broad international appeal, both the MARBLE conference and the current special issue focuses on the mathematics behind blockchain to bridge the gap between theory and practice.The three selected article in this special issue were selected from 10 submitted manuscripts, following the standard, rigorous ACM DLT review procedures.The articles cover topics in decentralized finance, smart contracts and game-theoretic modelling of blockchains.The content of the articles is as follows.

This paper examines the hedging effectiveness of Bitcoin futures by comparing one form of the constant model, the conventional OLS method, with the time-varying model in estimating the optimal hedge ratio. For the time-varying model, we employ a powerful technique, Kalman filter, a r ecursive a lgorithm w hich h as n umerous real-time, technological applications, but has not been employed in the context of Bitcoin optimal hedge ratio analysis. Through applying the spot and futures daily settlement prices from 18th December 2017 to 30th November 2022 to the two models, we confirm that t he B itcoin futures is an effective instrument for risk hedging. Additionally, we find the dynamic model based on the Kalman filter p erforms b etter - especially in 2019 and 2020 - than the conventional OLS method in terms of risk reduction, supporting previous findings in the context of other commodity futures. We also certify that the Kalman filter s uccessfully c aptures the trend of the optimal hedge ratio, thus enabling hedgers to decide when to change their hedging strategy. Furthermore, we verify the volatile evolution of the estimated time-varying Bitcoin optimal hedge ratio, suggesting the need to further search for a better hedging instrument which achieves a less volatile time path to avoid excessive trading costs.

Decentralized Finance (DeFi), a blockchain powered peer-to-peer financial system, is mushrooming. Two years ago the total value locked in DeFi systems was approximately 700m USD, now, as of April 2022, it stands at around 150bn USD. The frenetic evolution of the ecosystem has created challenges in understanding the basic principles of these systems and their security risks. In this Systematization of Knowledge (SoK) we delineate the DeFi ecosystem along the following axes: its primitives, its operational protocol types and its security. We provide a distinction between technical security, which has a healthy literature, and economic security, which is largely unexplored, connecting the latter with new models and thereby synthesizing insights from computer science, economics and finance. Finally, we outline the open research challenges in the ecosystem across these security types.

This paper examines the determinants of the volatility of futures prices and basis for three commodities: gold, oil and Bitcoin – often dubbed solid, liquid and digital gold – by using contract-by-contract analysis which has been previously applied to crude oil futures volatility investigations. By extracting the spot and futures daily prices as well as the maturity, trading volume and open interest data for the three assets from 18th December 2017 to 30th November 2021, we find a positive and significant role for trading volume and a possible negative influence of open interest (when significant) in shaping the volatility in all three assets, supporting earlier findings in the context of oil futures. Additionally, we find maturity has a relatively positive significance for Bitcoin and oil futures price volatility. Furthermore, our analysis demonstrates that maturity affects the basis of Bitcoin and gold positively – confirming the general theory that the basis converges to zero as maturity nears for Bitcoin and gold – while oil is affected in both directions.

We coin the term Protocols for Loanable Funds (PLFs) to refer to protocols which establish distributed ledger-based markets for loanable funds. PLFs are emerging as one of the main applications within Decentralized Finance (DeFi), and use smart contract code to facilitate the intermediation of loanable funds. In doing so, these protocols allow agents to borrow and save programmatically. Within these protocols, interest rate mechanisms seek to equilibrate the supply and demand for funds. In this paper, we review the methodologies used to set interest rates on three prominent DeFi PLFs, namely Compound, Aave and dYdX. We provide an empirical examination of how these interest rate rules have behaved since their inception in response to differing degrees of liquidity. We then investigate the market efficiency and inter-connectedness between multiple protocols, examining first whether Uncovered Interest Parity holds within a particular protocol and second whether the interest rates for a particular token market show dependence across protocols, developing a Vector Error Correction Model for the dynamics.

Financial deposits are fundamental to the security of cryptoeconomic protocols as they serve as insurance against potential misbehaviour of agents. However, protocol designers and their agents face a trade-off when choosing the deposit size. While substantial deposits might increase the protocol security, for example by minimising the impact of adversarial behaviour or risks of currency fluctuations, locked-up capital incurs opportunity costs. Moreover, some protocols require over-collateralization in anticipation of future events and malicious intentions of agents. We present Balance, an application-agnostic system that reduces over-collateralization without compromising protocol security. In Balance, malicious agents receive no additional utility for cheating once their deposits are reduced. At the same time, honest and rational agents increase their utilities for behaving honestly as their opportunity costs for the locked-up deposits are reduced. Balance is a round-based mechanism in which agents need to continuously perform desired actions. Rather than treating agents' incentives and behaviour as ancillary, we explicitly model agents' utility, proving the conditions for incentive compatibility. Balance improves social welfare given a distribution of honest, rational, and malicious agents. Further, we integrate Balance with a cross-chain interoperability protocol, XCLAIM, reducing deposits by 10% while maintaining the same utility for behaving honestly. Our implementation allows any number of agents to be maintained for at most 55,287 gas (~ USD 0.07) to update all agents' scores, and at a cost of 54,948 gas (~ USD 0.07) to update the assignment of all agents to layers.

Building trustless cross-blockchain trading protocols is challenging. Centralized exchanges thus remain the preferred route to execute transfers across blockchains. However, these services require trust and therefore undermine the very nature of the blockchains on which they operate. To overcome this, several decentralized exchanges have recently emerged which offer support for atomic cross-chain swaps (ACCS). ACCS enable the trustless exchange of cryptocurrencies across blockchains, and are the only known mechanism to do so. However, ACCS suffer significant limitations; they are slow, inefficient and costly, meaning that they are rarely used in practice. We present XCLAIM: the first generic framework for achieving trustless and efficient cross-chain exchanges using cryptocurrency-backed assets (CbAs). XCLAIM offers protocols for issuing, transferring, swapping and redeeming CbAs securely in a non-interactive manner on existing blockchains. We instantiate XCLAIM between Bitcoin and Ethereum and evaluate our implementation; it costs less than USD 0.50 to issue an arbitrary amount of Bitcoin-backed tokens on Ethereum. We show XCLAIM is not only faster, but also significantly cheaper than atomic cross-chain swaps. Finally, XCLAIM is compatible with the majority of existing blockchains without modification, and enables several novel cryptocurrency applications, such as cross-chain payment channels and efficient multi-party swaps.

Application partitioning that splits the executions into local and remote parts, plays a critical role in high-performance mobile offloading systems. Optimal partitioning will allow mobile devices to obtain the highest benefit from Mobile Cloud Computing (MCC) or Mobile Edge Computing (MEC). Due to unstable resources in the wireless network (network disconnection, bandwidth fluctuation, network latency, etc.) and at the service nodes (different speeds of mobile devices and cloud/edge servers, memory, etc.), static partitioning solutions with fixed bandwidth and speed assumptions are unsuitable for offloading systems. In this paper, we study how to dynamically partition a given application effectively into local and remote parts while reducing the total cost to the degree possible. For general tasks (represented in arbitrary topological consumption graphs), we propose a Min-Cost Offloading Partitioning (MCOP) algorithm that aims at finding the optimal partitioning plan (i.e., to determine which portions of the application must run on the mobile device and which portions on cloud/edge servers) under different cost models and mobile environments. Simulation results show that the MCOP algorithm provides a stable method with low time complexity which significantly reduces execution time and energy consumption by optimally distributing tasks between mobile devices and servers, besides it adapts well to mobile environmental changes.

Cryptocurrency mining can be said to be the modern alchemy, involving as it does the transmutation of electricity into digital gold. The goal of mining is to guess the solution to a cryptographic puzzle, the difficulty of which is determined by the network, and thence to win the block reward and transaction fees. Because the return on solo mining has a very high variance, miners band together to create so-called mining pools. These aggregate the power of several individual miners, and, by distributing the accumulated rewards according to some scheme, ensure a more predictable return for participants.In this paper we formulate a model of the dynamics of a queue-based reward distribution scheme in a popular Ethereum mining pool and develop a corresponding simulation. We show that the underlying mechanism disadvantages miners with above-average hash rates. We then consider two-miner scenarios and show how large miners may perform attacks to increase their profits at the expense of other participants of the mining pool. The outcomes of our analysis show the queue-based reward scheme is vulnerable to manipulation in its current implementation.

Virtual machine consolidation is attractive in cloud computing platforms for several reasons including reduced infrastructure costs, lower energy consumption and ease of management. However, the interference between co-resident workloads caused by virtualization can violate the service level objectives (SLOs) that the cloud platform guarantees. Existing solutions to minimize interference between virtual machines (VMs) are mostly based on comprehensive micro-benchmarks or online training which makes them computationally intensive. In this paper, we present CloudScope, a system for diagnosing interference for multi-tenant cloud systems in a lightweight way. CloudScope employs a discrete-time Markov Chain model for the online prediction of performance interference of co-resident VMs. It uses the results to optimally (re)assign VMs to physical machines and to optimize the hypervisor configuration, e.g. the CPU share it can use, for different workloads. We have implemented CloudScope on top of the Xen hypervisor and conducted experiments using a set of CPU, disk, and network intensive workloads and a real system (MapReduce). Our results show that CloudScope interference prediction achieves an average error of 9%. The interference-aware scheduler improves VM performance by up to 10% compared to the default scheduler. In addition, the hypervisor reconfiguration can improve network throughput by up to 30%.

Cloud-based software systems are expected to deliver reliable performance under dynamic workload while efficiently managing resources. Conventional monitoring frameworks provide limited support for flexible and intuitive performance queries. In this paper, we present a prototype monitoring and control platform for clouds that is a better fit to the characteristics of cloud computing (e.g. extensible, user-defined, scalable). Service Level Objectives (SLOs) are expressed graphically as Performance Trees, while violated SLOs trigger mitigating control actions.

As the computing industry enters the Cloud era, multicore architectures and virtualisation technologies are replacing traditional IT infrastructures. However, the complex relationship between applications and system resources in multicore virtualised environments is not well understood. Workloads such as web services and on-line financial applications have the requirement of high performance but benchmark analysis suggests that these applications do not optimally benefit from a higher number of cores.

Stochastic performance models are widely used to analyse systems that involve the flow and processing of customers and resources. However, model formulation and parameterisation are traditionally manual and thus expensive, intrusive and error-prone. Our earlier work has demonstrated the feasibility of automated performance model construction from location tracking data. In particular, we presented a methodology based on a four-stage data processing pipeline, which automatically constructs Generalised Stochastic Petri Net (GSPN) performance models from an input dataset of raw location tracking traces. This pipeline was enhanced with a presence-based synchronisation detection mechanism.

Most performance evaluation studies of database systems are high level studies limited by the expressiveness of their modelling formalisms. In this paper, we illustrate the potential of Queueing Petri Nets as a successor of traditionally-adopted modelling formalisms in evaluating the complexities of database systems. This is demonstrated through the construction and analysis of a Queueing Petri Net model of table-level database locking. We show that this model predicts mean response times better than a corresponding Petri net model.

The amount of data managed by organisations continues to grow relentlessly. Driven by the high costs of maintaining multiple local storage systems, there is a well established trend towards storage consolidation using multi-tier Virtualised Storage Systems (VSSs). At the same time, storage infrastructures are increasingly subject to stringent Quality of Service (QoS) demands. Within a VSS, it is challenging to match desired QoS with delivered QoS, considering the latter can vary dramatically both across and within tiers. Manual efforts to achieve this match require extensive and ongoing human intervention. This paper presents our work on the design and implementation of data allocation strategies in an enhanced version of the popular Linux Extended 3 Filesystem. This enhanced fllesystem features support for the specification of QoS metadata while maintaining compatibility with stock kernels. We present new inode and datablock allocation strategies which seek to match the QoS attributes set by users and/or applications on files and directories with the QoS actually delivered by each of the filesystem's block groups. To create realistic test filesystems we have modified the Impressions benchmarking framework to support QoS metadata. The effectiveness of the resulting data allocation in terms of QoS matching is evaluated using a special kernel module that is capable of inspecting detailed filesystem allocation data on the-fly. We show that our implementations of the proposed inode and datablock allocation strategies are capable of dramatically improving data placement with respect to QoS requirements when compared to the default allocators.

RAID systems are ubiquitously deployed in storage environments, both as standalone storage solutions and as fundamental components of virtualized storage platforms. Accurate models of their performance are crucial to delivering storage infrastructures that meet given quality of service requirements. To this end, this paper presents a flexible fork-join queueing simulation model of RAID systems that are composed of zoned disk drives and which operate under RAID levels 01 or 5. The simulator takes as input I/O workloads that are heterogeneous in terms of request size and that exhibit burstiness, and its primary output metric is I/O request response time distribution. We also study the effects of heavy workload, taking into account the request-reordering optimizations employed by modern disk drives. All simulation results are validated against device measurements and compared with existing analytical queueing network models for the development of the models.

Traditional methods for deriving performance models of customer flow in real-life systems are manual, timeconsuming and prone to human error. This paper proposes an automated four-stage data processing pipeline which takes as input raw high-precision location tracking data and which outputs a queueing network model of customer flow. The pipeline estimates both the structure of the network and the underlying interarrival and service time distributions of its component service centres. We evaluate our method’s effectiveness and accuracy in four experimental case studies.

We introduce Performance Trees (PTs), a novel representation formalism for the specification of model-based performance queries. Traditionally, stochastic logics have been the prevalent means of performance requirement expression; however, in practice, their use amongst system designers is limited on account of their inherent complexity and restricted expressive power. PTs are a more accessible alternative, in which performance queries are represented by hierarchical tree structures. This allows for the convenient visual composition of complex performance questions, and enables not only the verification of stochastic requirements, but also the direct extraction of performance measures. In addition, PTs offer a superset of the expressiveness of Continuous Stochastic Logic (CSL) since all CSL formulae can be translated into PT form. Performance Trees can be used to represent passage time, transient, steady-state and higher order queries of varying levels of sophistication. While they are conceptually independent of the underlying stochastic modelling formalism, in many cases the tree operators we use are already backed up by good algorithmic and tool support for both stochastic verification and performance measure extraction. We do not therefore perceive major barriers to the integration of PTs into existing stochastic model checking tools. Indeed, we illustrate how semi-Markov passage time computation algorithms, based on numerical Laplace transform inversion, can be directly applied to the resolution of a case study PT query.

Summary form only given. Here we present a disk-based parallel formulation of the multilevel k-way hypergraph partitioning algorithm. This algorithm provides the capability to partition very large hypergraphs that hitherto could not be partitioned since the memory required exceeds that available on a single workstation. The algorithm has three main phases: parallel coarsening, sequential partitioning of the coarsest hypergraph and parallel refinement. At each parallel coarsening and refinement step disk is used to minimise memory usage. We apply the algorithm to very large hypergraphs with /spl Theta/(10/sup 7 /) vertices from the domain of performance modelling and show that the partitioning quality is approximately 20% better in terms of the (k - 1) metric than approximate partitionings produced by a state-of-the-art parallel graph partitioning tool.

Probability distributions of response times are important in the design and analysis of transaction processing systems and computer-communication systems. We present a general technique for deriving such distributions from high-level modelling formalisms whose state spaces can be mapped onto finite Markov chains. We use a load-balanced, distributed implementation to find the Laplace transform of the first passage time density and its derivatives at arbitrary values of the transform parameter s. Setting s = 0 yields moments while the full passage time distribution is obtained using a novel distributed Laplace transform inverter based on the Laguerre method. We validate our method against a variety of simple densities, cycle time densities in certain overtake-free (tree-like) queueing networks and a simulated Petri net model. Our implementation is thereby rigorously validated and has already been applied to substantial Markov chains with over 1 million states. Corresponding theoretical results for semi-Markov chains are also presented.