Opacity of a discrete event system is a confidentiality property that characterizes instances when the secret behavior of the system cannot be revealed. This paper considers current-state opacity with respect to a set of secret states, and addresses the opacity enforcement problem via modification functions that are capable of replacing in real-time the output of the underlying system with another output, aiming to prevent the intruder from inferring the secret. We study modification functions that are constrained, i.e., they may not be able to modify certain outputs or they may have restrictions in how they modify a particular output. A system is said to be emc-enforceable if opacity can be enforced via modification functions under the given event modification constraints (emc). To verify whether a system is emc-enforceable, we construct a verifier, based on which a necessary and sufficient condition is obtained. If a system is emc-enforceable, an algorithm is developed to compute a modification strategy based on the verifier to enforce opacity. For m-enforceability, a special case of emc-enforceability without constraints, two necessary and sufficient conditions to verify and enforce opacity with reduced complexity are presented, one based on a system estimator and the other based on a detector. Note to Practitioners—Discrete event systems provide appropriate mathematical models for analysing information-flow properties of cyber-physical systems, such as intelligent transportation systems, command-control systems, and networked communication systems, in dynamically changing environments. Opacity is a general property capable of capturing safe information-flow in a cyber-physical system. This article targets the enforcement of opacity using modification functions that mask the output of the system into another output in a manner that appears consistent to an external observer as the system evolves. The designed modification function can be realized via triggers equipped with digital logic and storage functionality. As an output is generated by a system, a trigger displays a fake output based on the stored real and fake states.

This paper addresses the property of critical observability in labeled Petri nets. A system is deemed critically observable if its state estimate (formed by observing the system output) can be determined to belong to a set of either critical markings or non-critical markings. More generally, for a critically observable system, there may be multiple types of critical markings and the operator may desire to know the type to which the current state estimate belongs. We propose a generalized version of critical observability, namely generalized critical observability, and provide two necessary and sufficient conditions to check it based on basis markings and integer linear programs, effectively circumventing the need for an exhaustive enumeration of all reachable markings of the net. In addition, we investigate (generalized) critical observability of Petri nets under nondeterministic observations, which may arise due to the loss of transmission signals or due to interference with sensor measurement outputs. To handle this, an augmented system is constructed from the original Petri net by adding new transitions that capture the effect of transitions associated with nondeterministic labels. Thus, we transform the verification of (generalized) critical observability of a Petri net under nondeterministic observations to that of the augmented model. Two real-world examples illustrate the applicability of the presented notion and methodology.

In this article, we introduce a novel weighted digraph, namely, a resource requirement graph, to address deadlock problems in flexible manufacturing systems (FMSs) modeled with Petri nets. A liveness-enforcing supervisor consisting of recovery transitions designed to be enabled at pre-partial deadlocks is synthesized. First, a resource requirement graph is directly derived from a Petri net model of an FMS and is used to represent competition relations for shared resources by various processes. Subsequently, the notion of pre-partial deadlock, described as a set of linear inequalities, is introduced by analyzing a resource requirement graph. Then, an algorithm is presented to develop a supervisor consisting of recovery transitions that are only enabled at the identified pre-partial deadlocks. The controlled Petri net model of an FMS under the designed supervisor is shown to be live with all initial reachable markings retained. The method proposed in this article offers computational efficiency since the resource requirement graph is structurally compact compared to its counterpart net model. Finally, several examples are provided to demonstrate the developed techniques.

Various aspects of security and privacy in many application domains can be assessed based on proper analysis of successive measurements that are collected on a given system. This work is devoted to such issues in the context of timed stochastic Petri net models. We assume that certain events and part of the marking trajectories are observable to adversaries who aim to determine when the system is performing secret operations, such as time intervals during which the system is executing certain critical sequences of events (as captured, for instance, in language-based opacity formulations). The combined use of the k-step trajectory-observer and the Markov model of the stochastic Petri net leads to probabilistic indicators helpful for evaluating language-based opacity of the given system, related timing aspects, and possible strategies to improve them.

