Search

Your search keyword '"Masuzawa, Toshimitsu"' showing total 780 results
Start Over Author "Masuzawa, Toshimitsu"

Refine your results

more »

more »

more »

more »
780 results on '"Masuzawa, Toshimitsu"'

51. Construction auto-stabilisante d'arbre couvrant en d\'epit d'actions malicieuses

Author

Dubois, Swan, Masuzawa, Toshimitsu, and Tixeuil, Sébastien

Subjects
Computer Science - Distributed, Parallel, and Cluster Computing
Abstract

A self-stabilizing protocol provides by definition a tolerance to transient failures. Recently, a new class of self-stabilizing protocols appears. These protocols provides also a tolerance to a given number of permanent failures. In this article, we are interested in self-stabilizing protocols that deal with Byzantines failures. We prove that, for some problems which not allow strict stabilization (see [Nesterenko,Arora,2002]), there exist solutions that tolerates Byzantine faults if we define a new criteria of tolerance.

Published
2010

52. Stabilizing Maximal Independent Set in Unidirectional Networks is Hard

Author

Masuzawa, Toshimitsu and Tixeuil, Sébastien

Subjects
Computer Science - Data Structures and Algorithms, Computer Science - Computational Complexity, Computer Science - Distributed, Parallel, and Cluster Computing, Computer Science - Networking and Internet Architecture, Computer Science - Performance
Abstract

A distributed algorithm is self-stabilizing if after faults and attacks hit the system and place it in some arbitrary global state, the system recovers from this catastrophic situation without external intervention in finite time. In this paper, we consider the problem of constructing self-stabilizingly a \emph{maximal independent set} in uniform unidirectional networks of arbitrary shape. On the negative side, we present evidence that in uniform networks, \emph{deterministic} self-stabilization of this problem is \emph{impossible}. Also, the \emph{silence} property (\emph{i.e.} having communication fixed from some point in every execution) is impossible to guarantee, either for deterministic or for probabilistic variants of protocols. On the positive side, we present a deterministic protocol for networks with arbitrary unidirectional networks with unique identifiers that exhibits polynomial space and time complexity in asynchronous scheduling. We complement the study with probabilistic protocols for the uniform case: the first probabilistic protocol requires infinite memory but copes with asynchronous scheduling, while the second probabilistic protocol has polynomial space complexity but can only handle synchronous scheduling. Both probabilistic solutions have expected polynomial time complexity.

Published
2009

54. Communication Efficiency in Self-stabilizing Silent Protocols

Author

Devismes, Stéphane, Masuzawa, Toshimitsu, and Tixeuil, Sébastien

Subjects
Computer Science - Data Structures and Algorithms, Computer Science - Computational Complexity, Computer Science - Distributed, Parallel, and Cluster Computing, Computer Science - Networking and Internet Architecture
Abstract

Self-stabilization is a general paradigm to provide forward recovery capabilities to distributed systems and networks. Intuitively, a protocol is self-stabilizing if it is able to recover without external intervention from any catastrophic transient failure. In this paper, our focus is to lower the communication complexity of self-stabilizing protocols \emph{below} the need of checking every neighbor forever. In more details, the contribution of the paper is threefold: (i) We provide new complexity measures for communication efficiency of self-stabilizing protocols, especially in the stabilized phase or when there are no faults, (ii) On the negative side, we show that for non-trivial problems such as coloring, maximal matching, and maximal independent set, it is impossible to get (deterministic or probabilistic) self-stabilizing solutions where every participant communicates with less than every neighbor in the stabilized phase, and (iii) On the positive side, we present protocols for coloring, maximal matching, and maximal independent set such that a fraction of the participants communicates with exactly one neighbor in the stabilized phase.

Published
2008

55. Quiescence of Self-stabilizing Gossiping among Mobile Agents in Graphs

Author

Masuzawa, Toshimitsu and Tixeuil, Sébastien

Subjects
Computer Science - Distributed, Parallel, and Cluster Computing, Computer Science - Performance, Computer Science - Robotics
Abstract

