We study the robust geometric median problem in Euclidean space $\mathbb{R}^d$, with a focus on coreset construction. A coreset is a compact summary of a dataset $P$ of size $n$ that approximates the robust cost for all centers $c$ within a multiplicative error $\varepsilon$. Given an outlier count $m$, we construct a coreset of size $\tilde{O}(\varepsilon^{-2} \cdot \min \\{ \varepsilon^{-2}, d \\})$ when $n \geq 4m$, eliminating the $O(m)$ dependency present in prior work [Huang et al., 2022 & 2023]. For the special case of $d = 1$, we achieve an optimal coreset size of $\tilde{\Theta}(\varepsilon^{-1/2} + \frac{m}{n} \varepsilon^{-1})$, revealing a clear separation from the vanilla case studied in [Huang et al., 2023; Afshani and Chris, 2024]. Our results further extend to robust $(k,z)$-clustering in various metric spaces, eliminating the $m$-dependence under mild data assumptions. The key technical contribution is a novel non-component-wise error analysis, enabling substantial reduction of outlier influence, unlike prior methods that retain them. Empirically, our algorithms consistently outperform existing baselines in terms of size-accuracy tradeoffs and runtime, even when data assumptions are violated across a wide range of datasets.

We study the problem of constructing coresets for $(k, z)$-clustering when the input dataset is corrupted by stochastic noise drawn from a known distribution. In this setting, evaluating the quality of a coreset is inherently challenging, as the true underlying dataset is unobserved. To address this, we investigate coreset construction using surrogate error metrics that are tractable and provably related to the true clustering cost. We analyze a traditional metric from prior work and introduce a new error metric that more closely aligns with the true cost. Although our metric is defined independent of the noise distribution, it enables approximation guarantees that scale with the noise level. We design a coreset construction algorithm based on this metric and show that, under mild assumptions on the data and noise, enforcing an $\varepsilon$-bound under our metric yields smaller coresets and tighter guarantees on the true clustering cost than those obtained via classical metrics. In particular, we prove that the coreset size can improve by a factor of up to $\mathrm{poly}(k)$, where $n$ is the dataset size. Experiments on real-world datasets support our theoretical findings and demonstrate the practical advantages of our approach.

Abstract Internet of Things (IoT) jobs not only require computational resources but also are delay-sensitive and security-sensitive. Edge computing emerges as a promising paradigm to improve the quality of experience for IoT users. Edge computing faces many security threats, perhaps even more than traditional data centers. With a growing amount of data offloaded to Edge Data Centers (EDCs), the EDC performance needs to be considered and evaluated carefully for improving the vulnerable EDC resource utilization while satisfying IoT job requirements. This paper develops an analytical model, which can capture the dynamics of an EDC system with the following features: (i) The system is under heterogeneous workloads; (ii) the system is subject to attacks, which prevent equipment units in the system from providing service and (iii) the jobs in the system are delay-sensitive. Namely, the job processing fails before the processing is completed. Based on the proposed model, we develop formulas for performance and profit metrics and conduct a series of simulation experiments to verify the correctness and accuracy of our model. Finally, through our model, we evaluate the performance of the EDC, and we offer solutions for EDC administrators to maximize profit.

Fork after withholding (FAW) attack is an easy-to-conduct attack in the Bitcoin system and it is hard to be detected than some attacks like selfish mining and selfholding attacks. The previous studies about FAW attack made some strong assumptions, such as no propagation delay in the network.

Malignant miners with small computing power can achieve unfair revenue and degrade system throughput through launching Fork after withholding (FAW) attack in a Proof-of-Work (PoW) blockchain system. The existing works about FAW attack have some of the following issues: (i) only studying Bitcoin blockchain, (ii) assuming that the blockchain network is perfect and then ignoring forks due to block propagation delay, and (iii) assuming that there is only one pool under attack. This paper attempts to investigate FAW attack in imperfect Bitcoin and Ethereum networks where malicious miners attack multiple victim pools. We develop a simulator to capture the chain dynamics under FAW attack in a PoW system where the longest-chain protocol is used. Two different computing power allocation strategies for malicious miners, PAS and EAS, are investigated in terms of the profitability of FAW adversaries, the loss of victims, and the blockchain throughput. The results reveal that FAW adversaries can get more revenue under PAS when more victim pools are subjected to attack in both Bitcoin and Ethereum. If FAW adversaries adopt EAS and the number of victims vary from 1 to 12, they can get maximal revenue when attack 7 victims in Bitcoin. The blockchain throughput decreases significantly under PAS while it is almost unchanged under EAS with the increasing number of victims in both Bitcoin and Ethereum. Our work helps the design of countermeasures against FAW attack.

