Modeling the spread of fault in majority-based network systems: Dynamic monopolies in triangular grids

被引:10
作者
Adams, Sarah Spence [2 ]
Booth, Paul [2 ]
Troxell, Denise Sakai [1 ]
Zinnen, S. Luke [2 ]
机构
[1] Babson Coll, Div Math & Sci, Babson Pk, MA 02457 USA
[2] Franklin W Olin Coll Engn, Needham, MA 02492 USA
基金
美国国家科学基金会;
关键词
Spread of fault; Spread of disease; Dynamic Monopoly; Dynamo; Triangular grid;
D O I
10.1016/j.dam.2012.02.011
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
In a graph theoretical model of the spread of fault in distributed computing and communication networks, each element in the network is represented by a vertex of a graph where edges connect pairs of communicating elements, and each colored vertex corresponds to a faulty element at discrete time periods. Majority-based systems have been used to model the spread of fault to a certain vertex by checking for faults within a majority of its neighbors. Our focus is on irreversible majority processes wherein a vertex becomes permanently colored in a certain time period if at least half of its neighbors were in the colored state in the previous time period. We study such processes on planar, cylindrical, and toroidal triangular grid graphs. More specifically, we provide bounds for the minimum number of vertices in a dynamic monopoly defined as a set of vertices that, if initially colored, will result in the entire graph becoming colored in a finite number of time periods. (C) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码:1624 / 1633
页数:10
相关论文
共 15 条
[1]   Combinatorial model and bounds for target set selection [J].
Ackerman, Eyal ;
Ben-Zwi, Oren ;
Wolfovitz, Guy .
THEORETICAL COMPUTER SCIENCE, 2010, 411 (44-46) :4017-4022
[2]  
Adams S.S., 2011, ARXIV11025361V1
[3]   Dynamic monopolies and feedback vertex sets in hexagonal grids [J].
Adams, Sarah Spence ;
Troxell, Denise Sakai ;
Zinnen, S. Luke .
COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2011, 62 (11) :4049-4057
[4]   Dynamic monopolies of constant size [J].
Berger, E .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2001, 83 (02) :191-200
[5]  
Chang CL, 2010, LECT NOTES COMPUT SC, V6078, P109, DOI 10.1007/978-3-642-13073-1_11
[6]   Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion [J].
Dreyer, Paul A., Jr. ;
Roberts, Fred S. .
DISCRETE APPLIED MATHEMATICS, 2009, 157 (07) :1615-1627
[7]   Dynamic monopolies in tori [J].
Flocchini, P ;
Lodi, E ;
Luccio, F ;
Pagli, L ;
Santoro, N .
DISCRETE APPLIED MATHEMATICS, 2004, 137 (02) :197-212
[8]   Optimal irreversible dynamos in chordal rings [J].
Flocchini, P ;
Geurts, F ;
Santoro, N .
DISCRETE APPLIED MATHEMATICS, 2001, 113 (01) :23-42
[9]  
HARTKE SG, 2004, THESIS RUTGERS U
[10]  
Kempe D., 2015, PROC ACM SIGKDD INT, V11, P105