Adversarial patch attacks inject localized perturbations into images to mislead deep vision models. These attacks can be physically deployed, posing serious risks to real-world applications. In this paper, we propose CertMask, a certifiably robust defense that constructs a provably sufficient set of binary masks to neutralize patch effects with strong theoretical guarantees. While the state-of-the-art approach (PatchCleanser) requires two rounds of masking and incurs O(n^2) inference cost, CertMask performs only a single round of masking with O(n) time complexity, where n is the cardinality of the mask set to cover an input image. Our proposed mask set is computed using a mathematically rigorous coverage strategy that ensures each possible patch location is covered at least k times, providing both efficiency and robustness. We offer a theoretical analysis of the coverage condition and prove its sufficiency for certification. Experiments on ImageNet, ImageNette, and CIFAR-10 show that CertMask improves certified robust accuracy by up to +13.4% over PatchCleanser, while maintaining clean accuracy nearly identical to the vanilla model.

We introduce and study transfer schedulability , a novel concept that describes how properties of a reference schedule derived from a scheduling algorithm \(\mathcal {A}\) are transferred onto another scheduling algorithm \(\mathcal {B}\) for a given task system and fixed arrival times. Specifically, we say schedulability is transferred from \(\mathcal {A}\) to \(\mathcal {B}\) if the task set is schedulable under \(\mathcal {B}\) whenever all deadlines are met in the reference schedule produced by \(\mathcal {A}\) . We identify a sufficient criterion for schedulability to be transferred on uniprocessor systems, which we verify with the Rocq proof assistant, and based on this criterion develop runtime mechanisms that enforce transfer schedulability. We relate transfer schedulability to prior approaches from the literature and demonstrate how the concept can be utilized to avoid timing anomalies and lower runtime scheduling overheads. We demonstrate that transfer schedulability can be utilized to prevent timing anomalies for non-preemptive scheduling, self-suspending tasks, and directed acyclic graph (DAG) tasks where the edges induce delays. Our evaluation on synthesized task sets shows improved schedulability compared to standard scheduling algorithms. We also evaluated the number of interventions necessary to transfer schedulability, and additionally demonstrate that the proposed runtime mechanisms eliminate timing anomalies (like a completely static, fully table-driven approach) while achieving a response-time distribution closely resembling those of classic dynamic, event-driven schedulers like EDF.

Sensor fusion is the process of combining data from multiple sensors for acquiring a more accurate and comprehensive understanding of the observed environment. However, temporal misalignments between sensors can lead to incorrect fusion results, while the temporal robustness of sensor fusion algorithms is still a relatively unexplored research topic. To address this gap, we define three types of temporal robustness for sensor fusion: reference-point-based, strong sample-point-based, and weak sample-point-based temporal robustness. These definitions provide a framework to quantitatively evaluate the temporal robustness of sensor fusion functions. We also investigate the case where only a part of the sensors are misaligned. Furthermore, we consider potential probabilistic aspects for the proposed definitions. We assess the temporal robustness of a state-of-the-art fusion method in the context of 3D object detection, where camera and LiDAR data are fused. Our empirical evaluation shows that the examined fusion methods exhibit moderate robustness against temporal misalignment of images, but are especially sensitive to LiDAR misalignment. Our findings call attention to the necessity of providing robustness guarantees for sensor fusion functions against temporal misalignment.

In the near future, smart cities are expected to become more prevalent, with Uncrewed Aerial Vehicles (UAVs) playing a key role in making cities more efficient and sustainable. Effective path planning is essential for the safe and efficient integration of drones into urban airspace. However, one potential limitation of UAVs is that they may not have sufficient computing power to perform real-time contingency planning when encountering obstacles. To address this challenge, this work proposes edge-assisted offloading scenarios where contingency planning is considered as a resource-intensive task that can be offloaded to nearby edge nodes. We implemented and compared various strategies for generating offloading plans in a robot swarm simulator based on latency and cost metrics. Our evaluation revealed that the offloading plans generated using the genetic algorithm tended to perform better in terms of average latency or cost per offloading, albeit with higher runtime overhead compared to the other strategies.

