In particular, the thesis will focus on parameterized networks of discrete-event systems. These are collections of interacting, isomorphic subsystems, where the number of subsystems is, for practical purposes, arbitrary; thus, the system parameter of interest is, in this case, the size of the network as characterized by the number of subsystems. Parameterized networks are reasonable models of real systems where the number of subsystems is large, unknown, or time-varying: examples include communication, computer and transportation networks. Intuition and engineering practice suggest that, in checking properties of such networks , it should be sufficient to consider a ``testbed'' network of limited size. However, there is presently little rigorous support for such an approach.
In general, the problem of deciding whether a temporal property holds for a parameterized network of finite-state systems is undecidable; and the only decidable subproblems that have so far been identified place unreasonable restrictions on the means by which subsystems may interact. The key to ensuring decidability, and therefore the existence of effective solutions to the problem, is to identify restrictions that limit the computational power of the network. This can be done not only by limiting communication but also by restricting the structure of individual subsystems. In this thesis, we take both approaches, and also their combination on two different network topologies: ring networks and fully connected networks.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/4136 |
| Date | January 2008 |
| Creators | Nazari, Siamak |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.002 seconds