An optimal algorithm for distributed snapshots with causal message ordering

We present an optimal distributed algorithm to record a global state of a distributed system with causally ordered message delivery. The message complexity of our algorithm is O(n) bits where n is the number of processes in the system.     

A causal approach to nonmonotonic reasoning

We introduce logical formalisms of production and causal inference relations based on input/output logics of Makinson and Van der Torre [J. Philos. Logic 29 (2000) 383–408]. These inference relations will be assigned, however, both standard semantics (giving interpretation to their rules), and natural nonmonotonic semantics based on the principle of explanation closure. The resulting nonmonotonic formalisms will be shown to provide a logical representation of abductive reasoning, and a complete characterization of causal nonmonotonic reasoning from McCain and Turner [Proc. AAAI-97, Providence, RI, 1997, pp. 460–465]. The results of the study suggest production and causal inference as general nonmonotonic formalisms providing an alternative representation for a significant part of nonmonotonic reasoning.     

A modified PLS path modeling algorithm handling reflective categorical variables and a new model building strategy

Partial least squares (PLS) path modeling has found increased applications in customer satisfaction analysis thanks to its ability to handle complex models. A modified PLS path modeling algorithm together with a model building strategy are introduced and applied to customer satisfaction analysis at the French energy supplier Electricité de France. The modified PLS algorithm handles all kinds of scales (categorical or nominal variables) and is well suited when nominal or binary variables are involved. PLS path modeling and structural equation modeling are confirmatory approaches and thus need an initial conceptual model. A two-step model building strategy is presented; the first step is based on Bayesian networks structure learning to build the measurement model and the second step is based on partial correlation and hypothesis tests to build the structural model. Applications to customer satisfaction data are presented.     

A note on total ordering multicast using propagation trees

Jia (1995) proposed a multicast scheme, using propagation trees, to ensure the total ordering (including causal ordering) delivery of messages for group communication. Our study indicates that causal relation between some messages may not actually be presented in this protocol. We then present a revised approach for closed group communication     

A note on causal and CITE iterative learning control algorithms

The convergence properties of causal and current iteration tracking error (CITE) discrete time iterative learning control (ILC) algorithms are studied using time and frequency domain convergence criteria. Of particular interest are conditions for monotone convergence, and these are evaluated using a discrete-time version of Bode's integral theorem.     

A parametrized algorithm that implements sequential, causal, and cache memory consistencies

In this paper, we present an algorithm that can be used to implement sequential, causal, or cache consistency in distributed shared memory (DSM) systems. For this purpose it includes a parameter that allows us to choose the consistency model to be implemented. If all processes run the algorithm with the same value in this parameter, the corresponding consistency is achieved. (Additionally, the algorithm tolerates that processes use certain combination of parameter values.) This characteristic allows a concrete consistency model to be chosen, but implements it with the more efficient algorithm in each case (depending of the requirements of the applications). Additionally, as far as we know, this is the first algorithm proposed that implements cache coherence.In our algorithm, all the read and write operations are executed locally when implementing causal and cache consistency (i.e., they are fast). It is known that no sequential algorithm has only fast memory operations. In our algorithm, however, all the write operations and some read operations are fast when implementing sequential consistency. The algorithm uses propagation and full replication, where the values written by a process are propagated to the rest of the processes. It works in a cyclic turn fashion, with each process of the DSM system, broadcasting one message in turn. The values written by the process are sent in the message (instead of sending one message for each write operation): However, unnecessary values are excluded. All this permits the amount of message traffic owing to the algorithm to be controlled.     

The correctness problem: evaluating the ordering of binary features in rankings

In machine learning, feature ranking (FR) algorithms are used to rank features by relevance to the class variable. FR algorithms are mostly investigated for the feature selection problem and less studied for the problem of ranking. This paper focuses on the latter. A question asked about the problem of ranking given in the terminology of FR is: as different FR criteria estimate the relationship between a feature and the class variable differently on a given data, can we determine which criterion better captures the “true” feature-to-class relationship and thus generates the most “correct” order of individual features? This is termed as the “correctness” problem. It requires a reference ordering against which the ranks assigned to features by a FR algorithm are directly compared. The reference ranking is generally unknown for real-life data. In this paper, we show through theoretical and empirical analysis that for two-class classification tasks represented with binary data, the ordering of binary features based on their individual predictive powers can be used as a benchmark. Thus, allowing us to test how correct is the ordering of a FR algorithm. Based on these ideas, an evaluation method termed as FR evaluation strategy (FRES) is proposed. Rankings of three different FR criteria (relief, mutual information, and the diff-criterion) are investigated on five artificially generated and four real-life binary data sets. The results indicate that FRES works equally good for synthetic and real-life data and the diff-criterion generates the most correct orderings for binary data.     

