木庭 淳

We consider a multiagent network model consisting of nodes and edges as cities and their links to neighbors, respectively. Each network node has an agent and priced goods and the agent can buy or sell goods in the neighborhood. Though every node may not have an equal price, we show the prices will reach an equilibrium by iterating buy and sell operations. First, we present a protocol model in which each buying agent makes a bid to the lowest priced goods in the neighborhood and each selling agent selects the highest bid, if any. Second, we derive a sufficient condition which stabilizes price in our model. We also show the equilibrium price can be derived from the total funds and the total goods for any network. This is a special case of the Fisher's quantity equation, thus we can confirm the correctness of our model. We then examine the best bidding strategy is available to our protocol. Third, we analyze stabilization time for path and cycle networks. Finally, we perform simulation experiments for estimating the stabilization time, the number of bidders and the effects of spreading funds. Our model is suitable for investigating the effects of network topologies on price stabilization.

In 1997, a minority game (MG) was proposed as a non-cooperative iterated game with an odd population of agents who make bids whether to buy or sell. Since then, many variants of the MG have been proposed. However, the common disadvantage in their characteristics is to ignore the past actions beyond a constant memory. So it is difficult to simulate actual payoffs of agents if the past price behavior has a significant influence on the current decision. In this paper we present a new variant of the MG, called an asset value game (AG), and its extension, called an extended asset value game (ExAG). In the AG, since every agent aims to decrease the mean acquisition cost of his asset, he automatically takes the past actions into consideration. The AG, however, is too simple to reproduce the complete market dynamics, that is, there may be some time lag between the price and his action. So we further consider the ExAG by using probabilistic actions, and compare them by simulation. © Springer-Verlag Berlin Heidelberg 2013.

A minority game (MG) is a non-cooperative iterated game with an odd population agents who make bids whether to buy or sell. Based on the framework of MG, several kinds of games have been proposed. However, the common disadvantage nu their characteristics is to neglect past actions. So WC present a new variant of the MG, called an asset value game (AG), in which every agent aims to decrease a mean asset value, that is. an acquisition cost averaged through the past actions. The AG, however, is too simple to reproduce the complete market dynamics. So we further consider an improvement of AG, called an extended asset value game (ExAG), and investigate their features and obtain some results by simulation.

A non-cooperative iterated multiagent game, called a minority game, and its variations have been extensively studied in this decade. To increase its market similarity, a $-game was presented by observing the current and the next agent's payoffs. However, since the $-game is defined as an offline game, it is difficult to simulate it in practice. So we propose a new online version of the $-game, called a lazy $-game, and analyze the price behavior of the game. First, we reveal the condition of a bubble phenomenon in the lazy $-game. Next, we investigate the price behavior in the lazy $-game and show that there are some upper/lower bounds of the price as long as both the buyers group and the sellers group are nonempty. Then, we consider the similarity between the lazy $-game and the $-game. Finally, we present some simulation results. (C) 2009 Elsevier B.V. All rights reserved.

Sensor networks have promising applications such as battlefield surveillance, biological detection, and emergency navigation, etc. Crucial problems in sensor networks are energy-efficiency and collision avoidance in wireless communication. To deal with the problems, we consider a self-stabilizing solution to the construction of k disjoint sense-steep trees, where range adjustment and the use of GPS are allowed. Each root is determined by its identifier and is distinguished by its color, the identification of a tree. Using a dominating k-partition rule, each non-root node first determines a color irrelevant to the root. Then, the non-root node determines a parent node that is equally colored with minimal distance. If there is no appropriate parent, the range is extended or shrunk until the nearest parent is determined. Finally, we perform a simulation.

This paper presents a new method for request-based self-stabilizing token passing. A token is passed via a dynamic BFS (breadth-first search) tree rooted at a requesting process. When one of the tree edges reaches a process that has a token, the process is aware of the occurrence of a request. Then the token is passed towards the root. Even if multiple tokens stay at distinct roots, it can be shown that they will be merged into a single token. Furthermore, each request-rooted tree continues to grow until the request is serviced. As a result, the tree with a request that has long been neglected grows larger and larger, which makes it easier for the requesting process to get a token. Such advantages can be achieved by using bounded memory. We also evaluate the stabilization time and the efficiency of servicing k requests, called k-covering time, of our method. (C) 2005 Elsevier Inc. All rights reserved.

We present a new method for avoiding false privileges with the aid of stable storage. The method is motivated by the commitment in database systems. The commit guarantees that a write operation to stable storage has successfully completed. Since programs are stored in stable storage in self-stabilization, we assume that the stable values are also free from any transient fault. They sometimes give us additional information on whether a state is faulty or not. Using the stable values, we can improve our previous weakly time-adaptive protocol. We analyze the efficiency and the safety of our method and compare it with previously proposed ones. Furthermore, we extend our method by keeping an old version of stable values and show its usefulness.

For bidirectional rings, there have been proposed self-stabilizing mutual exclusion protocols, which are either time-adaptive (i.e., efficient in recovery) or 1-latent (i.e., efficient in legal execution) but not both. This paper proposes a randomized self-stabilizing mutual exclusion protocol that inherits both of the advantages from them: It is 1-latent in the sense that the privilege is circulated in a linear round (i.e., very intuitively, the privilege is transferred from a process to another by a "step"), provided that the system always stays in legitimate configurations, and is weakly time-adaptive in the sense that the system stabilizes from any configuration c in O(f) steps with a high probability, where f is the number of corrupted processes in c. It also guarantees with a high probability that there is at most one privilege even while converging to a legitimate configuration. © World Scientific Publishing Company.

Most conventional studies on self-stabilization have been indifferent to the vulnerability under convergence. This paper investigates how mutual exclusion property can be achieved in self-stabilizing rings even for illegitimate configurations. We present a new method which uses a state with a large state space to detect faults. If some faults are detected, every process is reset and not given a privilege. Even if the reset values are different between processes, our protocol mimics the behavior of Dijkstra's unidirectional K-state protocol. Then we have a fast and safe mutual exclusion protocol. Simulation study also examines its performance.

分散システムにおいて仮想リングを構築する新方法について述べる。我々の方法の特徴は通常のトークン伝達を行っている間にバックグラウンドジョブとして仮想リングを改良するというもので、拡張型の深さ優先探索手法を利用している。トークンは仮想リングを何度も周回するので、仮想リングはしだいに改良され、(もし存在するなら)ハミルトン閉路に近づく。我々の方法は主に2つのトークンを使う。すなわち1つはより短い新しいリングを構築するためのものであり、いま1つは相互排除のためのものである。従ってMisraの方法を修正して用いることにより、トークンの消失にも耐えることができる。

This paper studies the effects of reordering page requests for multisize page caching. First, we consider a "semi-online" model, where an input queue keeps requests which will be processed in the future. It is assumed that they arrive during the processing time of miss requests. We develop an efficient page replacement algorithm which shifts some page requests in the queue. Second, we analyze the miss ratios of two methods, the nonshifting method and our shifting method, under the semi-online model. The analysis assumes that the input/output ratio of the queue is in equilibrium. Third, we compare our method with the other algorithms by simulation.