In this paper, we consider a uniform bipartition problem in a population protocol model. The goal of the uniform bipartition problem is to divide a population into two groups of the same size. We study the problem under global fairness with various assumptions: 1) a population with or without a base station, 2) symmetric or asymmetric protocols, and 3) designated or arbitrary initial states. As a result, we completely clarify solvability of the uniform bipartition problem under global fairness and, if solvable, show the tight upper and lower bounds on the number of states.

This paper introduces e-spill, an eager spill mechanism, which dynamically finds the optimal spill-threshold by monitoring the GC time at runtime and thereby prevent expensive GC overhead. Our e-spill adopts a slow-start model to gradually increase the spill-threshold until it reaches the optimal point without substantial GCs. We prototype e-spill as an extension to Spark and evaluate it using six workloads on three different parallel platforms. Our evaluations show that e-spill improves performance by up to 3.80× and saves the cost of cluster operation on Amazon EC2 cloud by up to 51% over the baseline system following Spark Tuning Guidelines.

Nowadays the computing technology is going through a major paradigm shift. Local processing platforms are being replaced by physically out of reach yet more powerful and scalable environments such as the cloud computing platforms. Previously, we introduced the OJIT system as a novel approach for obfuscating remotely executed programs, making them difficult for adversaries to reverse-engineer. The system exploited the JIT compilation technology to randomly and dynamically transform the code, making it constantly changing, thereby complicating the execution state. This work aims to propose the new design iOJIT, as an enhanced approach that patches the old systems shortcomings, and potentially provides more effective obfuscation. Here, we present an analytic study of the obfuscation techniques on the generated code and the cost of applying such transformations in terms of execution time and performance overhead. Based upon this profiling study, we implemented a new algorithm to choose which obfuscation techniques would be better chosen for “efficient” obfuscation according to our metrics, i.e., less prone to security attacks. Another goal was to study the system performance with different applications. Therefore, we applied our system on a cloud platform running different standard benchmarks from SPEC suite.

Many applications, such as image signal processing, has an inherent tolerance for insignificant inaccuracies. Multiplication is a key arithmetic function for many applications. Approximate multipliers are considered an efficient technique to trade off energy relative to performance and accuracy for the error-tolerant applications. Here, we design and analyze four approximate multipliers that demonstrate lower power consumption and shorter critical path delay than the conventional multiplier. They employ an approximate tree compressor that halves the height of the partial product tree and generates a vector to compensate accuracy. Compared with the conventional Wallace tree multiplier, one of the evaluated 8-bit approximate multipliers reduces power consumption and critical path delay by 36.9% and 38.9%, respectively. With a 0.25% normalized mean error distance, the silicon area required to implement the multiplier is reduced by 50.3%. Our multipliers outperform the previously proposed approximate multipliers relative to power consumption, critical path delay, and design area. Results from two image processing applications also demonstrate that the qualities of the images processed by our multipliers are sufficiently accurate for such error-tolerant applications.

We investigate enumeration of distinct flat-foldable crease patterns under the following assumptions: positive integer n is given; every pattern is composed of n lines incident to the center of a sheet of paper; every angle between adjacent lines is equal to 2π/n; every line is assigned one of “mountain,” “valley,” and “flat (or consequently unfolded)”; crease patterns are considered to be equivalent if they are equal up to rotation and reflection. In this natural problem, we can use two well-known theorems for flat-foldability: the Kawasaki Theorem and the Maekawa Theorem in computational origami. Unfortunately, however, they are not enough to characterize all flat-foldable crease patterns. Therefore, so far, we have to enumerate and check flat-foldability one by one using computer. In this study, we develop the first algorithm for the above stated problem by combining these results in a nontrivial way and show its analysis of efficiency.

This paper presents a novel delta-sigma modulator that uses a switched-capacitor (SC) integrator with the structure of a finite impulse response (FIR) filter in a loop filter configuration. The delta-sigma analog-to-digital converter (ΔΣADC) is used in various conversion systems to enable low-power, high-accuracy conversion using oversampling and noise shaping. Increasing the gain coefficient of the integrator in the loop filter configuration of the ΔΣADC suppresses the quantization noise that occurs in the signal band. However, there is a trade-off relationship between the integrator gain coefficient and system stability. The SC integrator, which contains an FIR filter, can suppress quantization noise in the signal band without requiring an additional operational amplifier. Additionally, it can realize a higher signal-to-quantization noise ratio. In addition, the poles that are added by the FIR filter structure can improve the system's stability. It is also possible to improve the flexibility of the pole placement in the system. Therefore, a noise transfer function that does not contain a large gain peak is realized. This results in a stable system operation. This paper presents the essential design aspects of a ΔΣADC with an FIR filter. Two types of simulation results are examined for the proposed first- and second-order, and these results confirm the effectiveness of the proposed architecture.