Timing guarantee is an important aspect and must be ensured for every individual task in real-time systems. Even for periodic tasks, providing timing guarantees for segmented self-suspending tasks is challenging due to timing anomalies, i.e., the reduction of execution or suspension time of some jobs enlarges the response time of another job. The existing worstcase response time analyses for sporadic self-suspending tasks are only over-approximations and lead to overly pessimistic results. In this paper, we focus on eliminating timing anomalies without negative impacts on the worst-case response time (WCRT) analysis when scheduling periodic tasks with segmented selfsuspension behavior. We propose two treatments, segment release time enforcement and segmentpriority modification, and prove that both treatments eliminate timing anomalies. In our evaluation, the proposed treatments achieve higher acceptance ratios in terms of schedulability compared to state-of-the-art scheduling algorithms. We also implement the segment-level fixed-priority scheduling mechanism on RTEMS, and showcase the validity of the treatment segment priority modification.

To utilize the performance benefits of heterogeneous multicore platforms in real-time systems, we need task models that expose the parallelism and heterogeneity of the workload, such as typed DAG tasks, as well as scheduling algorithms that effectively exploit this information. In this paper, we introducetype-aware federated schedulingalgorithms for sporadic typed DAG tasks with implicit deadlines running on a heterogeneous multicore platform with two different types of cores. In type-aware federated scheduling, a task can be executed in one of the three strategies:Exclusive Allocation,Semi-Exclusive Allocation, andSequential and Share. InExclusive Allocation, clusters of cores of both core types are exclusively allocated to tasks, while cores of only one type are exclusively allocated to tasks inSemi-Exclusive Allocation. The workload of the other type from tasks inSemi-Exclusive Allocationand the workload from tasks inSequential and Shareshare the cores that are not exclusively allocated to any task. We prove that our type-aware federated scheduling algorithm has a capacity augmentation bound of 7.25. We also show that no constant capacity augmentation bound can be obtained withoutSemi-Exclusive Allocation. Compared to the state of the art, the type-aware federated scheduling algorithm achieves better schedulability, especially for task sets with skewed workload.

In this paper, we propose a bicameralism voting to improve the accuracy of a deep learning network. After we train a deep learning network with existing data, we may want to improve it with some newly collected data. However, it would be time consuming if we retrain the model with all the available data. Instead, we propose a collective framework that train models on mobile devices with new data (also collected from the mobile devices) via transfer learning. Then we collect the predictions from these new models from the mobile devices, and achieve more accurate predictions by combining their predictions via voting. The proposed bicameralism voting is different from federated learning, since we do not average the weights of models from mobile devices, but let them vote by bicameralism. The proposed bicameralism voting mechanism has three advantages. First, this collective mechanism improves the accuracy of the deep learning model. The accuracy of bicameralism voting (VGG-19 on the data set Food-101 dataset) is 77.838%, higher than that of a single model (75.517%) with the same amount of training data. Second, the bicameralism voting saves computation resource, because it only updates an existing model, and can be done in parallel by multiple devices. For example, in our experiments to update an existing model via transfer learning takes about 10 minutes on a server, but to train a model from scratch with both the original and the new data will take more than a week. Finally, the bicameralism voting is flexible. Unlike federated learning, bicameralism voting can use any architecture of model, any preprocessing of input data, and any format of model when the models are trained on different mobile devices.

Infrastructure-as-a-Service (IaaS) is a popular form of cloud computing that provides virtualized computing resources. The current trend of IaaS is moving from virtual machine-based into container-based. In this paper, we study the energy-efficient resource allocation problem for container-based virtualization in a data center. Our goal is to minimize the energy consumption by determining 1) the number of cores allocated to a container, 2) the operating frequency of the container, and 3) the deployment of the container to server. Every container has to meet its service level agreement (SLA). We propose dynamic programming algorithms that can be used under different scenarios, depending on the affordable time complexity. The performance of the proposed algorithms is evaluated with energy consumption data collected from experiments.

