Skip to main content
Article
Modeling the Spread of Fault in Majority-Based Network Systems: Dynamic Monopolies in Triangular Grids
Discrete Applied Mathematics (2012)
  • Sarah Spence Adams
  • Paul Booth
  • Denise Sakai Troxell, Babson College
  • Luke Zinnen
Abstract

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 monopolydefined as a set of vertices that, if initially colored, will result in the entire graph becoming colored in a finite number of time periods.

Keywords
  • Spread of fault; Spread of disease; Dynamic Monopoly; Dynamo; Triangular grid
Disciplines
Publication Date
July 1, 2012
Publisher Statement

© 2012 Elsevier. This article was published in Discrete Applied Mathematics, vol. 160, iss. 10-11, pg. 1624-1633 and may be found here.

Citation Information
Sarah Spence Adams, Paul Booth, Denise Sakai Troxell and Luke Zinnen. "Modeling the Spread of Fault in Majority-Based Network Systems: Dynamic Monopolies in Triangular Grids" Discrete Applied Mathematics Vol. 160 Iss. 10-11 (2012)
Available at: http://works.bepress.com/sarah_spence_adams/21/