This paper deals with the minimum and maximum value distributions based on the n-variate FGM copula with one dependence parameter. The ranges of dependence parameters are theoretically determined so that the probability density function always takes a non-negative value. However, the closed-form conditions of the ranges for the dependence parameters have not been known in the literature. In this paper, we newly provide the necessary conditions of the ranges of the dependence parameters for the minimum and maximum value distributions which are derived from FGM copula, and show the asymptotic properties of the ranges.

Data generated from the Internet of Things (IoT) devices in smart spaces are utilized in a variety of fields such as context recognition, service recommendation, and anomaly detection. However, the missing values in the data streams of the IoT devices remain a challenging problem owing to various missing patterns and heterogeneous data types from many different data streams. In this regard, while we were analyzing the dataset collected from a smart space with multiple IoT devices, we found a continuous missing pattern that is quite different from the existing missing-value patterns. The pattern has blocks of consecutive missing values over a few seconds and up to a few hours. Therefore, the pattern is a vital factor to the availability and reliability of IoT applications; yet, it cannot be solved by the existing missing-value imputation methods. Therefore, a novel approach for missing-value imputation of the continuous missing pattern is required. We deliberate that even if the missing values of the continuous missing pattern occur in one data stream, missing-values imputation is possible through learning other data streams correlated with this data stream. To solve the missing values of the continuous missing pattern problem, we analyzed multiple IoT data streams in a smart space and figured out the correlations between them that are the interdependencies among the data streams of the IoT devices in a smart space. To impute missing values of the continuous missing pattern, we propose a deep learning-based missing-value imputation model exploiting correlation information, namely, the deep imputation network (DeepIN), in a smart space. The DeepIN uses that multiple long short-term memories are constructed according to the correlation information of each IoT data stream. We evaluated the DeepIN on a real dataset from our campus IoT testbed, and the experimental results show that our proposed approach improves the imputation performance by 57.36% over the state-of-the-art missing-value imputation algorithm. Thus, our approach can be a promising methodology that enables IoT applications and services with a reasonable missing-value imputation accuracy (80∼85%) on average, even if a long-term block of values is missing in IoT environments.

In parallel computing systems, the interconnection network forms the critical infrastructure which enables robust and scalable communication between hundreds of thousands of nodes. The traditional packet-switched network tends to suffer from long communication time when network congestion occurs. In this context, we explore the use of circuit switching (CS) to replace packet switches with custom hardware that supports circuit-based switching efficiently with low latency. In our target CS network, a certain amount of bandwidth is guaranteed for each communication pair so that the network latency can be predictable when a limited number of node pairs exchange messages. The number of allocated time slots in every switch is a direct factor to affect the end-to-end latency, we thereby improve the slot utilization and develop a network topology generator to minimize the number of time slots optimized to target applications whose communication patterns are predictable. By a quantitative discrete-event simulation, we illustrate that the minimum necessary number of slots can be reduced to a small number in a generated topology by our design methodology while maintaining network cost 50% less than that in standard tori topologies.

In this study, we propose a statistical reputation approach for constructing a reliable packet route in ad-hoc sensor networks. The proposed method uses reputation as a measurement for router node selection through which a reliable data route is constructed for packet delivery. To refine the reputation, a transaction density is defined here to showcase the influence of node transaction frequency over the reputation. And to balance the energy consumption and avoid choosing repetitively the same node with high reputation, node remaining energy is also considered as a reputation factor in the selection process. Further, a shortest-path-tree routing protocol is designed so that data packets can reach the base station through the minimum intermediate nodes. Simulation tests illustrate the improvements in the packet delivery ratio and the energy utilization.

This paper proposes a new design criterion of adaptively scaled belief (ASB) in Gaussian belief propagation (GaBP) for large multi-user multi-input multi-output (MU-MIMO) detection. In practical MU detection (MUD) scenarios, the most vital issue for improving the convergence property of GaBP iterative detection is how to deal with belief outliers in each iteration. Such outliers are caused by modeling errors due to the fact that the law of large number does not work well when it is difficult to satisfy the large system limit. One of the simplest ways to mitigate the harmful impact of outliers is belief scaling. A typical approach for determining the scaling parameter for the belief is to create a look-up table (LUT) based on the received signal-to-noise ratio (SNR) through computer simulations. However, the instantaneous SNR differs among beliefs because the MIMO channels in the MUD problem are random; hence, the creation of LUT is infeasible. To stabilize the dynamics of the random MIMO channels, we propose a new transmission block based criterion that adapts belief scaling to the instantaneous channel state. Finally, we verify the validity of ASB in terms of the suppression of the bit error rate (BER) floor.

