A distributed constraint optimization problem (DCOP) is a framework to model multi-agent coordination problems. Asynchronous distributed optimization (ADOPT) is a well-known complete DCOP algorithm, and many of its variants have been proposed over the last decade. It is considered proven that ADOPT-based algorithms have the key properties of termination and optimality, which guarantee that the algorithms terminate in a finite time and obtain an optimal solution, respectively. In this paper, we present counterexamples to the termination and optimality of ADOPT-based algorithms. They are classified into three types, at least one of which exists in each of ADOPT and eight of its variants that we analyzed. In other words, the algorithms may potentially not terminate or terminate with a suboptimal solution. Furthermore, we show that the bounded-error approximation of ADOPT, which enables the algorithm to terminate faster with the quality of the solution guaranteed within a predefined error bound, also suffers from flaws. Additionally, we propose an amended version of ADOPT that avoids the flaws in existing algorithms and prove that it has the properties of termination and optimality.

A distributed constraint optimization problem (DCOP) is a framework to model multi-agent coordination problems. Asynchronous distributed optimization (ADOPT) is a well-known complete DCOP algorithm, and owing to its superior characteristics, many variants have been proposed over the last decade. It is considered proven that ADOPT-based algorithms have the key properties of termination and optimality, which guarantee that the algorithms terminate in a finite time and obtain an optimal solution, respectively. In this paper, we present counterexamples to the termination and optimality of ADOPT-based algorithms. The flaws are classified into three types, at least one of which exists in each of ADOPT and seven of its variants that we analyzed. In other words, the algorithms may potentially not terminate or terminate with a suboptimal solution. We also propose an amended version of ADOPT that avoids the flaws in existing algorithms and prove that it has the properties of termination and optimality.

Popular data concentration is a widely accepted storage energy-saving technique which places frequently-accessed data on a small subset of hard disks and spins-down other infrequently-accessed disks. Many previous studies use intuitive heuristic algorithms for data placement that promote the imbalance in the access frequencies across hard disks. However, the relevance and the optimality of such file placements have not been rigorously investigated. In this paper, we formally define the energy-saving file placement problem under the capacity and performance constraints as a combinatorial optimization problem and show the theory of the optimal file placement where the file access rates in the next period are given. Our analysis based on a stochastic process of disk state transitions gives the theoretical support for the common heuristic placement method. To examine the effectiveness of the optimal file placement, we experimentally evaluate the energy-efficiency of a test storage system using the file access rates generated from the real access traces from Flickr. The experimental results show that the energy consumption can be reduced by 31.8 percent with the optimal file placement compared to the evenly distributed file placement. We also conduct simulation experiments to confirm the energy-saving impacts in larger-scale storage systems.

In the research of agents playing computer games, attempts have been made to create agents with particular playstyles. A typical approach adopted in previous studies is to define the reward functions so that the agent has the desired playstyle. However, based on this approach, it is difficult to identify other playstyles that have not been specified in advance. The purpose of this paper is to create agents with playstyles by combining a genetic algorithm called NeuroEvolution of Augmenting Topologies (NEAT) and clustering based on the logs of gameplay by agents. Here, individuals of NEAT are classified in some species by clustering according to the play log and crossed with the same species. We evaluated our method by an experiment with a roguelike game and observed that multiple playstyles were identified. Furthermore, by comparing the proposed method with the method using only NEAT, it was shown that the bias in the number of individuals among playstyles can be suppressed.

A number of attempts have been made to solve imperfect information games using reinforcement learning. Since it is not easy to apply reinforcement learning directly to imperfect information games, methods, such as Neural Fictitious Self-Play (NFSP), have been proposed. In this study, we investigate an alternative method to solve imperfect information games using reinforcement learning. The basic idea is to learn from self-playing the perfect information games where the hidden information in the original game is revealed. Based on the policy obtained from this learning, the current state of the game is estimated from the opponent's moves and the own best move. We applied the proposed method to an imperfect information game called Geister and evaluated its effectiveness through experiments. As a result, we obtained that the winning rate was higher than that of the direct learning of imperfect information games using reinforcement learning.