This paper considers gossiping among mobile agents in graphs: agents move on the graph and have to disseminate their initial information to every other agent. We focus on self-stabilizing solutions for the gossip problem, where agents may start from arbitrary locations in arbitrary states. Self-stabilization requires (some of the) participating agents to keep moving forever, hinting at maximizing the number of agents that could be allowed to stop moving eventually. This paper formalizes the self-stabilizing agent gossip problem, introduces the quiescence number (i.e., the maximum number of eventually stopping agents) of self-stabilizing solutions and investigates the quiescence number with respect to several assumptions related to agent anonymity, synchrony, link duplex capacity, and whiteboard capacity.

Published
2008

56. Space-Efficient Uniform Deployment of Mobile Agents in Asynchronous Unidirectional Rings

Author

Shibata, Masahiro, Kakugawa, Hirotsugu, Masuzawa, Toshimitsu, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Lotker, Zvi, editor, and Patt-Shamir, Boaz, editor

Published
2018
Full Text
View/download PDF

57. Constant-Space Self-stabilizing Token Distribution in Trees

Author

Sudo, Yuichi, Datta, Ajoy K., Larmore, Lawrence L., Masuzawa, Toshimitsu, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Lotker, Zvi, editor, and Patt-Shamir, Boaz, editor

Published
2018
Full Text
View/download PDF

59. Available and Stabilizing 2-3 Trees

Author

Herman, Ted and Masuzawa, Toshimitsu

Subjects
Computer Science - Distributed, Parallel, and Cluster Computing, Computer Science - Data Structures and Algorithms, D.4.5, E.1, C.4
Abstract

Transient faults corrupt the content and organization of data structures. A recovery technique dealing with such faults is stabilization, which guarantees, following some number of operations on the data structure, that content of the data structure is legitimate. Another notion of fault tolerance is availability, which is the property that operations continue to be applied during the period of recovery after a fault, and successful updates are not lost while the data structure stabilizes to a legitimate state. The available, stabilizing 2-3 tree supports find, insert, and delete operations, each with O(lg n) complexity when the tree's state is legitimate and contains n items. For an illegitimate state, these operations have O(lg K) complexity where K is the maximum capacity of the tree. Within O(t) operations, the state of the tree is guaranteed to be legitimate, where t is the number of nodes accessible via some path from the tree's root at the initial state. This paper resolves, for the first time, issues of dynamic allocation and pointer organization in a stabilizing data structure., Comment: 22 pages, 5 figures

Published
2000

60. Available Stabilizing Heaps

Author

Herman, Ted and Masuzawa, Toshimitsu

Subjects
Computer Science - Distributed, Parallel, and Cluster Computing, Computer Science - Data Structures and Algorithms, C.2.4, D.1.3, D.3.3, E.2, C.4
Abstract

This paper describes a heap construction that supports insert and delete operations in arbitrary (possibly illegitimate) states. After any sequence of at most O(m) heap operations, the heap state is guarantee to be legitimate, where m is the initial number of items in the heap. The response from each operation is consistent with its effect on the data structure, even for illegitimate states. The time complexity of each operation is O(lg K) where K is the capacity of the data structure; when the heap's state is legitimate the time complexity is O(lg n) for n equal to the number items in the heap., Comment: 10 pages

Published
2000

61. Brief Announcement: Space-Efficient Uniform Deployment of Mobile Agents in Asynchronous Unidirectional Rings

Author

Shibata, Masahiro, Kakugawa, Hirotsugu, Masuzawa, Toshimitsu, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Spirakis, Paul, editor, and Tsigas, Philippas, editor

Published
2017
Full Text
View/download PDF

62. Self-stabilizing Rendezvous of Synchronous Mobile Agents in Graphs

Author

Ooshita, Fukuhito, Datta, Ajoy K., Masuzawa, Toshimitsu, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Spirakis, Paul, editor, and Tsigas, Philippas, editor

Published
2017
Full Text
View/download PDF

63. Brief Announcement: A Self-stabilizing Algorithm for the Minimal Generalized Dominating Set Problem

Author

Kobayashi, Hisaki, Kakugawa, Hirotsugu, Masuzawa, Toshimitsu, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Spirakis, Paul, editor, and Tsigas, Philippas, editor

Published
2017
Full Text
View/download PDF

64. How to Simulate Message-Passing Algorithms in Mobile Agent Systems with Faults