Deep learning is an increasingly important technique that can solve complex problems. Due to the growth of data and model complexity, large-scale deep learning has became an important issue. Distributed deep learning is an efficient way to address these complexity issues in training a huge model. However, in a distributed environment network bandwidth becomes a performance bottleneck for deep learning. We propose various optimizations in reducing network usage by scheduling network request events properly, so as to reduce the total training time. These scheduling optimization only requires software innovation and without the need to upgrade physical network bandwidth, thus is economically competitive. The experiments indicate that our scheduler achieves up to 25 % speedup over traditional schedulers.

Auto-scaling is a technique that allocates resources according to dynamic workload. This paper focuses on auto-scaling with heterogeneous container configurations. The goal is to minimize the cost of container adjustments, and to reduce the resource insufficiency penalty, while maintaining high resource utilization. It is extremely difficult to achieve the minimal cost without knowing the future workloads in advance. Thus, we first propose an optimal dynamic programming algorithm that can scale optimally when given the future workload. This optimal solution is used as the baseline to evaluate other algorithms that do not have the future workload information. Then, we propose two greedy algorithms that do not need workload information in advance, and a heuristic algorithm that first predicts the workload of the next time step using Gradient Boosting Regression, then makes scaling decisions using the optimal dynamic programming algorithm. We evaluate these four algorithms with two realistic workload traces. The experiments show that when the cost to start new servers is much higher than resource insufficiency penalty, our short-term prediction approach will only increase the total cost by only 9.6%, and decrease the utilization by only 10%, when compared with the optimal dynamic programming that knows the future workload.

We consider the partial vertex cover problem with hard capacity constraints (Partial VC-HC) on hypergraphs. In this problem we are given a hypergraph G=(V,E) with a maximum edge size f and a covering requirement R. Each edge is associated with a demand, and each vertex is associated with a capacity and an (integral) available multiplicity. The objective is to compute a minimum vertex multiset such that at least R units of demand from the edges are covered by the capacities of the vertices in the multiset and the multiplicity of each vertex does not exceed its available multiplicity. In this paper we present an f-approximation for this problem, improving over a previous result of (2f+2)(1+epsilon) by Cheung et al to the tight extent possible. Our new ingredient of this work is a generalized analysis on the extreme points of the natural LP, developed from previous works, and a strengthened LP lower-bound obtained for the optimal solutions.

A recent trend in computing platforms is moving from homogeneous multi-core architectures toward heterogeneous and asymmetric multi-core. Therefore, the design of new schedulers for asymmetric multi-core platform has become an important issue. However, most of the existing schedulers focus on how to distinguish workloads suitable for performance "big" cores from those for power-efficient "little" cores, without considering how to distribute jobs to asymmetric cores running at adjustable frequency. In this paper, we propose an energy-efficient scheduler for throughput guaranteed jobs running on asymmetric multi-core platforms. The proposed scheduler not only determines the frequency of cores and job-to-core assignment in order to reduce energy consumption, but also schedules the jobs so that the throughput of all jobs are guaranteed. The simulation results indicate that the proposed scheduler consumes 40% less energy than the existing Global Task Scheduler with DVFS enabled.

Many enterprises or institutes are building private clouds within their own data centers. Data centers may have different batches of physical machines due to annual upgrades, but the number of machines is fixed most of the time. Consequently it is crucial to schedule jobs with different resource requirements and characteristics to meet different job timing constraints, in such heterogeneous yet most of the time static environments. This paper describes a cloud resource management framework that dynamically allocates and reallocates computation resources for jobs that have different requirements, including deadline and priority. This framework makes decisions according to specified policies, and the framework provides four default policies for system administrators to choose to fit their specific needs. The framework is designed to be component-pluggable. The components of the framework can be hot-swapped, i.e., Replaced without shutting down the services. In addition, the framework can work as an individual cloud computing system, or as an extension of an existing cloud system. Our experiment results demonstrate that our system is capable of dynamically adjusting the resource allocation plan according to run-time statistics collected. The system also tolerates hardware failures, and will dynamically reallocate workers to compensate for the downtime in order to finish the jobs before deadline. Our experiments also suggest a trade-off between priority and deadline.

