Biblio

Distributed optimization algorithms are proposed to, potentially, reduce the computational time of large-scale optimization problems, such as security-constrained economic dispatch (SCED). While various geographical decomposition strategies have been presented in the literature, we proposed a temporal decomposition strategy to divide the SCED problem over the considered scheduling horizon. The proposed algorithm breaks SCED over the scheduling time and takes advantage of parallel computing using multi-core machines. In this paper, we investigate how to partition the overall time horizon. We study the effect of the number of partitions (i.e., SCED subproblems) on the overall performance of the distributed coordination algorithm and the effect of partitioning time interval on the optimal solution. In addition, the impact of system loading condition and ramp limits of the generating units on the number of iterations and solution time are analyzed. The results show that by increasing the number of subproblems, the computational burden of each subproblem is reduced, but more shared variables and constraints need to be modeled between the subproblems. This can result in increasing the total number of iterations and consequently the solution time. Moreover, since the load behavior affects the active ramping between the subproblems, the breaking hour determines the difference between shared variables. Hence, the optimal number of subproblems is problem dependent. A 3-bus and the IEEE 118-bus system are selected to analyze the effect of the number of partitions.

Partitioning security components of IoT devices to enable the use of Trusted Execution Environments adds resilience against side-channel attacks. Devices are hardened against extraction of sensitive information, but at the same time additional effort must be spent for the integration of the TEE and software partitioning. To perform partitioning, the developer typically inserts Remote Procedure Calls into the software. Existing RPC-based solutions require the developer to write Interface Definition Language files to generate RPC stubs. In this work, we present an RPC-based framework that supports software partitioning via a graphical user interface. The framework extracts required information about the interfaces from source-code header files to eliminate the need for IDL files. With this approach the TEE integration time is reduced and reuse of existing libraries is supported. We evaluate a Proof-of-Concept by partitioning a TLS library for IoT devices and compare our approach to other RPC-based solutions.

Bitcoin is the leading example of a blockchain application that facilitates peer-to-peer transactions without the need for a trusted intermediary. This paper considers possible attacks related to the decentralized network architecture of Bitcoin. We perform a data driven study of Bitcoin and present possible attacks based on spatial and temporal characteristics of its network. Towards that, we revisit the prior work, dedicated to the study of centralization of Bitcoin nodes over the Internet, through a fine-grained analysis of network distribution, and highlight the increasing centralization of the Bitcoin network over time. As a result, we show that Bitcoin is vulnerable to spatial, temporal, spatio-temporal, and logical partitioning attacks with an increased attack feasibility due to network dynamics. We verify our observations by simulating attack scenarios and the implications of each attack on the Bitcoin . We conclude with suggested countermeasures.

Packet classification is a core function in network and security systems; hence, hardware-based solutions, such as packet classification accelerator chips or Ternary Content Addressable Memory (T-CAM), have been widely adopted for high-performance systems. With the rapid improvement of general hardware architectures and growing popularity of multi-core multi-threaded processors, software-based packet classification algorithms are attracting considerable attention, owing to their high flexibility in satisfying various industrial requirements for security and network systems. For high classification speed, these algorithms internally use large tables, whose size increases exponentially with the ruleset size; consequently, they cannot be used with a large rulesets. To overcome this problem, we propose a new software-based packet classification algorithm that simultaneously supports high scalability and fast classification performance by merging partition decision trees in a search table. While most partitioning-based packet classification algorithms show good scalability at the cost of low classification speed, our algorithm shows very high classification speed, irrespective of the number of rules, with small tables and short table building time. Our test results confirm that the proposed algorithm enables network and security systems to support heavy traffic in the most effective manner.

Balanced partitioning is often a crucial first step in solving large-scale graph optimization problems: in some cases, a big graph is chopped into pieces that fit on one machine to be processed independently before stitching the results together, leading to certain suboptimality from the interaction among different pieces. In other cases, links between different parts may show up in the running time and/or network communications cost, hence the desire to have small cut size. We study a distributed balanced partitioning problem where the goal is to partition the vertices of a given graph into k pieces, minimizing the total cut size. Our algorithm is composed of a few steps that are easily implementable in distributed computation frameworks, e.g., MapReduce. The algorithm first embeds nodes of the graph onto a line, and then processes nodes in a distributed manner guided by the linear embedding order. We examine various ways to find the first embedding, e.g., via a hierarchical clustering or Hilbert curves. Then we apply four different techniques such as local swaps, minimum cuts on partition boundaries, as well as contraction and dynamic programming. Our empirical study compares the above techniques with each other, and to previous work in distributed algorithms, e.g., a label propagation method, FENNEL and Spinner. We report our results both on a private map graph and several public social networks, and show that our results beat previous distributed algorithms: we notice, e.g., 15-25% reduction in cut size over [UB13]. We also observe that our algorithms allow for scalable distributed implementation for any number of partitions. Finally, we apply our techniques for the Google Maps Driving Directions to minimize the number of multi-shard queries with the goal of saving in CPU usage. During live experiments, we observe an ≈ 40% drop in the number of multi-shard queries when comparing our method with a standard geography-based method.