Author

Gotoh, Tsuyoshi, Ooshita, Fukuhito, Kakugawa, Hirotsugu, Masuzawa, Toshimitsu, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Spirakis, Paul, editor, and Tsigas, Philippas, editor

Published
2017
Full Text
View/download PDF

65. Brief Announcement: Reduced Space Self-stabilizing Center Finding Algorithms in Chains and Trees

Author

Sudo, Yuichi, Datta, Ajoy K., Larmore, Lawrence L., Masuzawa, Toshimitsu, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Spirakis, Paul, editor, and Tsigas, Philippas, editor

Published
2017
Full Text
View/download PDF

76. An Interest-Based Peer Clustering Algorithm Using Ant Paradigm

Author

Izumi, Taisuke, Masuzawa, Toshimitsu, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Ijspeert, Auke Jan, editor, Masuzawa, Toshimitsu, editor, and Kusumoto, Shinji, editor

Published
2006
Full Text
View/download PDF

77. Bio-inspired Replica Density Control in Dynamic Networks

Author

Suzuki, Tomoko, Izumi, Taisuke, Ooshita, Fukuhito, Kakugawa, Hirotsugu, Masuzawa, Toshimitsu, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Ijspeert, Auke Jan, editor, Masuzawa, Toshimitsu, editor, and Kusumoto, Shinji, editor

Published
2006
Full Text
View/download PDF

78. Loosely-Stabilizing Leader Election on Arbitrary Graphs in Population Protocols Without Identifiers nor Random Numbers

Author

Sudo, Yuichi, Ooshita, Fukuhito, Kakugawa, Hirotsugu, Masuzawa, Toshimitsu, Sudo, Yuichi, Ooshita, Fukuhito, Kakugawa, Hirotsugu, and Masuzawa, Toshimitsu

Abstract

In the population protocol model Angluin et al. proposed in 2004, there exists no self-stabilizing leader election protocol for complete graphs, arbitrary graphs, trees, lines, degree-bounded graphs and so on unless the protocol knows the exact number of nodes. To circumvent the impossibility, we introduced the concept of loose-stabilization in 2009, which relaxes the closure requirement of self-stabilization. A loosely-stabilizing protocol guarantees that starting from any initial configuration a system reaches a safe configuration, and after that, the system keeps its specification (e.g. the unique leader) not forever, but for a sufficiently long time (e.g. exponentially large time with respect to the number of nodes). Our previous works presented two loosely-stabilizing leader election protocols for arbitrary graphs; One uses agent identifiers and the other uses random numbers to elect a unique leader. In this paper, we present a loosely-stabilizing protocol that solves leader election on arbitrary graphs without agent identifiers nor random numbers. By the combination of virus-propagation and token-circulation, the proposed protocol achieves polynomial convergence time and exponential holding time without such external entities. Specifically, given upper bounds N and Delta of the number of nodes n and the maximum degree of nodes delta respectively, it reaches a safe configuration within O(m*n^3*d + m*N*Delta^2*log(N)) expected steps, and keeps the unique leader for Omega(N*e^N) expected steps where m is the number of edges and d is the diameter of the graph. To measure the time complexity of the protocol, we assume the uniformly random scheduler which is widely used in the field of the population protocols., OPODIS 2015 : 19th International Conference on Principles of Distributed Systems, 14-17 Dec. 2015 , Rennes, France

Published
2023

79. Dynamic Ring Exploration with (H,S) View

Author

Gotoh, Tsuyoshi, Sudo, Yuichi, Ooshita, Fukuhito, Masuzawa, Toshimitsu, Gotoh, Tsuyoshi, Sudo, Yuichi, Ooshita, Fukuhito, and Masuzawa, Toshimitsu

Abstract