In this paper we describe a scheduling framework that allocates resources to both batch jobs and interactive jobs simultaneously in a private cloud with a static amount of resources. In the system, every job has an individual service level agreement (SLA), and violating the SLA incurs penalty. We propose a model to formally quantify the SLA violation penalty of both batch and interactive jobs. The analysis on the interactive jobs focuses on queuing analysis and response time. The analysis on batch jobs focuses on the non-preemptive job scheduling for multiple processing units. Based on this model we also propose algorithms to estimate the penalty for both batch jobs and interactive jobs, and algorithms that reduce the total SLA violation penalty. Our experiment results suggest that our system effectively reduces the total penalty by allocating the right amount of resources to heterogeneous jobs in a private cloud system.

Energy-efficient task scheduling is a fundamental issue in many application domains, such as energy conservation for mobile devices and the operation of green computing data centers. Modern processors support dynamic voltage and frequency scaling (DVFS) on a per-core basis, i.e., the CPU can adjust the voltage or frequency of each core. As a result, the core in a processor may have different computing power and energy consumption. To conserve energy in multi-core platforms, we propose task scheduling algorithms that leverage per-core DVFS and achieve a balance between performance and energy consumption. We consider two task execution modes: the batch mode, which runs jobs in batches, and the online mode in which jobs with different time constraints, arrival times, and computation workloads co-exist in the system. For tasks executed in the batch mode, we propose an algorithm that finds the optimal scheduling policy, and for the online mode, we present a heuristic algorithm that determines the execution order and processing speed of tasks in an online fashion. The heuristic ensures that the total cost is minimal for every time interval during a task's execution.

Web applications play a major role in various enterprise and cloud services. With the popularity of social networks and with the speed at which information can be disseminate around the globe, online systems need to face ever growing, unpredictable peak load events. Auto-scaling technique provides on-demand resources according to workload in cloud computing system. However, most of the existing solutions are subject to some of the following constraints: (1) replying on user-provided scaling metrics and threshold values, (2) employing the simple Majority Vote scaling algorithm, which is ineffective for scaling Web applications, and (3) lack of capability for predicting workload changes. In this work, we develop an auto-scaling system, WebScale, which is not subject to the aforementioned constraints, for managing resources for Web applications in data centers. We also compare the efficiency of different scaling algorithms for Web applications, and devise a new method for analyzing the trend of workload changes. The experiment results demonstrate that WebScale can keep the response time of Web applications low even when facing sudden load changing.

Power consumption is one of the most critical problems in data centers. One effective way to reduce power consumption is to consolidate the hosting workloads and shut down physical machines which become idle after consolidation. Server consolidation is a NP-hard problem. In this paper, a new algorithms Dynamic Round-Robin (DRR), is proposed for energy-aware virtual machine scheduling and consolidation. We compare this strategy with the GREEDY, ROUNDROBIN and POWERSAVE scheduling strategies implemented in the Eucalyptus Cloud system. Our experiment results show that the Dynamic Round-Robin algorithm reduce a significant amount of power consumption compared with the three strategies in Eucalyptus.