The reliance of many emerging applications on shared cyber-infrastructures has prompted the study of various notions for security and privacy, including notions for deterministic, non-deterministic, and probabilistic systems. The main contribution of this work is to extend these ideas to timed stochastic systems, by introducing and analyzing timing aspects of initial-state opacity, as measures of vulnerability to security violations. More specifically, we consider partially observed stochastic Petri net (POSPN) models that behave according to Markovian dynamics. We assume that certain events are observable to an outside observer (intruder) and we are interested in initial-state opacity, i.e., determining whether an intruder can infer that the initial marking of the system necessarily lies within a given secret set of initial states. In case initial-state opacity is violated for some behavior in the system, we are also interested in knowing how much time the system remains safe before this violation occurs.

Discrete event systems (DES) are event-driven systems whose state evolutions are determined by occurrences of asynchronous events. Examples include a variety of systems from domains as diverse as transportation, automated manufacturing, process control, communication and networking, security protocols, and others. This talk discusses the recursive algorithms for state estimation and event inference in DES, which are key tasks for proper monitoring and control of such systems, as well as the verification of properties of interest, such as diagnosability and opacity. The verification of such properties becomes even more challenging in emerging distributed settings where there may exist multiple interacting systems and multiple monitors, with diverse (and possibly unreliable) observation and communication capabilities. The talk discusses recent progress on distributed state estimation and event inference in emerging interconnected DES, as well as efficient ways for verifying properties of interest, such as diagnosability (i.e., the ability to detect within finite time the occurrence/type of a fault) and opacity (i.e., the guarantee that outsiders will never be able to infer that the system lies within a certain of certain secret/critical states).

This paper provides revisions to the algorithms presented by Chen et al., 2013 for testing diagnosability of stochastic discrete-event systems. Additional new contributions include PSPACE-hardness of verifying strong stochastic diagnosability (referred as A-Diagnosability in Thorsley et al., 2005) and a necessary and sufficient condition for testing stochastic diagnosability (referred as AA-Diagnosability in Thorsley et al., 2005) that involves a new notion of probabilistic equivalence.

In this paper we consider the problem of designing a state feedback controller for a labeled Petri net whose initial marking is known to belong to a given convex set. We allow for silent transitions (i.e., transitions labeled with the empty word) and indistinguishable transitions (i.e., transitions sharing the same label with other transitions). Transitions that are neither silent nor indistinguishable, are said to be observable since the observation of their label univocally identifies them. Moreover, we divide the set of observable transitions into controllable and uncontrollable (all unobservable transitions are obviously uncontrollable). Based on our previous results on marking observation in the above setting, we show how to derive, at design time, a state feedback control law; this way, the most burdensome part of the computations, is performed off-line.

In many emerging security applications, a property of a system, that may reveal important details about its behaviour, needs to be kept secret (opaque) to outside observers (intruders). Motivated by such applications, several authors have formalized, analyzed, and described methods to verify notions of opacity in discrete event systems of interest. This paper offers a review of various definitions of opacity, along with methodologies for their verification and complexity analysis. We review state-based notions of opacity (namely, current-state opacity and initial-state opacity) in non-deterministic finite automata, as well as their extensions to stochastic settings. Specifically, we discuss these notions of opacity and methods to verify them in discrete event systems modeled by non-deterministic finite automata (NFA's) or probabilistic finite automata (PFA's).

The 12 papers in this special section can be divided into two sets. The first eight papers deal with general DES control problems, while the second set of four papers addresses other particular DES problems such as diagnosability analysis, state estimation, deadlock avoidance and testing.

A non-deterministic finite automaton is initial-state opaque if the membership of its true initial state to a given set of secret states S remains opaque (i.e., uncertain) to an intruder who observes system activity through some natural projection map. By establishing that the verification of initial state opacity is equivalent to the language containment problem, earlier work has established that the verification of initial state opacity is a PSPACE-complete problem. In this paper, motivated by the desire to incorporate probabilistic (likelihood) information, we extend the notion of initial state opacity to stochastic discrete event systems. Specifically, we consider systems that can be modeled as probabilistic finite automata, and introduce and analyze the notions of almost initial state opacity and step-based almost initial state opacity, both of which hinge on the a priori probability that the given system generate behavior that violates initial-state opacity. We also discuss how almost initial state opacity and step-based almost initial state opacity can be verified, and analyze the complexity of the proposed verification methods.