The longest-chain and Greedy Heaviest Observed Subtree (GHOST) protocols are the two most famous chain-selection protocols to address forking in Proof-of-Work (PoW) blockchain systems. Inclusive protocol was proposed to lower the loss of miners who produce stale blocks and increase the blockchain throughput. This paper aims to make an analytical-model-based quantitative comparison of their capabilities against selfish mining attack. Analytical models have been developed for the longest-chain protocol but less to the GHOST protocol. However, the blockchain dynamics and evolution are different when adopting different chain-selection protocols. Therefore, the corresponding analytical models and/or the formulas of calculating metrics (such as miner profitability and system throughput) may be different. To address these challenges, this paper first develops a novel Markov model and the formulas of evaluation metrics, in order to analyze a GHOST-based blockchain system under selfish mining attack. Then extensive experiments are conducted for comparison and we observe that: (i) The GHOST protocol is more resistant to selfish mining attack than the longest-chain protocol from the aspect of relative revenue of selfish miners. (ii) Inclusive protocol can promote the security (evaluated in terms of miner profitability) improvement of the system which has little total computational power or a high forking probability. Additionally, the longest-chain protocol is more sensitive to inclusive protocol than GHOST protocol. (iii) It is hard for each of the two common-used difficulty adjustment algorithms to achieve higher system throughput and security.

Selfish mining, as a serious threat to blockchain, has been attracting attentions from academic and industry. Stochastic modeling has been explored to quantitatively investigate selfish mining in imperfect blockchain networks. However, prior modeling-based analysis approaches have some of the following issues: (1) only focus on Bitcoin or Ethereum, or (2) ignore extended forks and just consider natural forks, or (3) only compute the mining revenue without assessing the performance and security of the blockchain system when the system suffers from selfish mining. In this paper, we aim to address these issues. We build a Markov chain to make quantitative analysis of selfish mining in imperfect Bitcoin and Ethereum networks with natural and extended forks. Formulas are derived to calculate the mining revenue for the selfish pool (comprising selfish miners) and honest miners, respectively. Moreover, we derive the formulas of performance metrics (namely, transactions per second and stale block ratio) and the formula of security metric (namely, the probability of double-spending success) of the system. These quantitative results can help understand the impact of selfish mining on imperfect blockchain networks and then help the detection of selfish mining.

Abstract The rapid and widespread adoption of internet of things-related services advances the development of the cloud-edge framework, including multiple cloud datacenters (CDCs) and edge micro-datacenters (EDCs). This paper aims to apply analytical modeling techniques to assess the effectiveness of cloud-edge computing resource allocation policies from the perspective of improving the performance of cloud-edge service. We focus on two types of physical device (PD)-allocation policies that define how to select a PD from a CDC/EDC for service provision. The first is randomly selecting a PD, denoted as RandAvail. The other is denoted as SEQ, in which an available idle PD is selected to serve client requests only after the waiting queues of all busy PDs are full. We first present the models in the case of an On–Off request arrival process and verify the approximate accuracy of the proposed models through simulations. Then, we apply analytical models for comparing RandAvail and SEQ policies, in terms of request rejection probability and mean response time, under various system parameter settings.

Moving Target Defense (MTD) technology protects a target system by complicating the attacking process of adversaries. It has been gaining more and more attention with the massive growth of vulnerabilities and the widespread deployment of critical network services. This paper aims to analyze service Mean Time To Failure (MTTF) in a vulnerable network system which suffers attacks from adversaries. The system consists of multiple Physical Machines (PM) and each PM can support Docker Containers (DC) to run service. It applies Dynamic Platform Protection Technique (DPT), a kind of MTD techniques, to reduce the impact of attacks on service. A DC can be live migrated among these PMs in order to provision continuous service to users. We propose a model which captures the service behaviors during the service execution in the system. Our model allows both service residency/execution time at a PM and service migration time to be generally distributed. We also derive the formula for calculating MTTF and its approximate accuracy is validated through comparing analytical results with simulation results. Moreover, a formula is proposed to predict the total cost of the system, which helps administrators manage the network system effectively.

With the coming age of big data, the image signals play more and more important role in our life due to the extraordinary advance of network communication technology, and the corresponding high efficiency image processing techniques are demanded urgently. The Fourier transform is an important image processing tool which is used in a wide range of applications. Traditional Fourier transform algorithm computes on the value of each point of image, regardless of their properties in frequency domain. However, most image signals possess sparsity in frequency domain. In this paper, we present a new fast two-dimensional Fourier transform based on image sparsity. With hash function including a series of procedures such as random spectrum permutation, filtering and subsampling in frequency domain, the algorithm could identify and estimate the k largest coefficients quickly. In most sparse cases, the resulting algorithm performs faster than state-of-the-art fast Fourier transform algorithm, FFTW.