The correctness of the Schorr-Waite list marking algorithm

Summary This paper presents a relatively simple proof of a nontrivial algorithm for marking all the nodes of a list structure. The proof separates properties of the algorithm from properties of the data on which it operates and is a significant application of the method of intermittent assertions.(This paper grew out of an earlier version which was submitted to this journal on October 16, 1974)     

A linear algorithm for MLL proof net correctness and sequentialization

The paper presents in full detail the first linear algorithm given in the literature (Guerrini (1999) [6]) implementing proof structure correctness for multiplicative linear logic without units. The algorithm is essentially a reformulation of the Danos contractibility criterion in terms of a sort of unification. As for term unification, a direct implementation of the unification criterion leads to a quasi-linear algorithm. Linearity is obtained after observing that the disjoint-set union-find at the core of the unification criterion is a special case of union-find with a real linear time solution.     

A note on Bayesian identification of change points in data sequences

Recent research in mathematical methods for finance suggests that time series for financial data should be studied with non-stationary models and with structural changes that include both jumps and heteroskedasticity (with jumps in variance). It has been recognized that discriminating between variations caused by the continuous motion of Brownian shocks and the genuine discontinuities in the path of the process constitutes a challenge for existing computational procedures. This issue is addressed here, using the product partition model (PPM), for performing such discrimination and the estimation of process jump parameters. Computational implementation aspects of PPM applied to the identification of change points in data sequences are discussed. In particular, we analyze the use of a Gibbs sampling scheme to compute the estimates and show that there is no significant impact of such use on the quality of the results. The influence of the size of the data sequence on the estimates is also of interest, as well as the efficiency of the PPM to correctly identify atypical observations occurring in close instants of time. Extensive Monte Carlo simulations attest to the effectiveness of the Gibbs sampling implementation. An illustrative financial time series example is also presented.     

A note on continuous-time ELS

The parameter estimation of continuous-time finite-dimensional linear stochastic systems is a problem of long-standing interest. The method usually used is the extended least-squares (ELS) algorithm described by a nonlinear stochastic differential equation (SLD), with the existence of the global strong solution assumed. This paper shows that the ELS estimate does exist in [0, ∞), and at the same time presents a number of convergence results paralleling those for the discrete-time case.     

A note on the maximum solutions of riccati equations

A property of the maximum solutions of Riccati equations was discussed by Kawasaki and Shimemura (Automatica, 19, 557–560, 1983). While we maintain their result is correct, their proof is incomplete. The focus of this paper is to rigorously substantiate their claim. Also, a more general property of the maximum solutions of Riccati equations is proposed and proven.     

A simplified correctness proof for a well-known algorithm computing strongly connected components

The computation of the strongly connected components of a directed graph is one of the fundamental algorithmic graph problems. Linear-time algorithms with simple implementations are known. Here a simplified correctness proof for one of these algorithms is presented.     

A note on the greedy algorithm for the unsplittable flow problem

In a recent paper Chekuri and Khanna improved the analysis of the greedy algorithm for the edge disjoint paths problem and proved the same bounds also for the related uniform capacity unsplittable flow problem. Here we show that their ideas can be used to get the same approximation ratio even for the more general Unsplittable Flow Problem with nonuniform edge capacities.     

A note concerning the closest point pair algorithm

An algorithm, described by Sedgewick, finds the distance between the closest pair of n given points in a plane using a variant of mergesort. This takes O(nlogn) time. To prove this it is necessary to show that, in the merge phase of the algorithm, no more than a constant number of distances need to be checked for each point considered. Cormen, Leiserson and Rivest show that checking seven distances is sufficient while Sedgewick suggests that this should be four. This paper shows that checking three distances is sufficient and that a slight modification of the algorithm reduces the number to two.