In this paper we consider marking estimation in labeled Petri nets whose initial marking is known to belong to a given convex set. We allow for silent transitions (i.e., transitions labeled with the empty word) and indistinguishable transitions (i.e., transitions sharing the same label with other transitions). We demonstrate that all sets of markings consistent with a given sequence of observations can be described in linear algebraic terms (as a union of convex sets) and a marking observer may be constructed offline under appropriate bounded ness assumptions. This reduces the problem of computing the set of markings consistent with a given observation sequence to the problem of moving along a path in a labeled directed graph.

This paper considers networked systems and develops distributed algorithm that is resilient against potential packet drops in the communication links between system components. We apply this algorithm to the problem of coordinating distributed energy resources (DERs) for the provision of ancillary services in electrical networks, e.g., reactive power support for voltage control. In this problem, each system component can contribute a certain amount of active and/or reactive power, bounded from above and (possibly) below by capacity constraints, and the objective is to coordinate the components so as to collectively provide a predetermined total amount of active and/or reactive power. In the algorithm we propose to address this problem, each DER maintains a set of variables and updates them through information exchange with neighboring DERs. We show that, as long as the underlying graph that describes the information exchange between components is strongly connected, and the predetermined total amount of active and/or reactive power does not violate (upper or lower) total capacity constraints, DERs can use this approach to calculate, in a distributed fashion, their fair contribution (subject to their capacity constraints). We show that the proposed algorithms reach almost surely convergence to the fair solution, even in the presence of communication link failures.

Nowadays, there is an increasing demand for wireless and mobile networks that guarantee secure and reliable data communication among users. To enable data exchanges, authentication mechanisms need to be in place to dynamically verify the identity of communicating parties. Authentication is used as a base to deploy security mechanisms and exchange information. However, authentication is static and it does not provide any information regarding the trustworthiness of communicating peers. Trust is a complex issue as it lies in the complexity of human behavior. Trust has typically been evaluated by measuring individual performance on a specific functionality or generally measuring specific behavior and translating it to a trust value. In this paper we define properties and requirements for trust at the individual and system level. Contrary to previous work, we consider trust in a non-linear manner that matches behavior in social networks. In addition, trust evaluations do not only take into account individual behavior independently, but also focus on its impact on the system. Finally, we present a novel 3-d trust model that is structured to reflect the overall trustworthiness of a system and responds to changes in node behavior. It provides a simplified and concurrently dynamic way of aggregating and representing trust and can be used to guide network functionalities, such as routing, or more generally evaluate trust in collaborative modes of interaction among individuals. An example application is also provided.

This paper proposes an approach for estimating the least-cost transition firing sequence(s) that matches (match) the observation of a sequence of labels produced by transition activity in a given labeled Petri net. Each transition in the labeled net is associated with a (possibly empty) label and also with a nonnegative cost which captures its likelihood (e.g., in terms of the amount of workload or power required to execute the transition). Given full knowledge of the structure of the labeled Petri net and the observation of a sequence of labels, we aim at finding the transition firing sequence(s) that is (are) consistent with both the observed label sequence and the Petri net, and also has (have) the least total cost (i.e., the least sum of individual transition costs). The existence of unobservable transitions makes this task extremely challenging since the number of firing sequences that might be consistent can potentially be infinite. Under the assumption that the unobservable transitions in the net form an acyclic subnet and have strictly positive costs, we develop a recursive algorithm that is able to find the least-cost firing sequence(s) by reconstructing only a finite number of firing sequences. In particular, if the unobservable transitions in the net are contact-free, the proposed recursive algorithm finds the least-cost transition firing sequences with complexity that is polynomial in the length of the observed sequence of labels.

Motivated by security and privacy considerations in a variety of applications of discrete event systems, we describe and analyze the computational complexity required for verifying the notion ofK-step opacity for systems that are modeled as nondeterministic finite automata with partial observation on their transitions. Specifically, a system isK-step opaque if, at any specific point within the lastKobservations, the entrance of the system state to a given set of secret states remains opaque (uncertain) to an intruder who has complete knowledge of the system model and observes system activity through some natural projection map. We provide two methods for verifyingK-step opacity using two different state estimator constructions, and analyze the computational complexity of both.

