Matrix approach to deadlock-free dispatching in multi-class finite buffer flowlines

For finite-buffer manufacturing systems, the major stability issue is "deadlock," rather than "bounded-buffer-length stability." The paper introduces the concept of "system deadlock," defined rigorously in Petri net terms, and system operation with uninterrupted part-flow is characterized in terms of the absence of this condition. For a large class of finite-buffer multiclass re-entrant flowline systems, an analysis of "circular waits" yields necessary and sufficient conditions for the occurrence of "system deadlock." This allows the formulation of a maximally permissive one-step-look-ahead deadlock-avoidance control policy for dispatching jobs, while maximizing the percent utilization of resources. The result is a generalized kanban dispatching strategy, which is more general than the standard multiclass last buffer first serve (LBFS) dispatching strategies for finite buffer flowlines that typically under-utilize the resources. The problem of computational complexity associated with Petri net (PN) applications is overcome by using certain sub-matrices of the PN incidence matrix. Computationally efficient matrix techniques are given for implementing the deadlock-free dispatching policy.     

Robust gossiping with an application to consensus

We study deterministic gossiping in synchronous systems with dynamic crash failures. Each processor is initialized with an input value called rumor. In the standard gossip problem, the goal of every processor is to learn all the rumors. When processors may crash, then this goal needs to be revised, since it is possible, at a point in an execution, that certain rumors are known only to processors that have already crashed. We define gossiping to be completed, for a system with crashes, when every processor knows either the rumor of processor v or that v has already crashed, for any processor v. We design gossiping algorithms that are efficient with respect to both time and communication. Let t<n be the number of failures, where n is the number of processors. If , then one of our algorithms completes gossiping in O(log²t) time and with O(npolylogn) messages. We develop an algorithm that performs gossiping with O(n^1.77) messages and in O(log²n) time, in any execution in which at least one processor remains non-faulty. We show a trade-off between time and communication in gossiping algorithms: if the number of messages is at most O(npolylogn), then the time has to be at least . By way of application, we show that if n−t=Ω(n), then consensus can be solved in O(t) time and with O(nlog²t) messages.     

Setting up a competition framework for the evaluation of structure extraction from OCR-ed books

This paper describes the setup of the Book Structure Extraction competition run at ICDAR 2009. The goal of the competition was to evaluate and compare automatic techniques for deriving structure information from digitized books, which could then be used to aid navigation inside the books. More specifically, the task that participants faced was to construct hyperlinked tables of contents for a collection of 1,000 digitized books. This paper describes the setup of the competition and its challenges. It introduces and discusses the book collection used in the task, the collaborative construction of the ground truth, the evaluation measures, and the evaluation results. The paper also introduces a data set to be used freely for research evaluation purposes.     

A Survey of Symbolic Methods in Computational Analysis of Cryptographic Systems

Since the 1980s, two approaches have been developed for analyzing security protocols. One of the approaches relies on a computational model that considers issues of complexity and probability. This approach captures a strong notion of security, guaranteed against all probabilistic polynomial-time attacks. The other approach relies on a symbolic model of protocol executions in which cryptographic primitives are treated as black boxes. Since the seminal work of Dolev and Yao, it has been realized that this latter approach enables significantly simpler and often automated proofs. However, the guarantees that it offers with respect to the more detailed computational models have been quite unclear. For more than 20 years the two approaches have coexisted but evolved mostly independently. Recently, significant research efforts attempt to develop paradigms for cryptographic systems analysis that combines the best of both worlds. There are two broad directions that have been followed. Computational soundness aims to establish sufficient conditions under which results obtained using symbolic models imply security under computational models. The direct approach aims to apply the principles and the techniques developed in the context of symbolic models directly to computational ones. In this paper we survey existing results along both of these directions. Our goal is to provide a rather complete summary that could act as a quick reference for researchers who want to contribute to the field, want to make use of existing results, or just want to get a better picture of what results already exist.     

Long-term high-frequency validation of MODIS LST products in a Mediterranean mountain environment

The accuracy of Moderate-resolution Imaging Spectroradiometer (MODIS) level 3 1 km land surface temperature (LST) products was assessed through long-term validation carried out in a mountainous site in Sierra Nevada, southeast Spain. A total of 1458 day and night thermal images, acquired by Terra and Aqua satellites during 2008, were processed and compared to ground-truth data recorded at the meteorological station of Robledal de Cañar with a frequency of one measurement every 10 min. The purpose of this investigation was to understand whether MODIS LST data can be used as input for climate models to be constructed for mountainous environments. Several trends in the MODIS LST data were observed, including the underestimation of daytime values and the overestimation of night-time values. Although all the data sets (Terra and Aqua, diurnal and nocturnal) showed high correlation coefficients with ground measurements, only night values maintained a relatively high accuracy of approximately 2°C of annual average error. Factors that may cause errors in the MODIS LST data, like acquisition angle, cloud, and snow cover, were analysed without conclusive results. High accuracy levels, i.e. close to 1°C, similar to other validation studies carried out over simpler and much more homogenous land-cover types such as cultivated fields, have been achieved for night images acquired during the summer months, thus making these datasets reliable for their use in climatic models over mountainous regions.     

Robustness and coordination in voltage control of large-scale power systems

