BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Taisuke Izumi

Taisuke Izumi appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Distributed, Parallel, and Cluster ComputingData Structures and AlgorithmsRoboticsInformation Theorymath.ITComputational GeometryDiscrete MathematicsNetworking and Internet ArchitectureSocial and Information Networks

Catalog footprint

What is connected

17works
9topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

17 published item(s)

preprint2022arXiv

Fully Polynomial-Time Distributed Computation in Low-Treewidth Graphs

We consider global problems, i.e. problems that take at least diameter time, even when the bandwidth is not restricted. We show that all problems considered admit efficient solutions in low-treewidth graphs. By ``efficient'' we mean that the running time has polynomial dependence on the treewidth, a linear dependence on the diameter (which is unavoidable), and only a polylogarithmic dependence on $n$, the number of nodes in the graph. We present the algorithms solving the following problems in the CONGEST model which all attain $\tilde{O(τ^{O(1)}D)}$-round complexity (where $τ$ and $D$ denote the treewidth and diameter of the graph, respectively): (1) Exact single-source shortest paths (actually, the more general problem of computing a distance labeling scheme) for weighted and directed graphs, (2) exact bipartite unweighted maximum matching, and (3) the weighted girth for both directed and undirected graphs. We derive all of our results using a single unified framework, which consists of two novel technical ingredients, The first is a fully polynomial-time distributed tree decomposition algorithm, which outputs a decomposition of width $O(τ^2\log n)$ in $\tilde{O}(τ^{O(1)}D)$ rounds (where $n$ is the number of nodes in the graph). The second ingredient, and the technical highlight of this paper, is the novel concept of a \emph{stateful walk constraint}, which naturally defines a set of feasible walks in the input graph based on their local properties (e.g., augmenting paths). Given a stateful walk constraint, the constrained version of the shortest paths problem (or distance labeling) requires the algorithm to output the shortest \emph{constrained} walk (or its distance) for a given source and sink vertices. We show that this problem can be efficiently solved in the CONGEST model by reducing it to an \emph{unconstrained} version of the problem.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

A Subquadratic-Time Distributed Algorithm for Exact Maximum Matching

For a graph G=(V,E), finding a set of disjoint edges that do not share any vertices is called a matching problem, and finding the maximum matching is a fundamental problem in the theory of distributed graph algorithms. Although local algorithms for the approximate maximum matching problem have been widely studied, exact algorithms has not been much studied. In fact, no exact maximum matching algorithm that is faster than the trivial upper bound of O(n^2) rounds is known for the general instance. In this paper, we propose a randomized O(s_{max}^{3/2}+log n)-round algorithm in the CONGEST model, where s_{\max} is the size of maximum matching. This is the first exact maximum matching algorithm in o(n^2) rounds for general instances in the CONGEST model. The key technical ingredient of our result is a distributed algorithms of finding an augmenting path in O(s_{\max}) rounds, which is based on a novel technique of constructing a sparse certificate of augmenting paths, which is a subgraph of the input graph preserving at least one augmenting path. To establish a highly parallel construction of sparse certificates, we also propose a new characterization of sparse certificates, which might also be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Fast Neighborhood Rendezvous

