Search

In the population protocol model, many problems cannot be solved in a self-stabilizing way. However, global knowledge, such as the number of nodes in a network, sometimes allow us to design a self-stabilizing protocol for such problems. In this paper, we investigate the effect of global knowledge on the possibility of self-stabilizing population protocols in arbitrary graphs. Specifically, we clarify the solvability of the leader election problem, the ranking problem, the degree recognition problem, and the neighbor recognition problem by self-stabilizing population protocols with knowledge of the number of nodes and/or the number of edges in a network.

In this paper, we consider the uniform deployment problem of mobile agents in synchronous dynamic bidirectional rings, which requires agents to spread uniformly in the ring. So far, uniform deployment has been considered in static graphs. In this paper, we consider this problem in 1-interval connected rings, that is, one of the links may be missing at each time step. In such networks, we aim to clarify the solvability of the uniform deployment problem, focusing on global knowledge given to the agents. To the best of our knowledge, this is the first research considering uniform deployment in dynamic networks. First, we consider agents with knowledge of the number n of nodes. In this case, we show that our algorithm can solve the problem with \(O(k\log n)\) memory space per agent, \(O(n\log k)\) rounds, and a total number of O(kn) moves, where k is the number of agents. Next, we consider agents without knowledge of n but with knowledge of k. In this case, when \(k\ge 4\), we show that our algorithm can also solve the problem but requires \(O(k\log n)\) memory space per agent, \(O(n^2)\) rounds, and a total number of \(O(n^2)\) moves. These results mean that the uniform deployment problem can be solved also in dynamic rings.

In this paper, we propose a self-stabilizing algorithm to construct a minimal weakly \(\mathcal {ST}\)-reachable directed acyclic graph (DAG). Given an arbitrary simple, connected, and undirected graph \(G=(V, E)\) and two sets of vertices, senders \(\mathcal {S} (\subset V)\) and targets \(\mathcal {T} (\subset V)\), a directed subgraph \(\overrightarrow{G}\) of G is a weakly \(\mathcal {ST}\)-reachable DAG on G if \(\overrightarrow{G}\) is a DAG and every sender can reach at least one target, and every target is reachable from at least one sender in \(\overrightarrow{G}\). We say that a weakly \(\mathcal {ST}\)-reachable DAG \(\overrightarrow{G}\) on G is minimal if any proper subgraph of \(\overrightarrow{G}\) is no longer a weakly \(\mathcal {ST}\)-reachable DAG. The weakly \(\mathcal {ST}\)-reachable DAG on G, which we consider here, is a relaxed version of the original (or strongly) \(\mathcal {ST}\)-reachable DAG on G where all targets are reachable from all senders. A strongly \(\mathcal {ST}\)-reachable DAG G does not always exist; even if we focus on the case \(|\mathcal {S}|=|\mathcal {T}|=2\), some G has no strongly \(\mathcal {ST}\)-reachable DAG. On the other hand, the proposed algorithm always construct a weakly \(\mathcal {ST}\)-reachable DAG for any given graph \(G=(V, E)\) and any \(\mathcal {S}, \mathcal {T} \subset V\).

A wireless network consisting of many wireless devices becomes popular and essential in distributed systems. In the wireless networks, each wireless device, also called nodes, can directly communicate with other devices located within its communication range. However, to communicate with the nodes outside the communication range, the message should be relayed to the target node via some other nodes. A virtual grid network is an overlay network on a wireless network which can be constructed by virtually dividing the area covered by the wireless network into geographical square regions of the same size, selecting a representative node at each region, and connecting the nodes of neighboring regions. A virtual grid network is utilized for realizing an energy-efficient wireless network because not all of the nodes in the system need to join the routing, moreover, a routing algorithm can be easily designed thanks to regularity of the grid topology. A local-information-based self-optimizing routing algorithm, Zigzag, in virtual grid networks was proposed. In this paper, we propose the locality-based model, named \((\alpha , \beta )\)-range model, based on the snapshot range \(\alpha \) and communication range \(\beta \) to clearly specify the locality. Moreover, we propose a new self-optimizing routing algorithm Improved-Zigzag which improves Zigzag by reducing the snapshot range.

The influence of addition of the small amount of transition metals to Al-Mg-Si alloy had reported by many researchers. In the previous our work, β′ phase in alloys Al — 1.0 mass% Mg2Si -0.5 mass% Ag (Ag-addition) and Al -1.0 mass% Mg2Si (base) were investigated by high resolution transmission electron microscopy (HRTEM) and selected area electron diffraction (SAED), in order to understand the effect of Ag. In addition, the distribution of Ag was investigated by energy filtered mapping and high annular angular dark field scanning transmission electron microscopy (HAADF-STEM). One Ag-containing atomic column was observed per β’ unit cell, and the unit cell symmetry is slightly changed as compared with the Ag-free β’. In this work, the microstructure of G.P. zone and β’’ phase was investigated by TEM observation, which were formed before β’ phase. The deformed sample by high pressure torsion (HPT) technique before aging was also investigated to understand its effect for aging in this alloy.

In this study, the aging behaviour of Al-1.0mass%Mg2Si alloys containing 0.35at.%Cu, 0.35at.%Ag, 0.2at.%Cu-0.1at.%Ag and 0.1at.%Cu-0.2at.%Ag has been investigated by hardness measurement and HRTEM observation. 0.35Cu alloy has the highest peak hardness. 0.1Cu-0.2Ag alloy has the shortest aging time to the peak hardness. 0.1Cu-0.2Ag alloy has the fastest age-hardening rate in the early period of aging. 0.35Ag alloy has the finest microstructure at the peak hardness. The precipitates were classified into random-type, parallelogram-type, β’-phase and Q’-phase using HRTEM image with different aging time. Relative frequency of all types of precipitates changed by aging times.