The researches about a mobile entity (called agent) on dynamic networks have attracted a lot of attention in recent years. Exploration which requires an agent to visit all the nodes in the network is one of the most fundamental problems. While the exploration of dynamic networks with complete information or with no information about network changes has been studied, an agent with partial information about the network changes has not been considered yet despite its practical importance. In this paper, we consider the exploration of dynamic networks by a single agent with partial information about network changes. To the best of our knowledge, this is the very first work to investigate the exploration problem with such partial information. As a first step in this researchdirection, we focus on 1-interval connected rings as dynamic networks in this paper. We assume that the single agent has partial information called the (H, S) view by which it always knows whether or not each of the links within H hops is available in each of the next S time steps. In this setting, we show that H + S n and S dn/2e (n is the size of the network) are necessary and sufficient conditions to explore 1-interval connected rings. Moreover, we investigate the upper and lower bounds of the exploration time. It is proven that the exploration time is O(n2) for dn/2e S < 2H0 ???? 1,O(n2/H + nH) for S max(dn/2e, 2H0 ???? 1), O(n2/H + n log H) for S n ???? 1, and W(n2/H) forany S where H0 = min(H, bn/2c).

Published
2023

81. Gathering of Mobile Robots with Defected Views

Author

Yonghwan Kim and Masahiro Shibata and Yuichi Sudo and Junya Nakamura and Yoshiaki Katayama and Toshimitsu Masuzawa, Kim, Yonghwan, Shibata, Masahiro, Sudo, Yuichi, Nakamura, Junya, Katayama, Yoshiaki, Masuzawa, Toshimitsu, Yonghwan Kim and Masahiro Shibata and Yuichi Sudo and Junya Nakamura and Yoshiaki Katayama and Toshimitsu Masuzawa, Kim, Yonghwan, Shibata, Masahiro, Sudo, Yuichi, Nakamura, Junya, Katayama, Yoshiaki, and Masuzawa, Toshimitsu

Abstract

An autonomous mobile robot system consisting of many mobile computational entities (called robots) attracts much attention of researchers, and it is an emerging issue for a recent couple of decades to clarify the relation between the capabilities of robots and solvability of the problems. Generally, each robot can observe all other robots as long as there are no restrictions on visibility range or obstructions, regardless of the number of robots. In this paper, we provide a new perspective on the observation by robots; a robot cannot necessarily observe all other robots regardless of distances to them. We call this new computational model the defected view model. Under this model, in this paper, we consider the gathering problem that requires all the robots to gather at the same non-predetermined point and propose two algorithms to solve the gathering problem in the adversarial (N,N-2)-defected model for N ≥ 5 (where each robot observes at most N-2 robots chosen adversarially) and the distance-based (4,2)-defected model (where each robot observes at most two robots closest to itself), respectively, where N is the number of robots. Moreover, we present an impossibility result showing that there is no (deterministic) gathering algorithm in the adversarial or distance-based (3,1)-defected model, and we also show an impossibility result for the gathering in a relaxed (N, N-2)-defected model.

Published
2023
Full Text
View/download PDF

82. Loosely-Stabilizing Leader Election on Arbitrary Graphs in Population Protocols

Author

Sudo, Yuichi, Ooshita, Fukuhito, Kakugawa, Hirotsugu, Masuzawa, Toshimitsu, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Aguilera, Marcos K., editor, Querzoni, Leonardo, editor, and Shapiro, Marc, editor

Published
2014
Full Text
View/download PDF

83. A Communication-Efficient Self-stabilizing Algorithm for Breadth-First Search Trees

Author

Datta, Ajoy K., Larmore, Lawrence L., Masuzawa, Toshimitsu, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Aguilera, Marcos K., editor, Querzoni, Leonardo, editor, and Shapiro, Marc, editor

Published
2014
Full Text
View/download PDF

84. Edge Coloring Despite Transient and Permanent Faults

Author

Maurer, Alexandre, Masuzawa, Toshimitsu, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Felber, Pascal, editor, and Garg, Vijay, editor

Published
2014
Full Text
View/download PDF

85. Move-Optimal Partial Gathering of Mobile Agents in Asynchronous Trees

Author

Shibata, Masahiro, Ooshita, Fukuhito, Kakugawa, Hirotsugu, Masuzawa, Toshimitsu, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, and Halldórsson, Magnús M., editor

Published
2014
Full Text
View/download PDF

86. Algorithms for Partial Gathering of Mobile Agents in Asynchronous Rings

Author

Shibata, Masahiro, Kawai, Shinji, Ooshita, Fukuhito, Kakugawa, Hirotsugu, Masuzawa, Toshimitsu, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Baldoni, Roberto, editor, Flocchini, Paola, editor, and Binoy, Ravindran, editor

