記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：International Conference on Probabilistic, Combinatorial and Asymptotic Methods |rn|for the Analysis of Algorithms  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Society for Industrial and Applied Mathematics  

DOI： 10.1137/1.9781611974324.13

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Hungarian-Japanese Symposium|rn|on Discrete Mathematics and Its Applications  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：SPRINGER INT PUBLISHING AG  

Distributed voting is a fundamental topic in distributed computing. In the standard model of pull voting, at each step every vertex chooses a neighbour uniformly at random and adopts its opinion. The voting is completed when all vertices hold the same opinion. In the simplest case, each vertex initially holds one of two different opinions. This partitions the vertices into arbitrary sets A and B. For many graphs, including regular graphs and irrespective of their expansion properties, if both A and B are sufficiently large sets, then pull voting requires Omega(n) expected steps, where n is the number of vertices of the graph.
In this paper we consider a related class of voting processes based on sampling two opinions. In the simplest case, every vertex v chooses two random neighbours at each step. If both these neighbours have the same opinion, then v adopts this opinion. Otherwise, v keeps its own opinion. Let G be a connected graph with n vertices and m edges. Let P be the transition matrix of a simple random walk on G with second largest eigenvalue lambda < 1/root 2. We show that if the initial imbalance in degree between the two opinions satisfies vertical bar d(A) - d(B)vertical bar/2m >= 2 lambda(2), then with high probability voting completes in O(log n) steps, and the opinion with the larger initial degree wins.
The condition that lambda < 1/root 2 includes many classes of expanders, for example random d-regular graphs where d >= 10. If however 1/root 2 <= lambda(P) <= 1 - epsilon for a constant epsilon > 0, or only a bound on the conductance of the graph is known, the sampling process can be modified so that voting still provably completes in O(log n) steps with high probability. The modification uses two sampling based on probing to a fixed depth O(1/epsilon) from any vertex.
In its most general form our voting process allows vertices to bias their sampling of opinions among their neighbours to achieve a desired outcome. This is done by allocating weights to edges.

DOI： 10.1007/978-3-662-48653-5_17

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Springer Verlag  

We consider the rotor-router mechanism for distributing particles in an undirected graph. If the last particle passing through a vertex v took an edge (v,u), then the next time a particle is at v, it will leave v along the next edge (v,w) according to a fixed cyclic order of edges adjacent to v. The system works in synchronized steps and when two or more particles meet at the same vertex, they coalesce into one particle. A k-particle configuration of such a system is stable, if it does not lead to any coalescing. For 2≤k≤n, we give the full characterization of stable k-particle configurations for cycles. We also show sufficient conditions for regular graphs with n vertices to admit n-particle stable configurations.

DOI： 10.1007/978-3-319-25258-2_31

Scopus

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Springer International Publishing  

DOI： 10.1007/978-3-319-08783-2_3

Web of Science

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap