How to Guard a Graph?

We initiate the study of the algorithmic foundations of games in which a set of cops has to guard a region in a graph (or digraph) against a robber. The robber and the cops are placed on vertices of the graph; they take turns in moving to adjacent vertices (or staying). The goal of the robber is to enter the guarded region at a vertex with no cop on it. The problem is to find the minimum number of cops needed to prevent the robber from entering the guarded region. The problem is highly non-trivial even if the robber’s or the cops’ regions are restricted to very simple graphs. The computational complexity of the problem depends heavily on the chosen restriction. In particular, if the robber’s region is only a path, then the problem can be solved in polynomial time. When the robber moves in a tree (or even in a star), then the decision version of the problem is NP-complete. Furthermore, if the robber is moving in a directed acyclic graph, the problem becomes PSPACE-complete.     

Firing variability is higher than deduced from the empirical coefficient of variation

A convenient and often used summary measure to quantify the firing variability in neurons is the coefficient of variation (CV), defined as the standard deviation divided by the mean. It is therefore important to find an estimator that gives reliable results from experimental data, that is, the estimator should be unbiased and have low estimation variance. When the CV is evaluated in the standard way (empirical standard deviation of interspike intervals divided by their average), then the estimator is biased, underestimating the true CV, especially if the distribution of the interspike intervals is positively skewed. Moreover, the estimator has a large variance for commonly used distributions. The aim of this letter is to quantify the bias and propose alternative estimation methods. If the distribution is assumed known or can be determined from data, parametric estimators are proposed, which not only remove the bias but also decrease the estimation errors. If no distribution is assumed and the data are very positively skewed, we propose to correct the standard estimator. When defining the corrected estimator, we simply use that it is more stable to work on the log scale for positively skewed distributions. The estimators are evaluated through simulations and applied to experimental data from olfactory receptor neurons in rats.     

On set consensus numbers

It is conjectured that the only way a failure detector (FD) can help solving n-process tasks is by providing k-set consensus for some ${k\in\{1,\ldots,n\}}$ among all the processes. It was recently shown by Zieli??ski that any FD that allows for solving a given n-process task that is unsolvable read-write wait-free, also solves (n ? 1)-set consensus. In this paper, we provide a generalization of Zieli??ski??s result. We show that any FD that solves a colorless task that cannot be solved read-write k-resiliently, also solves k-set consensus. More generally, we show that every colorless task ${\mathcal{T}}$ can be characterized by its set consensus number: the largest ${k\in\{1,\ldots,n\}}$ such that ${\mathcal{T}}$ is solvable (k ? 1)-resiliently. A task ${\mathcal{T}}$ with set consensus number k is, in the failure detector sense, equivalent to k-set consensus, i.e., a FD solves ${\mathcal{T}}$ if and only if it solves k-set consensus. As a corollary, we determine the weakest FD for solving k-set consensus in every environment, i.e., for all assumptions on when and where failures might occur.     

Accelerating temporal verification of Simulink diagrams using satisfiability modulo theories

Automatic verification of programs and computer systems with input variables represents a significant and well-motivated challenge. The case of Simulink diagrams is especially difficult, because there the inputs are read iteratively, and the number of input variables is in theory unbounded. We apply the techniques of explicit model checking to account for the temporal (control) aspects of verification and use set-based representation of data, thus handling both sources of non-determinism present in the verification. Two different representations of sets are evaluated in scalability with respect to the range of input variables. Explicit (enumerating) sets are very fast for small ranges but fail to scale. Symbolic sets, represented as first-order formulas in the bit-vector theory and compared using satisfiability modulo theory solvers, scale well to arbitrary (though still bounded) range of input variables. To leverage the combined strengths of explicit and symbolic representations, we have designed a hybrid representation which we showed to outperform both pure representations. Thus, the proposed method allows complete automatic verification without the need to limit the non-determinism of input. Moreover, the principle underlying the hybrid representation entails inferring knowledge about the system under verification, which the developers did not explicitly include in the system, and which can significantly accelerate the verification process.     

On generalized middle-level problem

Let be the subgraph of the hypercube Q_n induced by levels between k and n-k, where n?2k+1 is odd. The well-known middle-level conjecture asserts that is Hamiltonian for all k?1. We study this problem in for fixed k. It is known that and are Hamiltonian for all odd n?3. In this paper we prove that also is Hamiltonian for all odd n?5, and we conjecture that is Hamiltonian for every k?0 and every odd n?2k+1.     

Assessment of spatial and temporal properties of Ka/Q band earth‐space radio channel across Europe using Alphasat Aldo Paraboni payload

The upcoming migration of satellite services to higher bands, namely, the Ka‐ and Q/V‐bands, offers many advantages in terms of bandwidth and system capacity. However, it poses challenges as propagation effects introduced by the various atmospheric phenomena are particularly pronounced in these bands and can become a serious constraint in terms of system reliability and performance. This paper presents the goals, organisation, and preliminary results of an ongoing large‐scale European coordinated propagation campaign using the Alphasat Aldo Paraboni Ka/Q band signal payload on satellite, performed by a wide scientific consortium in the framework of a European Space Agency (ESA) project. The main objective of this activity is the experimental characterisation of the spatial and temporal correlation over Europe of the radio channel at Ka and Q band for future modelling activities and to collect data for development and testing of fading mitigation techniques.     

Failure detectors as type boosters

The power of an object type T can be measured as the maximum number n of processes that can solve consensus using only objects of T and registers. This number, denoted cons(T), is called the consensus power of T. This paper addresses the question of the weakest failure detector to solve consensus among a number k > n of processes that communicate using shared objects of a type T with consensus power n. In other words, we seek for a failure detector that is sufficient and necessary to “boost” the consensus power of a type T from n to k. It was shown in Neiger (Proceedings of the 14th annual ACM symposium on principles of distributed computing (PODC), pp. 100–109, 1995) that a certain failure detector, denoted Ω _n , is sufficient to boost the power of a type T from n to k, and it was conjectured that Ω _n was also necessary. In this paper, we prove this conjecture for one-shot deterministic types. We first show that, for any one-shot deterministic type T with cons(T) ≤ n, Ω _n is necessary to boost the power of T from n to n + 1. Then we go a step further and show that Ω _n is also the weakest to boost the power of (n + 1)-ported one-shot deterministic types from n to any k > n. Our result generalizes, in a precise sense, the result of the weakest failure detector to solve consensus in asynchronous message-passing systems (Chandra et al. in J ACM 43(4):685–722, 1996). As a corollary, we show that Ω _t is the weakest failure detector to boost the resilience level of a distributed shared memory system, i.e., to solve consensus among n > t processes using (t − 1)-resilient objects of consensus power t. This paper is a revised and extended version of a paper that appeared in the Proceedings of the 17th International Symposium on Distributed Computing (DISC 2003), entitled “On failure detectors and type boosters.”