Search

In this paper, we consider the gathering problem of seven autonomous mobile robots on triangular grids. The gathering problem requires that, starting from any connected initial configuration where a subgraph induced by all robot nodes (nodes where a robot exists) constitutes one connected graph, robots reach a configuration such that the maximum distance between two robots is minimized. For the case of seven robots, gathering is achieved when one robot has six adjacent robot nodes (they form a shape like a hexagon). In this paper, we aim to clarify the relationship between the capability of robots and the solvability of gathering on a triangular grid. In particular, we focus on visibility range of robots. To discuss the solvability of the problem in terms of the visibility range, we consider strong assumptions except for visibility range. Concretely, we assume that robots are fully synchronous and they agree on the direction and orientation of the x-axis, and chirality in the triangular grid. In this setting, we first consider the weakest assumption about visibility range, i.e., robots with visibility range 1. In this case, we show that there exists no collision-free algorithm to solve the gathering problem. Next, we extend the visibility range to 2. In this case, we show that our algorithm can solve the problem from any connected initial configuration. Thus, the proposed algorithm is optimal in terms of visibility range., 23rd Workshop on Advances in Parallel and Distributed Computational Models (APDCM2021), May 17, 2021, to be held in conjunction with 35th IEEE International Parallel and Distributed Processing Symposium (IPDPS2021), May 17-21, 2021, Portland, Oregon, USA

We present a new state transfer method for geographic State Machine Replication (SMR) that dynamically allocates the state to be transferred among replicas according to changes in communication bandwidths. SMR is a method that improves fault tolerance by replicating a service to multiple replicas. When a replica is newly added or is recovered from a failure, the other replicas transfer the current state of the service to it. However, in geographic SMR, the communication bandwidths of replicas are different and constantly changing. Therefore, existing state transfer methods cannot fully utilize the available bandwidth, and their state transfer time becomes long. To overcome this problem, our method divides the state into multiple chunks and assigns them to replicas based on each replica's bandwidth so that the broader a replica's bandwidth is, the more chunks it transfers. The number of assigned chunks is dynamically updated based on the currently estimated bandwidth. The performance evaluation on Amazon EC2 shows that the proposed method reduces the state transfer time by up to 47% compared with the existing one., Comment: This manuscript was submitted to the Ninth International Symposium on Computing and Networking (CANDAR 2021)

We study the gathering problem requiring a team of mobile agents to gather at a single node in arbitrary networks. The team consists of $k$ agents with unique identifiers (IDs), and $f$ of them are weakly Byzantine agents, which behave arbitrarily except falsifying their identifiers. The agents move in synchronous rounds and cannot leave any information on nodes. If the number of nodes $n$ is given to agents, the existing fastest algorithm tolerates any number of weakly Byzantine agents and achieves gathering with simultaneous termination in $O(n^4\cdot|\Lambda_{good}|\cdot X(n))$ rounds, where $|\Lambda_{good}|$ is the length of the maximum ID of non-Byzantine agents and $X(n)$ is the number of rounds required to explore any network composed of $n$ nodes. In this paper, we ask the question of whether we can reduce the time complexity if we have a strong team, i.e., a team with a few Byzantine agents, because not so many agents are subject to faults in practice. We give a positive answer to this question by proposing two algorithms in the case where at least $4f^2+9f+4$ agents exist. Both the algorithms take the upper bound $N$ of $n$ as input. The first algorithm achieves gathering with non-simultaneous termination in $O((f+|\Lambda_{good}|)\cdot X(N))$ rounds. The second algorithm achieves gathering with simultaneous termination in $O((f+|\Lambda_{all}|)\cdot X(N))$ rounds, where $|\Lambda_{all}|$ is the length of the maximum ID of all agents. The second algorithm significantly reduces the time complexity compared to the existing one if $n$ is given to agents and $|\Lambda_{all}|=O(|\Lambda_{good}|)$ holds., Comment: 20 pages, 1 figure, 2 tables, 5 pseudo-codes

Tantalizing hints of the Higgs boson of mass around 125 GeV have been reported at the LHC. We explore the MSSM parameter space in which the 125 GeV state is identified as the heavier of the CP even Higgs bosons, and study two scenarios where the two photon production rate can be significantly larger than the standard model (SM). In one scenario, $\Gamma(H\to \gamma\gamma)$ is enhanced by a light stau contribution, while the $WW^{\ast}$ ($ZZ^{\ast}$) rate stays around the SM rate. In the other scenario, $\Gamma(H\to b\bar{b})$ is suppressed and not only the $\gamma\gamma$ but also the $WW^{\ast}$ ($ZZ^{\ast}$) rates should be enhanced. The $\tau\bar{\tau}$ rate can be significantly larger or smaller than the SM rate in both scenarios. Other common features of the scenarios include top quark decays into charged Higgs boson, single and pair production of all Higgs bosons in $e^+e^-$ collisions at $\sqrt{s}\lesssim 300$ GeV., Comment: 20 pages, 5 figures, accepted version for publication in JHEP

We study contributions of a scalar diquark particle in a color representation of anti-triplet and sextet to the top quark pair production at the Tevatron and the Large hadron collider (LHC). The model can give Forward-Backward (FB) asymmetry at the Tevatron while can avoid the same sign top quark production at the LHC by assuming the top-number conserving diquark couplings. We study compatibility between the large positive FB asymmetry observed at the Tevatron and non-observation of the charge asymmetry at the LHC, by including contributions from the single and pair production of diquarks. We find that the whole parameter space of the models can soon be explored at the LHC by measuring the total t-tbar production cross section and the inclusive charge asymmetry with smaller uncertainties. In addition, we compare the statistical significance of the charge asymmetry measured at the LHC with that of the optimal observable of the subprocess FB asymmetry, and find that they are comparable even when we ignore the uncertainty in the parton distribution functions., Comment: 18 pages,7 figures, 1 table. Accepted version for publication in JHEP