Compiler techniques for program optimizations have been well studied for single-thread programs. With the advance of multi-core architectures, compiler optimizations for multi-threaded parallel programs have started to draw research attention in recent years. Optimizations for multi-threaded parallel programs on multi-core architectures are much more difficult because of the complicated interaction and resource competition between threads. Therefore, identifying the appropriate code segments for performing optimization becomes one of the most challenging issues. In this work, we propose a novel technique to identify the code segments that exhibit unstable performance behavior% because of resource contention between threads, and show that by applying appropriate optimizations to such code segments, the performance of the parallel program can be improved. Our technique is based on a simple and efficient sampling method that analyzes variations in the performance variance of basic blocks to classify basic blocks into "stable" and "unstable" ones. ``Stable'' basic blocks have low average coefficient of variation(CoV) while "unstable" ones have CoV higher than a threshold value. Such analysis results can be used to determine the "unstable" code segments that may benefit from runtime optimizations. Our experiment results on the SPEC OMP2001 benchmark suite demonstrate that the proposed method is effective in finding "unstable" code segments.

The European Space Agency (ESA) released a Call for Proposals for the next Earth Explorer Core Mission in March 2005, with the aim to select the 7thEarth Explorer (EE-7) mission for launch in the next decade. Twenty-four proposals were received and subject to scientific and technical assessment. Six candidate missions were selected and further investigated in the preliminary feasibility studies (Phase 0). A further down-selection was made after the User Consultation Meeting held in Lisbon, Portugal in January 2009. Three candidate missions were selected for further feasibility investigations (phase A). Each of the candidate missions is now being defined in detail through two parallel and competing industrial studies and many complementary science and technology studies, aiming to the final down-selection in 2011/12, followed by the mission implementation with a planned launch in the 2016/17 timeframe.

Abstract Suppose G is a connected graph and T a spanning tree of G. A vertex v ε V(G) is said to be a degree‐preserving vertex if its degree in T is the same as its degree in G. The degree‐preserving spanning tree problem is to find a spanning tree T of a connected graph G such that the number of degree‐preserving vertices is maximized. The purpose of this article is to provide an O(m.α(m,n))‐time algorithm for the degree‐preserving spanning tree problem in strongly chordal graphs, where α is the inverse of Ackermann's function. Furthermore, we present an O(m + n)‐time algorithm in directed path graphs. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

We introduce and study orderly spanning trees of plane graphs. This algorithmic tool generalizes canonical orderings, which exist only for triconnected plane graphs. Although not every plane graph admits an orderly spanning tree, we provide an algorithm to compute an orderly pair for any connected planar graph G, consisting of an embedded planar graph H isomorphic to G, and an orderly spanning tree of H. We also present several applications of orderly spanning trees: (1) a new constructive proof for Schnyder's realizer theorem, (2) the first algorithm for computing an area-optimal 2-visibility drawing of a planar graph, and (3) the most compact known encoding of a planar graph with O(1)-time query support. All algorithms in this paper run in linear time.

Let G be an n-node planar graph. In a visibility representation of G, each node of G is represented by a horizontal line segment such that the line segments representing any two adjacent nodes of G are vertically visible to each other. In the present paper we give the best known compact visibility representation of G. Given a canonical ordering of the triangulated G, our algorithm draws the graph incrementally in a greedy manner. We show that one of three canonical orderings obtained from Schnyder's realizer for the triangulated G yields a visibility representation of G no wider than $\left\lfloor{\frac{22n-40}{15}}\right\rfloor$. Our easy-to-implement O(n)-time algorithm bypasses the complicated subroutines for four-connected components and four-block trees required by the best previously known algorithm of Kant. Our result provides a negative answer to Kant's open question about whether $\left\lfloor{\frac{3n-6}{2}}\right\rfloor$ is a worst-case lower bound on the required width. Also, if G has no degree-three (respectively, degree-five) internal node, then our visibility representation for G is no wider than $\left\lfloor{\frac{4n-9}{3}}\right\rfloor$ (respectively, $\left\lfloor{\frac{4n-7}{3}}\right\rfloor$). Moreover, if G is four-connected, then our visibility representation for G is no wider than n-1, matching the best known result of Kant and He. As a by-product, we give a much simpler proof for a corollary of Wagner's theorem on realizers due to Bonichon, Le Saëc, and Mosbah.