We present an optimistic primary-backup (so-called passive replication) mechanism for highly available Internet services on intercloud platforms. Our proposed method aims at providing Internet services despite the occurrence of a large-scale disaster. To this end, each service in our method creates replicas in different data centers and coordinates them with an optimistic consensus algorithm instead of a majority-based consensus algorithm such as Paxos. Although our method allows temporary inconsistencies among replicas, it eventually converges on the desired state without an interruption in services. In particular, the method tolerates simultaneous failure of the majority of nodes and a partitioning of the network. Moreover, through interservice communications, members of the service groups are autonomously reorganized according to the type of failure and changes in system load. This enables both load balancing and power savings, as well as provisioning for the next disaster. We demonstrate the service availability provided by our approach for simulated failure patterns and its adaptation to changes in workload for load balancing and power savings by experiments with a prototype implementation.

We present a game-theoretic approach for power reduction in large-scale distributed storage systems. The key idea is to use distributed hash tables to dynamically migrate virtual nodes, thus skewing the workload towards a subset of physical disks without overloading them. To realize this idea in an autonomous way (i.e., without any kind of central controller), virtual nodes are considered to be selfish agents playing a game in which each node receives a payoff according to the workload of the disk on which it currently resides. We model this setting as a potential game, where an increase in the payoff to a virtual node reduces the power of the system. This game consists of a pair of global and private utility functions, derived by means of the Wonderful Life Utility technique. The former function evaluates the state of the system, and the latter provides criteria for the migration of each node. The performance of our method is measured by simulations and a prototype implementation. From these evaluations, we find that our method reduces the running time of the disks in active mode by 12.7-18.7%, with an overall average response time of 50-190 ms.

Recently, Bana and Comon-Lundh introduced the notion of computationally complete symbolic attacker to deliver unconditional computational soundness to symbolic protocol verification. First we explain the relationship between their technique and Fitting's embedding of classical logic into S4. Then, based on predicates for "key usability", we provide an axiomatic system in their framework to handle secure encryption when keys are allowed to be sent. We examine both IND-CCA2 and KDM-CCA2 encryptions, both symmetric and asymmetric situations. For unforgeability, we consider INT-CTXT encryptions. This technique does not require the usual limitations of computational soundness such as the absence of dynamic corruption, the absence of key-cycles or unambiguous parsing of bit strings. In particular, if a key-cycle possibly corrupts CCA2 encryption, our technique delivers an attack. If it does not endanger security, the security proof goes through. We illustrate how our notions can be applied in protocol proofs.

We present a power-saving method for large-scale distributed storage systems. The key idea is to use virtual nodes and migrate them dynamically so as to skew the workload towards a small number of disks while not overloading them. Our proposed method consists of two kinds of algorithms, one for gathering or spreading virtual nodes according to the daily variation of workloads so that the active disks are reduced to a minimum, the other for coping with the changes in the popularity of data over a longer period. For this dynamic migration, data stored in virtual nodes are managed by a distributed hash table. Furthermore, to improve the reliability as well as to reduce the migration cost, we also propose an extension of our method by introducing a replication mechanism. The performance of our method is measured both by simulation and a prototype implementation. From the experiments, we observed that our method skews the workload so that the average load for the active physical nodes as a function of the overall capacity is 67%. At the same time, we maintain a preferred response time by setting a suitable maximum workload for each physical node.

Various security models for supporting delegation in workflow systems have been proposed to achieve flexible access control in collaborative business processes. Since workflow systems come into their own when controlling large-scale business processes in a well-structured organization, these models are often based on role-based access control (RBAC). However, to realize a higher level of collaboration enabling users in different organizations to complete a common workflow, it is necessary to support cross-domain delegation of tasks. For this purpose, we propose a delegation model for workflow systems that extends the capability-role-based access control (CRBAC) model introduced in our previous work. The central idea behind our proposed model is that authority to perform tasks, as well as roles, are mapped to capabilities, thereby realizing delegation by capability transfer. By adopting the approach of a capability-based access control mechanism, our model provides both flexibility and reduced administration costs, thus allowing it to cope with unexpected changes in task assignments. We demonstrate these advantages by considering an example.

For flexible and dynamic resource management in environments where users collaborate to fulfill their common tasks, various attempts at modeling delegation of authority have been proposed using the role-based access control (RBAC) model. However, to achieve a higher level of collaboration in large-scale networked systems, it is worthwhile supporting cross-domain delegation with low administration cost. For that purpose, we propose a capability-role-based access control (CRBAC) model, by integrating a capability-based access control mechanism into the RBAC96 model. Central to this scheme is the mapping of capabilities to permissions as well as to roles in each domain, thereby realizing the delegation of permissions and roles by capability transfer. By taking this approach of capability-based access control, our model has the advantages of flexibility and reduced administration costs. We also demonstrate the effectiveness of our model by using examples of various types of delegation in clinical information systems.