In this paper, we consider state estimation in discrete-event systems (DESs) modeled by labeled Petri nets and present upper bounds on the number of system states (or markings) that are consistent with an observed sequence of labels. Our analysis is applicable to Petri nets that may have nondeterministic transitions (i.e., transitions that share the same label) and/or unobservable transitions (i.e., transitions that are associated with the null label). More specifically, given knowledge of a labeled Petri net structure and its initial state, we show that the number of consistent markings in a Petri net with nondeterministic transitions is at most polynomial in the length of the observation sequence (i.e., polynomial in the number of labels observed). This polynomial dependency of the number of consistent markings on the length of the observation sequence also applies to Petri nets with unobservable transitions under the assumption that their unobservable subnets are structurally bounded. The bounds on the number of markings established in this paper imply that the state estimation problem in labeled Petri nets can be solved with complexity that is polynomial in the length of the observation sequence.

In this paper, we propose low-complexity max-product algorithms for the problem of multiple fault diagnosis (MFD). The MFD problem is described by a bipartite diagnosis graph (BDG) which consists of a set of components, a set of alarms and a set of connections (or causal dependencies) between them. Given the alarm observations, along with a probabilistic description of the system and the dependencies among components, our goal is to find the combination of component states that has the maximum a posteriori (MAP) probability. Iterative belief propagation max-product algorithms (developed in our earlier work for the MFD problem) work well on systems associated with sparse BDGs (especially when connections and/or alarms are unreliable). However, these iterative algorithms are exponentially dependent on the maximum number of components per alarm and hence, not suitable for many practical applications. In this paper, by limiting during each iteration the maximum number of possibly faulty components per alarm, we study low-complexity versions of these existing max-product algorithms. On acyclic bipartite graphs, we show that under certain conditions on the solutions, the low-complexity algorithms are guaranteed to return the MAP solution. For arbitrary bipartite graphs, our experimental results indicate that the proposed algorithms still perform comparably to the original (more computationally expensive) algorithms.

Given an arbitrary network of interconnected nodes, we develop and analyze a distributed strategy that enables a subset of the nodes to calculate any given function of the node values. Our scheme utilizes a linear iteration where, at each time-step, each node updates its value to be a weighted average of its own previous value and those of its neighbors. We show that this approach can be viewed as a linear dynamical system, with dynamics that are given by the weight matrix of the linear iteration, and with outputs for each node that are captured by the set of values that are available to that node at each time-step. In connected networks with time-invariant topologies, we use observability theory to show that after running the linear iteration for a finite number of time-steps with almost any choice of weight matrix, each node obtains enough information to calculate any arbitrary function of the initial node values. The problem of distributed consensus via linear iterations, where all nodes in the network calculate the same function, is treated as a special case of our approach. In particular, our scheme allows nodes in connected networks with time-invariant topologies to reach consensus on any arbitrary function of the initial node values in a finite number of steps for almost any choice of weight matrix.

In this paper we consider the transmission of discrete-valued data via a communication channel that is subject to (additive) noise with a known upper bound on its magnitude but otherwise completely unrestricted and unknown behavior. We consider a discrete-time setup and extend previous equalization strategies for perfect reconstruction by allowing linear preprocessing of the data and/or linear feedback from the receiver to the transmitter. We are interested in the characterization of general conditions that allow perfect reconstruction of the discrete data with any given (possibly nonzero) delay (and under all possible realizations of channel noise and a limit on the power of transmission) when linear preprocessing of the data and/or linear feedback from the receiver is employed. In particular, we obtain necessary and sufficient conditions for perfect reconstruction under either linear power-limited preprocessing or linear power- limited preprocessing along with linear feedback. We prove that in order to improve the conditions for perfect reconstruction, it is necessary that the feedback and preprocessing systems are unstable. We also consider the case when a Decision Feedback Equalizer (DFE) structure is imposed at the receiver and provide necessary conditions for improvements in the perfect reconstruction in terms of l1norms of appropriate maps. In addition, a procedure that results in parametric l1optimization is developed to design a DFE to improve the maximum tolerable noise bound.

The Lee metric measures the circular distance between two elements in a cyclic group and is particularly appropriate as a measure of distance for data transmission under phase-shift-keying modulation over a white noise channel. In this paper, using newly derived properties on Newton's identities, we initially investigate the Lee distance properties of a class of BCH codes and show that (for an appropriate range of parameters) their minimum Lee distance is at least twice their designed Hamming distance. We then make use of properties of these codes to devise an efficient algebraic decoding algorithm that successfully decodes within the above lower bound of the Lee error-correction capability. Finally, we propose an attractive design for the corresponding VLSI architecture that is only mildly more complex than popular decoder architectures under the Hamming metric; since the proposed architecture can also be used for decoding under the Hamming metric without extra hardware, one can use the proposed architecture to decode under both distance metrics (Lee and Hamming).

In this paper, we consider vulnerabilities of networked systems and develop a multiple intrusion detection system (MIDS) which operates by running belief propagation on an appropriately constructed weighted bipartite graph. In this bipartite graph, one set of nodes represents the different types of intrusions that are possible, the other set of nodes represents the set of significant measures that are available, and the (weighted) connections represent the dependence of a certain measure on a particular type of intrusion. We assume that the effect of each active intrusion on a particular significant measure is superimposed on the normal operation of that measure; thus, we are able to obtain a complete representation of the overall bipartite graph model by superimposing the simpler graphs associated with each individual intrusion. The key ingredient of our MIDS is the development of a modified belief propagation max-product algorithm (MPA) that avoids the exponential complexity of the original MPA by limiting, during the iteration process, the number of active intrusions that are connected to a particular measure. Our simulation results indicate that the proposed MIDS performs well in detecting both single and multiple intrusions with a very low false alarm rate.

This paper proposes an approach for providing tolerance against faults that may compromise the functionality of a given controller modeled by a Petri net. The method is based on embedding the given Petri net controller into a larger (redundant) Petri net controller that retains the original functionality and properties, and uses additional places, connections, and tokens to impose invariant conditions that allow the systematic detection and identification of faults via linear parity checks. In particular, this paper considers two types of redundant Petri net controllers: 1) nonseparate redundant Petri net controllers have the same functionality as the given Petri net controller and allow for fault detection and identification, but do not necessarily retain the given controller intact; and 2) separate redundant Petri net controllers are a special case of the nonseparate redundant controllers that retain the given Petri net controller intact but enhance it with additional places to enable fault detection and identification. The work in this paper obtains complete characterizations of both types of redundant controllers along with necessary and sufficient conditions for them to be bisimulation equivalent to the given original Petri net controller. In addition, this paper discusses how each type of redundant controllers can be designed to have desirable fault detection and identification capabilities. When the bisimulation equivalence requirement is not directly enforced, nonseparate redundant controllers can potentially have advantages over separate ones (e.g., they can use fewer connections to detect and identify the same number of faults). An example of a Petri net controller for a production cell and its fault tolerance capabilities using separate and nonseparate embeddings is used to illustrate the approach.

We study the problem of performing sensor fusion and distributed consensus in networks, where the objective is to calculate some linear function of the initial sensor values at some or all of the sensors. We utilize a linear iteration where, at each time-step, each sensor updates its value to be a weighted average of its own previous value and those of its neighbors. We show that this approach can be viewed as a linear dynamical system, with dynamics that are given by the weight matrix for the linear iteration, and with outputs for each sensor that are captured by the subset of the state vector that is measurable by that sensor. We then cast the fusion and consensus problems as that of observing a linear functional of the initial state vector using only local measurements (that are available at each sensor). When the topology of the network is time-invariant, we show that the weight matrix can be chosen so that each sensor can calculate the desired function as a linear combination of its measurements over a finite number of time-steps.

Order-w reprocessing is a suboptimal soft-decision decoding approach for binary linear block codes in which up to w bits are systematically flipped on the so-called most reliable (information) basis (MRB). This correspondence first incorporates two preprocessing rules into order-w reprocessing and shows that, with appropriate choice of parameters, the proposed order-w reprocessing with preprocessing requires comparable complexity to order-w reprocessing but achieves asymptotically the performance of order-(w+2) reprocessing. To complement the MRB, a second basis is employed for practical SNRs and this approach is systematically extended to a multibasis order-w reprocessing scheme for high signal-to-noise ratios (SNRs). It is shown that the proposed multibasis scheme significantly enlarges the error-correction radius, a commonly used measure of performance at high SNRs, over the original (single-basis) order-w reprocessing. As a by-product, this approach also precisely characterizes the asymptotic performance of the well-known Chase and generalized minimum distance (GMD) decoding algorithms. The proposed algorithm successfully decodes the (192,96) Reed-Solomon concatenated code and the (256,147) extended BCH code in near optimal manner (within 0.01 dB at a block-error rate of 10-5) with affordable computational cost

This correspondence investigates soft-decision decoding of binary linear block codes using ordered recodings of test error patterns on the so-called "most reliable basis." The analysis demonstrates the optimality of the most reliable basis by showing that, among all possible bases, the most reliable basis minimizes the list error probability for a very general (and well-defined) class of orderings for recoding operations. The correspondence then proposes a suboptimal algorithm which utilizes reprocessing ordering and incorporates two techniques that render it computationally very efficient: 1) an iterative reference recoding technique which simplifies the recoding operation required for each test error pattern, and 2) an adaptive skipping rule which significantly reduces the average number of recodings. Simulation results with codes of relatively large length show that the proposed algorithm is computationally very efficient in comparison to existing algorithms in the literature

In this paper, we study the application of the max-product algorithm (MPA) to the generalized multiple-fault diagnosis (GMFD) problem, which consists of components (to be diagnosed) and alarms/connections that can be unreliable. The MPA and the improved sequential MPA (SMPA) that we develop in this paper are local-message-passing algorithms that operate on the bipartite diagnosis graph (BDG) associated with the GMFD problem and converge to the maximum a posteriori probability (MAP) solution if this graph is acyclic (in addition, the MPA requires the MAP solution to be unique). Our simulations suggest that both the MPA and the SMPA perform well in more general systems that may exhibit cycles in the associated BDGs (the SMPA also appears to outperform the MPA in these more general systems). In this paper, we provide analytical results for acyclic BDGs and also assess the performance of both algorithms under particular patterns of alarm observations in general graphs; this allows us to obtain analytical bounds on the probability of making erroneous diagnosis with respect to the MAP solution. We also evaluate the performance of the MPA and the SMPA algorithms via simulations, and provide comparisons with previously developed heuristics for this type of diagnosis problems. We conclude that the MPA and the SMPA perform well under reasonable computational complexity when the underlying diagnosis graph is sparse.

In this paper, we study the application of decoding algorithms to the multiple fault diagnosis (MFD) problem. Prompted by the resemblance between graphical representations for MFD problems and parity check codes, we develop a suboptimal iterative belief propagation algorithm (BPA) that is based on the graphical inference method for low density parity check codes. Our simulation results suggest that the algorithm performance strongly depends on the connection density and the reliability of the alarm network. In particular, when the connection density is low and when the alarms and/or connections are unreliable, the algorithm performs almost optimally, i.e., it converges to the solution with the highest posterior probability most of the times. We also provide analytical bounds on the performance of the algorithm for special classes of systems in our framework

The above paper introduced the construction of a modified reachability tree (MRT) for (unbounded) Petri nets and its application to reachability, liveness, and deadlock analysis. This note shows via a counterexample that some of the MRT properties claimed in the above paper are incorrect.

This paper discusses a systematic methodology for calculating the exact aliasing probability associated with schemes that use an arbitrary finite-state machine to compact the response of a combinational circuit to a sequence of independently selected, random test input vectors. The proposed approach identifies the strong influence of fault activation probabilities on the probability of aliasing and uses an asymmetric error model to simultaneously track the states of two (fictitious) compactors, one driven by the response of the fault-free combinational circuit and one driven by the response of the faulty combinational circuit. By deriving the overall Markov chain that describes the combined behavior of these two compactors, we are able to calculate the exact aliasing probability for any test sequence length. In particular, for long enough sequences, the probability of aliasing is shown to only depend on the stationary distribution of the Markov chain. The insights provided by our analysis are used to evaluate the testing performance of simple examples of nonlinear compactors and to demonstrate regimes where they exhibit lower aliasing probability than linear compactors with the same number of states. Finally, by establishing connections with previous work that evaluated aliasing probability in linear compactors, our analysis clarifies the role played by the entropy of the stationary distribution of the compactor states.

This paper discusses fault tolerance in discrete-time dynamic systems, such as finite-state controllers or computer simulations, with focus on the use of coding techniques to efficiently provide fault tolerance to linear finite-state machines (LFSMs). Unlike traditional fault tolerance schemes, which rely heavily-particularly for dynamic systems operating over extended time horizons-on the assumption that the error-correcting mechanism is fault free, we are interested in the case when all components of the implementation are fault prone. The paper starts with a paradigmatic fault tolerance scheme that systematically adds redundancy into a discrete-time dynamic system in a way that achieves tolerance to transient faults in both the state transition and the error-correcting mechanisms. By combining this methodology with low-complexity error-correcting coding, we then obtain an efficient way of providing fault tolerance to k identical unreliable LFSMs that operate in parallel on distinct input sequences. The overall construction requires only a constant amount of redundant hardware per machine (but sufficiently large k) to achieve an arbitrarily small probability of overall failure for any prespecified (finite) time interval, leading in this way to a lower bound on the computational capacity of unreliable LFSMs.

In this paper, we consider distributed systems that can be modeled as finite state machines with known behavior under fault-free conditions, and we study the detection of a general class of faults that manifest themselves as permanent changes in the next-state transition functionality of the system. This scenario could arise in a variety of situations encountered in communication networks, including faults occurred due to design or implementation errors during the execution of communication protocols. In our approach, fault diagnosis is performed by an external observer/diagnoser that functions as a finite state machine and which has access to the input sequence applied to the system but has only limited access to the system state or output. In particular, we assume that the observer/diagnoser is only able to obtain partial information regarding the state of the given system at intermittent time intervals that are determined by certain synchronizing conditions between the system and the observer/diagnoser. By adopting a probabilistic framework, we analyze ways to optimally choose these synchronizing conditions and develop adaptive strategies that achieve a low probability of aliasing, i.e., a low probability that the external observer/diagnoser incorrectly declares the system as fault-free. An application of these ideas in the context of protocol testing/classification is provided as an example.

In this paper, two universally applicable preprocessing rules are developed to improve iterative receding algorithms that utilize the most reliable basis (MRB), while focusing on order-w reprocessing. Simulation results show that the proposed algorithm successfully decodes the Reed-Solomon concatenated code in near optimal manner at a block-error-rate with the maximum number of candidate codewords.

This paper presents coding techniques that can be used to provide fault tolerance to a parallel prefix computation that is performed on a binary tree of processing nodes. More specifically, we discuss how a parallel prefix computation in an arbitrary Abelian group can be protected using group homomorphisms. The proposed approach is general enough to handle a variety of group operations of interest and allows for designs ranging from simple parity schemes to full replication. Error detecting and correcting mechanisms are used solely at the leaf nodes and can capture faults at any node or link within the binary tree architecture on which the parallel prefix computation is performed. Furthermore, by tracking the propagation of errors in the binary tree, our method can identify a processing node that has permanently failed based on information from simple error detecting mechanisms at the leaf nodes.

This paper proposes a sub-optimal maximum-likelihood decoding algorithm for linear block codes. Given reliability information about each bit in the received word, our approach initially finds the set of most reliable "basis" information bits; it then searches for the most likely codeword by iteratively flipping bits in this basis set, constructing the corresponding codeword and determining its likelihood. The search of "test error patterns" on the set of basis information bits is conducted so that at each iteration the new set of basis information bits differs from a previously studied (and stored) one in a single bit position. Thus, the new codeword can be obtained from a stored codeword by modifying only the redundant bits that depend on the modified bit. The space complexity of the proposed decoding scheme is polynomial in the code length. We also describe an heuristic criterion to approximate the optimal set of test error patterns subject to a limit on the maximum computational effort. Simulation results with codes of relatively large length show that the proposed approach is very efficient, especially under low SNR.

Modular redundancy, the traditional approach to fault tolerance, is prohibitively expensive because of the overhead in replicating the hardware. In this paper we discuss alternative methods for obtaining fault-tolerant architectures for discrete-time (DT) linear time-invariant (LTI) filters. We view such filters as dynamic systems and provide fault tolerance to them by embedding their state into redundant state-spaces of higher dimensions. The embedding for a given filter is achieved systematically in a way that preserves the functionality of the filter, perhaps in some encoded form. The resulting redundant filtering architecture allows us to detect, identify and correct hardware failures by performing simple (linear) checks. As we show through examples, our approach generalizes previous schemes and leads to new, fault-tolerant architectures for DT LTI filtering.