Published
2012
Full Text
View/download PDF

87. Communication-Efficient Self-stabilization in Wireless Networks

Author

Takimoto, Tomoya, Ooshita, Fukuhito, Kakugawa, Hirotsugu, Masuzawa, Toshimitsu, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Richa, Andréa W., editor, and Scheideler, Christian, editor

Published
2012
Full Text
View/download PDF

88. Randomized Rendezvous of Mobile Agents in Anonymous Unidirectional Ring Networks

Author

Kawai, Shinji, Ooshita, Fukuhito, Kakugawa, Hirotsugu, Masuzawa, Toshimitsu, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Even, Guy, editor, and Halldórsson, Magnús M., editor

Published
2012
Full Text
View/download PDF

89. Gathering of Mobile Robots with Defected Views

Author

Kim, Yonghwan, Shibata, Masahiro, Sudo, Yuichi, Nakamura, Junya, Katayama, Yoshiaki, and Masuzawa, Toshimitsu

Subjects
defected view model, gathering, Theory of computation → Self-organization, mobile robot
Abstract

An autonomous mobile robot system consisting of many mobile computational entities (called robots) attracts much attention of researchers, and it is an emerging issue for a recent couple of decades to clarify the relation between the capabilities of robots and solvability of the problems. Generally, each robot can observe all other robots as long as there are no restrictions on visibility range or obstructions, regardless of the number of robots. In this paper, we provide a new perspective on the observation by robots; a robot cannot necessarily observe all other robots regardless of distances to them. We call this new computational model the defected view model. Under this model, in this paper, we consider the gathering problem that requires all the robots to gather at the same non-predetermined point and propose two algorithms to solve the gathering problem in the adversarial (N,N-2)-defected model for N ≥ 5 (where each robot observes at most N-2 robots chosen adversarially) and the distance-based (4,2)-defected model (where each robot observes at most two robots closest to itself), respectively, where N is the number of robots. Moreover, we present an impossibility result showing that there is no (deterministic) gathering algorithm in the adversarial or distance-based (3,1)-defected model, and we also show an impossibility result for the gathering in a relaxed (N, N-2)-defected model., LIPIcs, Vol. 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022), pages 14:1-14:18

Published
2023
Full Text
View/download PDF

92. Space-Optimal Rendezvous of Mobile Agents in Asynchronous Trees

Author

Baba, Daisuke, Izumi, Tomoko, Ooshita, Fukuhito, Kakugawa, Hirotsugu, Masuzawa, Toshimitsu, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Patt-Shamir, Boaz, editor, and Ekim, Tınaz, editor

Published
2010
Full Text
View/download PDF

93. Loosely-Stabilizing Leader Election in Population Protocol Model

Author

Sudo, Yuichi, Nakamura, Junya, Yamauchi, Yukiko, Ooshita, Fukuhito, Kakugawa, Hirotsugu, Masuzawa, Toshimitsu, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Kutten, Shay, editor, and Žerovnik, Janez, editor

Published
2010
Full Text
View/download PDF

94. Brief Announcement: Communication-Efficient Self-stabilizing Protocols for Spanning-Tree Construction

Author

Masuzawa, Toshimitsu, Izumi, Taisuke, Katayama, Yoshiaki, Wada, Koichi, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Abdelzaher, Tarek, editor, Raynal, Michel, editor, and Santoro, Nicola, editor

Published
2009
Full Text
View/download PDF

95. Cached Sensornet Transformation of Non-silent Self-stabilizing Algorithms with Unreliable Links

Author

Kakugawa, Hirotsugu, Yamauchi, Yukiko, Kamei, Sayaka, Masuzawa, Toshimitsu, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Guerraoui, Rachid, editor, and Petit, Franck, editor

Published
2009
Full Text
View/download PDF

100. Convergence Time Analysis of Self-stabilizing Algorithms in Wireless Sensor Networks with Unreliable Links

Author

Kakugawa, Hirotsugu, Masuzawa, Toshimitsu, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Kulkarni, Sandeep, editor, and Schiper, André, editor

Published
2008
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results