In the rendezvous problem, two computing entities (called \emph{agents}) located at different vertices in a graph have to meet at the same vertex. In this paper, we consider the synchronous \emph{neighborhood rendezvous problem}, where the agents are initially located at two adjacent vertices. While this problem can be trivially solved in $O(Δ)$ rounds ($Δ$ is the maximum degree of the graph), it is highly challenging to reveal whether that problem can be solved in $o(Δ)$ rounds, even assuming the rich computational capability of agents. The only known result is that the time complexity of $O(\sqrt{n})$ rounds is achievable if the graph is complete and agents are probabilistic, asymmetric, and can use whiteboards placed at vertices. Our main contribution is to clarify the situation (with respect to computational models and graph classes) admitting such a sublinear-time rendezvous algorithm. More precisely, we present two algorithms achieving fast rendezvous additionally assuming bounded minimum degree, unique vertex identifier, accessibility to neighborhood IDs, and randomization. The first algorithm runs within $\tilde{O}(\sqrt{nΔ/δ} + n/δ)$ rounds for graphs of the minimum degree larger than $\sqrt{n}$, where $n$ is the number of vertices in the graph, and $δ$ is the minimum degree of the graph. The second algorithm assumes that the largest vertex ID is $O(n)$, and achieves $\tilde{O}\left( \frac{n}{\sqrtδ} \right)$-round time complexity without using whiteboards. These algorithms attain $o(Δ)$-round complexity in the case of $δ= ω(\sqrt{n} \log n)$ and $δ= ω(n^{2/3} \log^{4/3} n)$ respectively.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Low-Congestion Shortcuts without Embedding

Distributed optimization algorithms are frequently faced with solving sub-problems on disjoint connected parts of a network. Unfortunately, the diameter of these parts can be significantly larger than the diameter of the underlying network, leading to slow running times. Recent work by [Ghaffari and Hauepler; SODA'16] showed that this phenomenon can be seen as the broad underlying reason for the pervasive $Ω(\sqrt{n} + D)$ lower bounds that apply to most optimization problems in the CONGEST model. On the positive side, this work also introduced low-congestion shortcuts as an elegant solution to circumvent this problem in certain topologies of interest. Particularly, they showed that there exist good shortcuts for any planar network and more generally any bounded genus network. This directly leads to fast $O(D \log^{O(1)} n)$ distributed algorithms for MST and Min-Cut approximation, given that one can efficiently construct these shortcuts in a distributed manner. Unfortunately, the shortcut construction of [Ghaffari and Hauepler; SODA'16] relies heavily on having access to a genus embedding of the network. Computing such an embedding distributedly, however, is a hard problem - even for planar networks. No distributed embedding algorithm for bounded genus graphs is in sight. In this work, we side-step this problem by defining a restricted and more structured form of shortcuts and giving a novel construction algorithm which efficiently finds a shortcut which is, up to a logarithmic factor, as good as the best shortcut that exists for a given network. This new construction algorithm directly leads to an $O(D \log^{O(1)} n)$-round algorithm for solving optimization problems like MST for any topology for which good restricted shortcuts exist - without the need to compute any embedding. This includes the first efficient algorithm for bounded genus graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Time-optimal Loosely-stabilizing Leader Election in Population Protocols

We consider the leader election problem in population protocol models. In pragmatic settings of population protocols, self-stabilization is a highly desired feature owing to its fault resilience and the benefit of initialization freedom. However, the design of self-stabilizing leader election is possible only under a strong assumption (i.e. the knowledge of the \emph{exact} size of a network) and rich computational resources (i.e. the number of states). Loose-stabilization, introduced by Sudo et al [Theoretical Computer Science, 2012], is a promising relaxed concept of self-stabilization to address the aforementioned issue. Loose-stabilization guarantees that starting from any configuration, the network will reach a safe configuration where a single leader exists within a short time, and thereafter it will maintain the single leader for a long time, but not forever. The main contribution of the paper is a time-optimal loosely-stabilizing leader election protocol. While the shortest convergence time achieved so far in loosely-stabilizing leader election is $O(\log^3 n)$ parallel time, the proposed protocol with design parameter $τ\ge 1$ attains $O(τ\log n)$ parallel convergence time and $Ω(n^τ)$ parallel holding time (i.e. the length of the period keeping the unique leader), both in expectation. This protocol is time-optimal in the sense of both the convergence and holding times in expectation because any loosely-stabilizing leader election protocol with the same length of the holding time is known to require $Ω(τ\log n)$ parallel time.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Bounds on Asymptotic Rate of Capacitive Crosstalk Avoidance Codes for On-chip Buses