This paper investigates energy-efficient resource allocation problem for the wireless power transfer (WPT) enabled multi-user massive multiple-input multiple-output (MIMO) systems. In the considered systems, the sensor nodes (SNs) are firstly powered by WPT from the power beacon (PB) with a large scale of antennas. Then, the SNs use the harvested energy to transmit the data to the base station (BS) with multiple antennas. The problem of optimizing the energy efficiency objective is formulated with the consideration of maximum transmission power of the PB and the quality of service (QoS) of the SNs. By adopting fractional programming, the energy-efficient optimization problem is firstly converted into a subtractive form. Then, a joint power and time allocation algorithm based on the block coordinate descent and Dinkelbach method is proposed to maximize energy efficiency. Finally, simulation results show the proposed algorithm achieves a good compromise between the spectrum efficiency and total power consumption.

Brain-computer interfaces (BCIs) have been used by users to convey their intentions directly with brain signals. For example, a spelling system that uses EEGs allows letters on a display to be selected. In comparison, previous studies have investigated decoding speech information such as syllables, words from single-trial brain signals during speech comprehension, or articulatory imagination. Such decoding realizes speech recognition with a relatively short time-lag and without relying on a display. Previous magnetoencephalogram (MEG) research showed that a template matching method could be used to classify three English sentences by using phase patterns in theta oscillations. This method is based on the synchronization between speech rhythms and neural oscillations during speech processing, that is, theta oscillations synchronized with syllabic rhythms and low-gamma oscillations with phonemic rhythms. The present study aimed to approximate this classification method to a BCI application. To this end, (1) we investigated the performance of the EEG-based classification of three Japanese sentences and (2) evaluated the generalizability of our models to other different users. For the purpose of improving accuracy, (3) we investigated the performances of four classifiers: template matching (baseline), logistic regression, support vector machine, and random forest. In addition, (4) we propose using novel features including phase patterns in a higher frequency range. Our proposed features were constructed in order to capture synchronization in a low-gamma band, that is, (i) phases in EEG oscillations in the range of 2-50 Hz from all electrodes used for measuring EEG data (all) and (ii) phases selected on the basis of feature importance (selected). The classification results showed that, except for random forest, most classifiers perform similarly. Our proposed features improved the classification accuracy with statistical significance compared with a baseline feature, which is a phase pattern in neural oscillations in the range of 4-8 Hz from the right hemisphere. The best mean accuracy across folds was 55.9% using template matching trained by all features. We concluded that the use of phase information in a higher frequency band improves the performance of EEG-based sentence classification and that this model is applicable to other different users.

The Game of Life, a two-dimensional computationally universal cellular automaton, is known to exhibits 1/f noise in the evolutions starting from random configurations. In this paper we perform the spectral analysis on the computation process by a Turing machine constructed on the array of the Game of Life. As a result, the power spectrum averaged over the whole array has almost flat line at low frequencies and a lot of sharp peaks at high frequencies although some regions in which complicated behavior such as frequent memory rewriting occurs exhibit 1/f noise. This singular power spectrum is, however, easily turned into 1/f by slightly deforming the initial configuration of the Turing machine. These results emphasize the peculiarity of the computation process on the Game of Life that is never shared with the evolutions from random configurations. The Lyapunov exponents have positive values in three out of six trials and zero or negative values in other three trails. That means the computation process is essentially chaotic but it has capable of recovering a slight error in the configuration of the Turing machine.

Two points x, y inside a simple polygon P are said to be mutually link-2 visible if there exists the third point z ∈ P such that z is visible from both x and y. The polygon P is link-2 LR-visible if there are two points s, t on the boundary of P such that every point on the clockwise boundary of P from s to t is link-2 visible from some point of the other boundary of P from t to s and vice versa. We give a characterization of link-2 LR-visibility polygons by generalizing the known result on LR-visibility polygons. A new idea is to extend the concepts of ray-shootings and components to those under notion of link-2 visibility. Then, we develop an O(n log n) time algorithm to determine whether a given polygon is link-2 LR-visible. Using the characterization of link-2 LR-visibility polygons, we further present an O(n log n) time algorithm for determining whether a polygonal region is searchable by a k-searcher, k ≥ 2. This improves upon the previous O(n2) time bound [9]. A polygonal region P is said to be searchable by a searcher if the searcher can detect (or see) an unpredictable intruder inside the region, no matter how fast the intruder moves. A k-searcher holds k flashlights and can see only along the rays of the flashlights emanating from his position.

