This paper deals with the on-line control of partially observed discrete event systems (DES). The goal is to restrict the behavior of the system within a prefix-closed legal language while accounting for the presence ...
详细信息
This paper deals with the on-line control of partially observed discrete event systems (DES). The goal is to restrict the behavior of the system within a prefix-closed legal language while accounting for the presence of uncontrollable and unobservable events. In the spirit of recent work on the on-line control of partially observed DES (Heymann and Lin 1994) and on variable lookahead control of fully observed DES (Ben Hadj-Alouane et al. 1994c), we propose an approach where, following each observable event, a control action is computed on-line using an algorithm of linear worst-case complexity. This algorithm, called VLP-PO, has the following additional properties: (i) the resulting behavior is guaranteed to be a maximal controllable and observable sublanguage of the legal language;(ii) different maximals may be generated by varying the priorities assigned to the controllable events, a parameter of VLP-PO;(iii) a maximal containing the supremal controllable and normal sublanguage of the legal language can be generated by a proper selection of controllable event priorities;and (iv) no off-line calculations are necessary. We also present a parallel/distributed version of the VLP-PO algorithm called DI-VLP-PO. This version uses several communicating agents that simultaneously run (on-line) identical versions of the algorithm but on possibly different parts of the system model and the legal language, according to the structural properties of the system and the specifications. While achieving the same behavior as VLO-PO, DI-VLP-PO runs at a total complexity (for computation and communication) that is significantly lower than its sequential counterpart.
During the last decade, the availability of large amounts of social network information from various social and socio-technical networks has increased dramatically. These data sources are inherently dynamic with const...
详细信息
ISBN:
(纸本)9781728174457
During the last decade, the availability of large amounts of social network information from various social and socio-technical networks has increased dramatically. These data sources are inherently dynamic with constantly evolving relationships and connections between entities. Research in this area must address the challenge of analyzing these dynamic datasets under potentially strict time constraints. In addition, due to the sheer size of these networks, they tend to be stored and analyzed on distributed platforms. In our previous work, we designed methodologies which are anytime and anywhere to design scalable parallel/distributed algorithms that incorporate different forms of network changes. In this work, we will investigate various schemas to balance the incorporation of dynamic network changes that will substantially reduce idleness and load imbalances among processors. We will show theoretically that in most cases our buffer-based methodology performs better than the more common way of handling changes as they come in.
We study a simple random process that computes a maximal independent set (MIS) on a general n-vertex graph. Each vertex has a binary state, black or white, where black indicates inclusion into the MIS. The vertex stat...
详细信息
ISBN:
(纸本)9798400701214
We study a simple random process that computes a maximal independent set (MIS) on a general n-vertex graph. Each vertex has a binary state, black or white, where black indicates inclusion into the MIS. The vertex states are arbitrary initially, and are updated in parallel: In each round, every vertex whose state is "inconsistent" with its neighbors, i.e., it is black and has a black neighbor, or it is white and all neighbors are white, changes its state with probability 1/2. The process stabilizes with probability 1 on any graph, and the resulting set of black vertices is an MIS. We show that the expected stabilization time is O(log n) on certain graph families, such as cliques and graphs of bounded arboricity. Our main result is that the process stabilizes in poly(log n) rounds w.h.p. on G(n,p) random graphs, for 0 <= p <= poly(log n) . n(-1/2) or p >= 1/poly(log n). Further, we propose an extension of this process, with larger but still constant vertex state space, which stabilizes in poly(log n) rounds on G(n,p) w.h.p., for all 1 <= p <= 1. Both processes readily translate into distributed/parallel MIS algorithms, which are self-stabilizing, use constant space (and constant random bits per round), and assume restricted communication as in the beeping or the synchronous stone age models. To the best of our knowledge, no previously known MIS algorithm is self-stabilizing, uses constant space and constant randomness, and stabilizes in poly(log n) rounds on G(n,p) random graphs.
暂无评论