Sharding is a solution to the blockchain scalability problem. A sharded blockchain divides consensus nodes (validators) into groups called shards and processes transactions separately to improve throughput and latency. In this paper, we analyze the rational behavior of users in account/balance model-based sharded blockchains and identify a phenomenon in which accounts (users' wallets and smart contracts) eventually get concentrated in a few shards, making shard loads unfair. This phenomenon leads to bad user experiences, such as delays in transaction inclusions and increased transaction fees. To solve this problem, we propose two load balancing methods in account/balance model-based sharded blockchains. Both methods perform load balancing by periodically reassigning accounts: in the first method, the blockchain protocol itself performs load balancing and in the second method, wallets perform load balancing. We discuss the pros and cons of the two protocols, and apply the protocols to the execution sharding in Ethereum 2.0, an existing sharding design. Further, we analyze by simulation how the protocols behave to confirm that we can observe smaller transaction delays and fees. As a result, we released the simulation program as “Shargri-La,” a simulator designed for general-purpose user behavior analysis on the execution sharding in Ethereum 2.0.

Virtual network embedding has been intensively studied for a decade. The time complexity of most conventional methods has been reduced to the cube of the number of links. Since customers are likely to request a dense virtual network that connects every node pair directly (|E|=O(|V|2)) based on a traffic matrix, the time complexity is actually O(|E|3=|V|6). If we were allowed to reduce this dense network to a sparse one before embedding, the time complexity could be decreased to O(|V|3); the time saving would be of the order of a million times for |V|=100. The network reduction, however, combines several virtual links into a broader link, which makes the embedding cost (solution quality) much worse. This paper analytically and empirically investigates the trade-off between the embedding time and cost for the virtual network reduction. We define two simple reduction operations and analyze them with several interesting theorems. The analysis indicates that an exponential drop in embedding time can be achieved with a linear increase in embedding cost. A rigorous numerical evaluation justifies the desirability of the trade-off.

Inspired by the efficient proof procedures discussed in Computability logic [3],[5],[6], we describe a heuristic proof procedure for first-order logic. This is a variant of Gentzen sequent system [2] and has the following features: (a) it views sequents as games between the machine and the environment, and (b) it views proofs as a winning strategy of the machine. From this game-based viewpoint, a poweful heuristic can be extracted and a fair degree of determinism in proof search can be obtained. This article proposes a new deductive system LKg with respect to first-order logic and proves its soundness and completeness.

This paper proposes a novel multiple chaos embedded gravitational search algorithm (MCGSA) that simultaneously utilizes multiple different chaotic maps with a manner of local search. The embedded chaotic local search can exploit a small region to refine solutions obtained by the canonical gravitational search algorithm (GSA) due to its inherent local exploitation ability. Meanwhile it also has a chance to explore a huge search space by taking advantages of the ergodicity of chaos. To fully utilize the dynamic properties of chaos, we propose three kinds of embedding strategies. The multiple chaotic maps are randomly, parallelly, or memory-selectively incorporated into GSA, respectively. To evaluate the effectiveness and efficiency of the proposed MCGSA, we compare it with GSA and twelve variants of chaotic GSA which use only a certain chaotic map on a set of 48 benchmark optimization functions. Experimental results show that MCGSA performs better than its competitors in terms of convergence speed and solution accuracy. In addition, statistical analysis based on Friedman test indicates that the parallelly embedding strategy is the most effective for improving the performance of GSA.

In Recent years, a paradigm of optimization algorithms referred to as “meta-heuristics” have been gaining attention as a means of obtaining approximate solutions to optimization problems quickly without any special prior knowledge of the problems. Meta-heuristics are characterized by flexibility in implementation. In practical applications, we can make use of not only existing algorithms but also revised algorithms that reflect the prior knowledge of the problems. Most meta-heuristic algorithms lack mathematical grounds, however, and therefore generally require a process of trial and error for the algorithm design and its parameter adjustment. For one of the resolution of the problem, we propose an approach to design algorithms with mathematical grounds. The approach consists of first constructing a “framework” of which dynamic characteristics can be derived theoretically and then designing concrete algorithms within the framework. In this paper, we propose such a framework that employs two following basic strategies commonly used in existing meta-heuristic algorithms, namely, (1) multipoint searching, and (2) stochastic searching with pseudo-random numbers. In the framework, the update-formula of search point positions is given by a linear combination of normally distributed random numbers and a fixed input term. We also present a stability theory of the search point distribution for the proposed framework, using the variance of the search point positions as the index of stability. This theory can be applied to any algorithm that is designed within the proposed framework, and the results can be used to obtain a control rule for the search point distribution of each algorithm. We also verify the stability theory and the optimization capability of an algorithm based on the proposed framework by numerical simulation.

This paper proposes a technique for detecting the occurrences of refactoring from source code revisions. In a real software development process, a refactoring operation may sometimes be performed together with other modifications at the same revision. This means that detecting refactorings from the differences between two versions stored in a software version archive is not usually an easy process. In order to detect these impure refactorings, we model the detection within a graph search. Our technique considers a version of a program as a state and a refactoring as a transition between two states. It then searches for the path that approaches from the initial to the final state. To improve the efficiency of the search, we use the source code differences between the current and the final state for choosing the candidates of refactoring to be applied next and estimating the heuristic distance to the final state. Through case studies, we show that our approach is feasible to detect combinations of refactorings.

This paper treats meta-heuristics for combinatorial optimization problems. The parallelization of meta-heuristics is then discussed in which we show that parallel processing has possibility of not only speeding up but also improving solution quality. Finally we extend the discussion of the combinatorial optimization into autonomous decentralized systems, say autonomous decentralized optimization. This notion becomes very important with the advancement of the network-connected system architecture.

The optimization of channel assignment in cellular mobile networks is an NP-complete combinatorial optimization problem. For any reasonable size network, only sub-optimal solutions can be obtained by heuristic algorithms. In this paper, six channel assignment heuristic algorithms are proposed and evaluated. They are the combinations of three channel assignment strategies and two cell ordering methods. What we found are (i) the node-color ordering of cells is a more efficient ordering method than the node-degree ordering; (ii) the frequency exhaustive strategy is more suitable for systems with highly non-uniformly distributed traffic, and the requirement exhaustive strategy is more suitable for systems with less non-uniformly distributed traffic; and (iii) the combined frequency and requirement exhaustive strategy with node-color re-ordering is the most efficient algorithm. The frequency spans obtained using the proposed algorithms are much lower than that reported in the literature, and in many cases are equal to the theoretical lower bounds.

The main problem considered is submodular set cover, the problem of minimizing a linear function under a nondecreasing submodular constraint, which generalizes both well-known set cover and minimum matroid base problems. The problem is NP-hard, and two natural greedy heuristics are introduced along with analysis of their performance. As applications of these heuristics we consider various special cases of submodular set cover, including partial cover variants of set cover and vertex cover, and node-deletion problems for hereditary and matroidal properties. An approximation bound derived for each of them is either matching or generalizing the best existing bounds.

The vehicle routing and facility location fields are well-developed areas in management science and operations research application. There is an increasing recognition that effective decision-making in these fields requires the adoption of optimization software that can be embedded into a decision support system. In this paper, we describe the implementation details of our software components for solving the vehicle routing and facility location problems.

Reducing communication overhead is a key goal of program optimization for current scalable multiprocessors. A well-known approach to achieving this is to map tasks (indivisible units of computation) to processors so that communication and computation overlap as much as possible. In an earlier work, we developed a look-ahead scheduling heuristic for efficiently reducing communication overhead with the aim of decreasing the completion time of a given parallel program. In this paper, we report on an extension of the algorithm, which fills in the idle time slots created by interprocessor communication without increasing the algorithm's time complexity. The results of experiments emphasize the importance of optimally filling idle time slots in processors.

The classical max-min policy has been suggested by the ATM Forum to support the available bit rate (ABR) service class. However, there are several drawbacks in adopting the max-min rate allocation policy. In particular, the max-min policy is not able to support the minimum cell rate (MCR) requirement and the peak cell rate (PCR) constraint for each ABR connection. Furthermore, the max-min policy does not offer flexible options for network providers wishing to establish a usage-based pricing criterion. In this paper, we present a generic weight-based rate allocation policy, which generalizes the classical max-min policy by supporting the MCR/PCR for each connection. Our rate allocation policy offers a flexible usage-based pricing strategy to network providers. A centralized algorithm is presented to compute network-wide bandwidth allocation to achieve this policy. Furthermore, a simple switch algorithm using ABR flow control protocol is developed with the aim of achieving our rate allocation policy in a distributed networking environment. The effectiveness of our distributed algorithm in a local area environment is substantiated by simulation results based on the benchmark network configurations suggested by the ATM Forum.

This paper describes a new approach to the scheduling problem that assigns tasks of a parallel program described as a task graph onto parallel machines. The approach handles interprocessor communication and heterogeneity, based on using both the theoretical results developed so far and a lookahead scheduling strategy. The experimental results on randomly generated task graphs demonstrate the effectiveness of this scheduling heuristic.

Genetic algorithms have been shown to be very useful in a variety of search and optimization problems. In this paper, we propose a modified genetic channel router. We adopt the compatible crossover operator and newly designed compatible mutation operator in order to search solution space more effectively, where vertical constraints are integrated. By carefully selected fitness function forms and optimized genetic parameters, the current version speeds up benchmarks on average about 5.83 times faster than that of our previous version. Moreover the total convergence to optimal solutions for benchmarks can be always obtained.

Genetic algorithms have been shown to be very useful in a variety of search and optimization problems. In this paper, we describe the implementation of genetic algorithms for channel routing problems and identify the key points which are essential to making full use of the population of potential solutions, that is one of the characteristics of genetic algorithms. Three efficient crossover techniques which can be divided further into 13 kinds of crossover operators have been compared. We also extend our previous work with ability to deal with dogleg case by simply splitting multi-terminal nets into a series of 2-terminal subnets. It routes the Deutsch's difficult example with 21 tracks without any detours.

Evolution programs have been shown to be very useful in a variety of search and optimization problems, however, until now, there has been little attempt to apply evolution programs to channel routing problem. In this paper, we present an exolution program and identify the key points which are essential to successfully applying evolution programs to channel routing problem. We also indicate how integrating heuristic information related to the problem under consideration helps in convergence on final solutions and illustrate the validity of out approach by providing experimental results obtained for the benchmark tests. compared with the optimal solutions.

We propose a continuous speech recognition algorithm utilizing island-driven A* search. Conventional left-to-right A* search is probable to lose the optimal solution from a finite stack if some obscurities appear at the start of an input speech. Proposed island-driven A* search proceeds searching forward and backward from the clearest part of an input speech, and thus can avoid to lose the optimal solution from a finite stack.