State-of-the-art parallel systems employ a huge number of computing nodes that are connected by an interconnection network. An interconnection network (ICN) plays an important role in a parallel system, since it is responsible to communication capability. In general, an ICN shows non-linear phenomena in its communication performance, most of them are caused by congestion. Thus, designing a large-scale parallel system requires sufficient discussions through repetitive simulation runs. This causes another problem in simulating large-scale systems within a reasonable cost. This paper shows a promising solution by introducing the cellular automata concept, which is originated in our prior work. Assuming 2D-torus topologies for simplification of discussion, this paper discusses fundamental design of router functions in terms of cellular automata, data structure of packets, alternative modeling of a router function, and miscellaneous optimization. The proposed models have a good affinity to GPGPU technology and, as representative speed-up results, the GPU-based simulator accelerates simulation upto about 1264 times from sequential execution on a single CPU. Furthermore, since the proposed models are applicable in the shared memory model, multithread implementation of the proposed methods achieve about 162 times speed-ups at the maximum.

We propose new key recovery attacks on the two-round single-key n-bit Even-Mansour ciphers (2SEM) that are secure up to 22n/3 queries against distinguishing attacks proved by Chen et al. Our attacks are based on the meet-in-the-middle technique which can significantly reduce the data complexity. In particular, we introduce novel matching techniques which enable us to compute one of the two permutations without knowing a part of the key information. Moreover, we present two improvements of the proposed attack: one significantly reduces the data complexity and the other reduces the time complexity. Compared with the previously known attacks, our attack first breaks the birthday barrier on the data complexity although it requires chosen plaintexts. When the block size is 64 bits, our attack reduces the required data from 245 known plaintexts to 226 chosen plaintexts with keeping the time complexity required by the previous attacks. Furthermore, by increasing the time complexity up to 262, the required data is further reduced to 28, and DT=270, where DT is the product of data and time complexities. We show that our data-optimized attack requires DT=2n+6 in general cases. Since the proved lower bound on DT for the single-key one-round n-bit Even-Mansour ciphers is 2n, our results imply that adding one round to one-round constructions does not sufficiently improve the security against key recovery attacks. Finally, we propose a time-optimized attacks on 2SEM in which, we aim to minimize the number of the invocations of internal permutations.

Fail-Stop Signature (FSS) scheme is a signature scheme which satisfies unforgeability even against a forger with super-polynomial computational power (i.e. even against a forger who can compute acceptable signatures) and non-repudiability against a malicious signer with probabilistic polynomial time computational power (i.e. a PPT malicious signer). In this paper, under some settings, the equivalence relation has been derived between a set of security properties when single FSS scheme is used singly and a security property called Universally Composable (UC) security when plural FSS schemes are concurrently used. Here, UC security is a security property guaranteeing that even when plural schemes are concurrently used, security properties of each scheme (for single scheme usage) are preserved. The above main settings are as follows. Firstly, H-EUC (Externalized UC) security is introduced instead of “conventional” UC security, where a new helper functionality H is constructed appropriately. It is because that we can derive “conventional” UC security cannot hold for FSS schemes when malicious parties (e.g. a forger and a malicious signer) have super-polynomial computational power. In the environment where the above helper functionality H is used, all parties are PPT, but only a forger may compute acceptable signatures by obtaining some additional information from H. Secondly, the definition of unforgeability (in a set of security properties for single FSS scheme usage) is revised to match the above environment. The above equivalence relation derived under the above settings guarantees that even when plural FSS schemes are concurrently used, those security properties for single scheme usage are preserved, provided that some conditions hold. In particular, the equivalence relation in this paper has originality in terms of guaranteeing that unforgeability is preserved even against a forger who is PPT but may compute acceptable signatures. Furthermore, it has been firstly proved in this paper that H-EUC security holds for an existing instantiation of an FSS scheme by Mashatan et al. From this, it can be said that the equivalence relation shown in this paper is practical.

In this paper, we propose a new asymptotically stabilizing control law for a four-wheeled vehicle with a steering limitation. We adopt a locally semiconcave control Lyapunov function (LS-CLF) for the system. To overcome the nonconvexity of the input-constraint set, we utilize a saturation function and a signum function in the control law. The signum function makes the vehicle velocity nonzero except at the origin so that the angular velocity can be manipulated within the input constraint. However, the signum function may cause a chattering phenomenon at certain points of the state far from the origin. Thus, we integrate a lazy-switching mechanism for the vehicle velocity into the control law. The mechanism makes a sign of the vehicle velocity maintain, and the new control input also decreases the value of the LS-CLF. We confirm the effectiveness of our method by a computer simulation and experiments.

A compression-function-based MAC function called FMAC was presented as well as a vector-input PRF called vFMAC in 2016. They were proven to be secure PRFs on the assumption that their compression function is a secure PRF against related-key attacks with respect to their non-cryptographic permutations in the single user setting. In this paper, it is shown that both FMAC and vFMAC are also secure PRFs in the multi-user setting on the same assumption as in the single user setting. These results imply that their security in the multi-user setting does not degrade with the number of the users and is as good as in the single user setting.