In order to prevent the capacitive crosstalk in on-chip buses, several types of capacitive crosstalk avoidance codes have been devised. These codes are designed to prohibit transition patterns prone to the capacity crosstalk from any consecutive two words transmitted to on-chip buses. This paper provides a rigorous analysis on the asymptotic rate of (p,q)-transition free word sequences under the assumption that coding is based on a pair of a stateful encoder and a stateless decoder. The symbols p and q represent k-bit transition patterns that should not be appeared in any consecutive two words at the same adjacent k-bit positions. It is proved that the maximum rate of the sequences equals to the subgraph domatic number of (p,q)-transition free graph. Based on the theoretical results on the subgraph domatic partition problem, a pair of lower and upper bounds on the asymptotic rate is derived. We also present that the asymptotic rate 0.8325 is achievable for the (10,01)-transition free word sequences.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the Power of Weaker Pairwise Interaction: Fault-Tolerant Simulation of Population Protocols

In this paper we investigate the computational power of Population Protocols (PP) under some unreliable and/or weaker interaction models. More precisely, we focus on two features related to the power of interactions: omission failures and one-way communications. An omission failure, a notion that this paper introduces for the first time in the context of PP, is the loss by one or both parties of the information transmitted in an interaction. The failure may or may not be detected by either party. On the other hand, in one-way models, communication happens only in one direction: only one of the two agents can change its state depending on both agents' states, and the other agent may or may not be aware of the interaction. These notions can be combined, obtaining one-way protocols with (possibly detectable) omission failures. A general question is what additional power is necessary and sufficient to completely overcome the weakness of one-way protocols and enable them to simulate two-way protocols, with and without omission failures. As a basic feature, a simulator needs to implement an atomic communication of states between two agents; this task is further complicated by the anonymity of the agents, their lack of knowledge of the system, and the limited amount of memory that they may have. We provide the first answers to these questions by presenting and analyzing several simulators, i.e., wrapper protocols converting any protocol for the standard two-way model into one running on a weaker one.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Population Protocols with Faulty Interactions: the Impact of a Leader