In this paper it is shown how the robustness and the coordination of the voltage regulation actions for the transmission grid can be improved. Simpler approaches which ensure higher robustness and performances can be used if the control objectives are pursued at two hierarchical levels of different nature. Also, this is a way to coordinate means of control of different nature with a sufficient time and methodological separation in order to avoid negative mutual influence. At the first level, called the static level, optimal reachable set-points are computed for the second control level, called the dynamic level. The static level can be combined with the shunt reactive power compensation. The system non-linearities are taken into account at the static level while the dynamic level is a linear robust predictive control which takes into account the presence of asynchronous transmission delays. The predictive control strategy is based on the separation property; the output delays are handled using an original steady-state Kalman predictor of order equal to the length of the state of the system without delays. The robustness is improved at the dynamic level against uncertain delays, parametric uncertainties (like, e.g., moderate topological errors and load variations not taken into account in the control model) and unmodelled dynamics. The two-level organisation of the control allows, on one hand, to take into account the important evolutions of the system (like, e.g., large and known topological and load changes) and, on the other hand, a coherent hybrid reactive power control: the switched control of the grid shunt compensation for the reactive power is done at the static level while the reactive power injection provided by the generators is continuously handled at the dynamic level. This is a theoretical analysis of how concepts of automatic control and voltage regulation of power systems can be combined. To be applied as a control scheme, the results presented here should be adapted to a specific context (particularities of the power system and of the organisation of the power industry). They can be used, eventually in conjunction with other improvements, to existing horizontally-organised interconnections (in which all generators of a controlled region can be easily managed since owned by the same utility) or to face specific requirements of moving to the open access in the electric power industry like, e.g., tolerating simplified models in order to cover larger regions, taking into account the interaction between regions, recalibrating set-points, assisting human operator when necessary or facilitating implementation of mechanisms for the management of the reactive power based on price signals.     

Maximum throughput of multiple access channels in adversarial environments

We consider deterministic distributed broadcasting on multiple access channels in the framework of adversarial queuing. Packets are injected dynamically by an adversary that is constrained by the injection rate and the number of packets that may be injected simultaneously; the latter we call burstiness. A protocol is stable when the number of packets in queues at the stations stays bounded. The maximum injection rate that a protocol can handle in a stable manner is called the throughput of the protocol. We consider adversaries of injection rate 1, that is, of one packet per round, to address the question if the maximum throughput 1 can be achieved, and if so then with what quality of service. We develop a protocol that achieves throughput 1 for any number of stations against leaky-bucket adversaries. The protocol has O(n²+\textburstiness){\mathcal{O}(n^2+\text{burstiness})} packets queued simultaneously at any time, where n is the number of stations; this upper bound is proved to be best possible. A protocol is called fair when each packet is eventually broadcast. We show that no protocol can be both stable and fair for a system of at least two stations against leaky-bucket adversaries. We study in detail small systems of exactly two and three stations against window adversaries to exhibit differences in quality of broadcast among classes of protocols. A protocol is said to have fair latency if the waiting time of packets is O(\textburstiness){\mathcal{O}(\text{burstiness})}. For two stations, we show that fair latency can be achieved by a full sensing protocol, while there is no stable acknowledgment based protocol. For three stations, we show that fair latency can be achieved by a general protocol, while no full sensing protocol can be stable. Finally, we show that protocols that either are fair or do not have the queue sizes affect the order of transmissions cannot be stable in systems of at least four stations against window adversaries.     

Automatic cluster detection in Kohonen's SOM.

Kohonen's self-organizing map (SOM) is a popular neural network architecture for solving problems in the field of explorative data analysis, clustering, and data visualization. One of the major drawbacks of the SOM algorithm is the difficulty for nonexpert users to interpret the information contained in a trained SOM. In this paper, this problem is addressed by introducing an enhanced version of the Clusot algorithm. This algorithm consists of two main steps: 1) the computation of the Clusot surface utilizing the information contained in a trained SOM and 2) the automatic detection of clusters in this surface. In the Clusot surface, clusters present in the underlying SOM are indicated by the local maxima of the surface. For SOMs with 2-D topology, the Clusot surface can, therefore, be considered as a convenient visualization technique. Yet, the presented approach is not restricted to a certain type of 2-D SOM topology and it is also applicable for SOMs having an n-dimensional grid topology.     

Inferring competitive role patterns in reality TV show through nonverbal analysis

This paper introduces a new facet of social media, namely that depicting social interaction. More concretely, we address this problem from the perspective of nonverbal behavior-based analysis of competitive meetings. For our study, we made use of “The Apprentice” reality TV show, which features a competition for a real, highly paid corporate job. Our analysis is centered around two tasks regarding a person’s role in a meeting: predicting the person with the highest status, and predicting the fired candidates. We address this problem by adopting both supervised and unsupervised strategies. The current study was carried out using nonverbal audio cues. Our approach is based only on the nonverbal interaction dynamics during the meeting without relying on the spoken words. The analysis is based on two types of data: individual and relational measures. Results obtained from the analysis of a full season of the show are promising (up to 85.7% of accuracy in the first case and up to 92.8% in the second case). Our approach has been conveniently compared with the Influence Model, demonstrating its superiority.     

The investigations of gas‐powder two phase flow in packed bed

Gas‐powder two‐phase flow in packed beds was investigated and the results are presented in this paper. The experimental system, in which the glass powder and air gas were injected into the lower part of the packed bed allowed the estimation of the influence of gas velocity, powder feed rate, powder and packed particles diameter on pressure loss and total hold up of powder in the packed bed. On the base of the experimental results, a one‐dimensional mathematical model for gas‐powder two‐phase flow in the packed bed was developed. This model allows satisfactory prediction of the pressure loss and the hold ups of powders. The maximum deviation between calculated and measured values was less than ±15%. Futhermore, the conditions when the blockade of the flow occurs were defined. The additional pressure loss (expressed by F_k) due to the gravitional force of powders and the collision and the friction between powders and packed particles, was correlated with Froude number as: for the void fraction in the packed bed ?₀ of between 0.36 to 0.41 or .