We consider the problem of simulating traditional population protocols under weaker models of communication, which include one-way interactions (as opposed to two-way interactions) and omission faults (i.e., failure by an agent to read its partner's state during an interaction), which in turn may be detectable or undetectable. We focus on the impact of a leader, and we give a complete characterization of the models in which the presence of a unique leader in the system allows the construction of simulators: when simulations are possible, we give explicit protocols; when they are not, we give proofs of impossibility. Specifically, if each agent has only a finite amount of memory, the simulation is possible only if there are no omission faults. If agents have an unbounded amount of memory, the simulation is possible as long as omissions are detectable. If an upper bound on the number of omissions involving the leader is known, the simulation is always possible, except in the one-way model in which one side is unable to detect the interaction.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Improving Lower Bound on Opaque Set for Equilateral Triangle

An opaque set (or a barrier) for $U \subseteq \mathbb{R}^2$ is a set $B$ of finite-length curves such that any line intersecting $U$ also intersects $B$. In this paper, we consider the lower bound for the shortest barrier when $U$ is the unit equilateral triangle. The known best lower bound for triangles is the classic one by Jones [Jones,1964], which exhibits that the length of the shortest barrier for any convex polygon is at least the half of its perimeter. That is, for the unit equilateral triangle, it must be at least $3/2$. Very recently, this lower bounds are improved for convex $k$-gons for any $k\geq 4$ [Kawamura et al. 2014], but the case of triangles still lack the bound better than Jones' one. The main result of this paper is to fill this missing piece: We give the lower bound of $3/2 + 5 \cdot 10^{-13}$ for the unit-size equilateral triangle. The proof is based on two new ideas, angle-restricted barriers and a weighted sum of projection-cover conditions, which may be of independently interest.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Bitwise MAP Algorithm for Group Testing based on Holographic Transformation

In this paper, an exact bitwise MAP (Maximum A Posteriori) estimation algorithm for group testing problems is presented. We assume a simplest non-adaptive group testing scenario including N-objects with binary status and M-disjunctive tests. If a group contains a positive object, the test result for the group is assumed to be one; otherwise, the test result becomes zero. Our inference problem is to evaluate the posterior probabilities of the objects from the observation of M-test results and from our knowledge on the prior probabilities for objects. The heart of the algorithm is the dual expression of the posterior values. The derivation of the dual expression can be naturally described based on a holographic transformation to the normal factor graph (NFG) representing the inference problem.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A New Direction for Counting Perfect Matchings

In this paper, we present a new exact algorithm for counting perfect matchings, which relies on neither inclusion-exclusion principle nor tree-decompositions. For any bipartite graph of $2n$ nodes and $Δn$ edges such that $Δ\geq 3$, our algorithm runs with $O^{\ast}(2^{(1 - 1/O(Δ\log Δ))n})$ time and exponential space. Compared to the previous algorithms, it achieves a better time bound in the sense that the performance degradation to the increase of $Δ$ is quite slower. The main idea of our algorithm is a new reduction to the problem of computing the cut-weight distribution of the input graph. The primary ingredient of this reduction is MacWilliams Identity derived from elementary coding theory. The whole of our algorithm is designed by combining that reduction with a non-trivial fast algorithm computing the cut-weight distribution. To the best of our knowledge, the approach posed in this paper is new and may be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Emergent velocity agreement in robot networks

In this paper we propose and prove correct a new self-stabilizing velocity agreement (flocking) algorithm for oblivious and asynchronous robot networks. Our algorithm allows a flock of uniform robots to follow a flock head emergent during the computation whatever its direction in plane. Robots are asynchronous, oblivious and do not share a common coordinate system. Our solution includes three modules architectured as follows: creation of a common coordinate system that also allows the emergence of a flock-head, setting up the flock pattern and moving the flock. The novelty of our approach steams in identifying the necessary conditions on the flock pattern placement and the velocity of the flock-head (rotation, translation or speed) that allow the flock to both follow the exact same head and to preserve the flock pattern. Additionally, our system is self-healing and self-stabilizing. In the event of the head leave (the leading robot disappears or is damaged and cannot be recognized by the other robots) the flock agrees on another head and follows the trajectory of the new head. Also, robots are oblivious (they do not recall the result of their previous computations) and we make no assumption on their initial position. The step complexity of our solution is O(n).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Minimum Certificate Dispersal with Tree Structures

Given an n-vertex graph G=(V,E) and a set R \subseteq {{x,y} | x,y \in V} of requests, we consider to assign a set of edges to each vertex in G so that for every request {u, v} in R the union of the edge sets assigned to u and v contains a path from u to v. The Minimum Certificate Dispersal Problem (MCD) is defined as one to find an assignment that minimizes the sum of the cardinality of the edge set assigned to each vertex. This problem has been shown to be LOGAPX-complete for the most general setting, and APX-hard and 2-approximable in polynomial time for dense request sets, where R forms a clique. In this paper, we investigate the complexity of MCD with sparse (tree) structures. We first show that MCD is APX-hard when R is a tree, even a star. We then explore the problem from the viewpoint of the maximum degree Δof the tree: MCD for tree request set with constant Δis solvable in polynomial time, while that with Δ=Ω(n) is 2.56-approximable in polynomial time but hard to approximate within 1.01 unless P=NP. As for the structure of G itself, we show that the problem can be solved in polynomial time if G is a tree.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the Approximability and Hardness of Minimum Topic Connected Overlay and Its Special Instances

In the context of designing a scalable overlay network to support decentralized topic-based pub/sub communication, the Minimum Topic-Connected Overlay problem (Min-TCO in short) has been investigated: Given a set of t topics and a collection of n users together with the lists of topics they are interested in, the aim is to connect these users to a network by a minimum number of edges such that every graph induced by users interested in a common topic is connected. It is known that Min-TCO is NP-hard and approximable within O(log t) in polynomial time. In this paper, we further investigate the problem and some of its special instances. We give various hardness results for instances where the number of topics in which an user is interested in is bounded by a constant, and also for the instances where the number of users interested in a common topic is constant. For the latter case, we present a first constant approximation algorithm. We also present some polynomial-time algorithms for very restricted instances of Min-TCO.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Physical expander in Virtual Tree Overlay

In this paper, we propose a new construction of constantdegree expanders motivated by their application in P2P overlay networks and in particular in the design of robust trees overlay. Our key result can be stated as follows. Consider a complete binary tree T and construct a random pairing Π between leaf nodes and internal nodes. We prove that the graph GΠobtained from T by contracting all pairs (leaf-internal nodes) achieves a constant node expansion with high probability. The use of our result in improving the robustness of tree overlays is straightforward. That is, if each physical node participating to the overlay manages a random pair that couples one virtual internal node and one virtual leaf node then the physical-node layer exhibits a constant expansion with high probability. We encompass the difficulty of obtaining this random tree virtualization by proposing a local, selforganizing and churn resilient uniformly-random pairing algorithm with O(log2 n) running time. Our algorithm has the merit to not modify the original tree virtual overlay (we just control the mapping between physical nodes and virtual nodes). Therefore, our scheme is general and can be applied to a large number of tree overlay implementations. We validate its performances in dynamic environments via extensive simulations.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The BG-simulation for Byzantine Mobile Robots

This paper investigates the task solvability of mobile robot systems subject to Byzantine faults. We first consider the gathering problem, which requires all robots to meet in finite time at a non-predefined location. It is known that the solvability of Byzantine gathering strongly depends on a number of system attributes, such as synchrony, the number of Byzantine robots, scheduling strategy, obliviousness, orientation of local coordinate systems and so on. However, the complete characterization of the attributes making Byzantine gathering solvable still remains open. In this paper, we show strong impossibility results of Byzantine gathering. Namely, we prove that Byzantine gathering is impossible even if we assume one Byzantine fault, an atomic execution system, the n-bounded centralized scheduler, non-oblivious robots, instantaneous movements and a common orientation of local coordinate systems (where n denote the number of correct robots). Those hypotheses are much weaker than used in previous work, inducing a much stronger impossibility result. At the core of our impossibility result is a reduction from the distributed consensus problem in asynchronous shared-memory systems. In more details, we newly construct a generic reduction scheme based on the distributed BG-simulation. Interestingly, because of its versatility, we can easily extend our impossibility result for general pattern formation problems.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Gathering Problem for Two Oblivious Robots with Unreliable Compasses

Anonymous mobile robots are often classified into synchronous, semi-synchronous and asynchronous robots when discussing the pattern formation problem. For semi-synchronous robots, all patterns formable with memory are also formable without memory, with the single exception of forming a point (i.e., the gathering) by two robots. However, the gathering problem for two semi-synchronous robots without memory is trivially solvable when their local coordinate systems are consistent, and the impossibility proof essentially uses the inconsistencies in their coordinate systems. Motivated by this, this paper investigates the magnitude of consistency between the local coordinate systems necessary and sufficient to solve the gathering problem for two oblivious robots under semi-synchronous and asynchronous models. To discuss the magnitude of consistency, we assume that each robot is equipped with an unreliable compass, the bearings of which may deviate from an absolute reference direction, and that the local coordinate system of each robot is determined by its compass. We consider two families of unreliable compasses, namely,static compasses with constant bearings, and dynamic compasses the bearings of which can change arbitrarily. For each of the combinations of robot and compass models, we establish the condition on deviation ϕthat allows an algorithm to solve the gathering problem, where the deviation is measured by the largest angle formed between the x-axis of a compass and the reference direction of the global coordinate system: ϕ< π/2 for semi-synchronous and asynchronous robots with static compasses, ϕ< π/4 for semi-synchronous robots with dynamic compasses, and ϕ< π/6 for asynchronous robots with dynamic compasses. Except for asynchronous robots with dynamic compasses, these sufficient conditions are also necessary.

0 citations0 reviewsNo code linkedOpen access