Model checking transactional memories

Model checking transactional memories (TMs) is difficult because of the unbounded number, length, and delay of concurrent transactions, as well as the unbounded size of the memory. We show that, under certain conditions satisfied by most TMs we know of, the model checking problem can be reduced to a finite-state problem, and we illustrate the use of the method by proving the correctness of several TMs, including two-phase locking, DSTM, and TL2. The safety properties we consider include strict serializability and opacity; the liveness properties include obstruction freedom, livelock freedom, and wait freedom. Our main contribution lies in the structure of the proofs, which are largely automated and not restricted to the TMs mentioned above. In a first step we show that every TM that enjoys certain structural properties either violates a requirement on some program with two threads and two shared variables, or satisfies the requirement on all programs. In the second step, we use a model checker to prove the requirement for the TM applied to a most general program with two threads and two variables. In the safety case, the model checker checks language inclusion between two finite-state transition systems, a nondeterministic transition system representing the given TM applied to a most general program, and a deterministic transition system representing a most liberal safe TM applied to the same program. The given TM transition system is nondeterministic because a TM can be used with different contention managers, which resolve conflicts differently. In the liveness case, the model checker analyzes fairness conditions on the given TM transition system.     

Byzantine agreement with homonyms

So far, the distributed computing community has either assumed that all the processes of a distributed system have distinct identifiers or, more rarely, that the processes are anonymous and have no identifiers. These are two extremes of the same general model: namely, $n$ processes use $\ell $ different identifiers, where $1 \le \ell \le n$ . In this paper, we ask how many identifiers are actually needed to reach agreement in a distributed system with $t$ Byzantine processes. We show that having $3t+1$ identifiers is necessary and sufficient for agreement in the synchronous case but, more surprisingly, the number of identifiers must be greater than $\frac{n+3t}{2}$ in the partially synchronous case. This demonstrates two differences from the classical model (which has $\ell =n$ ): there are situations where relaxing synchrony to partial synchrony renders agreement impossible; and, in the partially synchronous case, increasing the number of correct processes can actually make it harder to reach agreement. The impossibility proofs use the fact that a Byzantine process can send multiple messages to the same recipient in a round. We show that removing this ability makes agreement easier: then, $t+1$ identifiers are sufficient for agreement, even in the partially synchronous model, assuming processes can count the number of messages with the same identifier they receive in a round.     

Human-aware robot navigation: A survey

Navigation is a basic skill for autonomous robots. In the last years human–robot interaction has become an important research field that spans all of the robot capabilities including perception, reasoning, learning, manipulation and navigation. For navigation, the presence of humans requires novel approaches that take into account the constraints of human comfort as well as social rules. Besides these constraints, putting robots among humans opens new interaction possibilities for robots, also for navigation tasks, such as robot guides. This paper provides a survey of existing approaches to human-aware navigation and offers a general classification scheme for the presented methods.     

Physiological and subjective evaluation of a human-robot object hand-over task

In the context of task sharing between a robot companion and its human partners, the notions of safe and compliant hardware are not enough. It is necessary to guarantee ergonomic robot motions. Therefore, we have developed Human Aware Manipulation Planner (Sisbot et al., 2010), a motion planner specifically designed for human–robot object transfer by explicitly taking into account the legibility, the safety and the physical comfort of robot motions. The main objective of this research was to define precise subjective metrics to assess our planner when a human interacts with a robot in an object hand-over task. A second objective was to obtain quantitative data to evaluate the effect of this interaction. Given the short duration, the “relative ease” of the object hand-over task and its qualitative component, classical behavioral measures based on accuracy or reaction time were unsuitable to compare our gestures. In this perspective, we selected three measurements based on the galvanic skin conductance response, the deltoid muscle activity and the ocular activity. To test our assumptions and validate our planner, an experimental set-up involving Jido, a mobile manipulator robot, and a seated human was proposed. For the purpose of the experiment, we have defined three motions that combine different levels of legibility, safety and physical comfort values. After each robot gesture the participants were asked to rate them on a three dimensional subjective scale. It has appeared that the subjective data were in favor of our reference motion. Eventually the three motions elicited different physiological and ocular responses that could be used to partially discriminate them.     

Removal of contaminants and pathogens from secondary effluents using intermittent sand filters

Intermittent infiltration percolation of wastewater through unsaturated sand bed is an extensive treatment technique aimed at eliminating organic matter, oxidizing ammonium and removing pathogens. The main purpose of this study was to determine the depuration efficiencies of a sand filter to remove contaminants from secondary wastewater effluents. Elimination of pathogenic bacteria (total and faecal coliforms, streptococci) and their relationship with the filter depth were investigated. Results showed a high capacity of infiltration percolation process to treat secondary effluents. Total elimination of suspended solids was obtained. Mean removal rate of BOD(5) and COD was more than 97 and more than 81%, respectively. Other water quality parameters such as NH(4)-N, TKN and PO(4)-P showed significant reduction except NO(3)-N which increased significantly in the filtered water. Efficiency of pathogenic bacteria removal was shown to mainly depend on the filter depth. Average reductions of 2.35 log total coliforms, 2.47 log faecal coliforms and 2.11 log faecal streptococci were obtained. The experimental study has shown the influence of the temperature on the output purification of infiltration percolation process.     

The impossibility of boosting distributed service resilience

We study f-resilient services, which are guaranteed to operate as long as no more than f of the associated processes fail. We prove three theorems asserting the impossibility of boosting the resilience of such services. Our first theorem allows any connection pattern between processes and services but assumes these services to be atomic (linearizable) objects. This theorem says that no distributed system in which processes coordinate using f-resilient atomic objects and reliable registers can solve the consensus problem in the presence of f+1 undetectable process stopping failures. In contrast, we show that it is possible to boost the resilience of some systems solving problems easier than consensus: for example, the 2-set-consensus problem is solvable for 2n processes and 2n-1 failures (i.e., wait-free) using n-process consensus services resilient to n-1 failures (wait-free). Our proof is short and self-contained.We then introduce the larger class of failure-oblivious services. These are services that cannot use information about failures, although they may behave more flexibly than atomic objects. An example of such a service is totally ordered broadcast. Our second theorem generalizes the first theorem and its proof to failure-oblivious services.Our third theorem allows the system to contain failure-aware services, such as failure detectors, in addition to failure-oblivious services. This theorem requires that each failure-aware service be connected to all processes; thus, f+1 process failures overall can disable all the failure-aware services. In contrast, it is possible to boost the resilience of a system solving consensus using failure-aware services if arbitrary connection patterns between processes and services are allowed: consensus is solvable for any number of failures using only 1-resilient 2-process perfect failure detectors.As far as we know, this is the first time a unified framework has been used to describe both atomic and non-atomic objects, and the first time boosting analysis has been performed for services more general than atomic objects.     

An unsupervised learning approach based on a Hopfield-like network for assessing posterior capsule opacification

Posterior capsule opacification (PCO) is the most common complication of cataract surgery, occurring in up to 50% of patients by 2–3 years after the operation [Spalton in Eye 13(Pt 3b):489–492, 1999]. This paper proposes a new approach for the assessment of PCO digital images. The approach deploys an unsupervised learning technique for clustering image pixels into different regions based on chromatic attributes. The innovative aspect of this paper lies in proposing the number of regions in a clustered image as a measurement tool for assessing the PCO. Experiments using synthetic data confirmed the plausibility of this approach. A series of experiments conducted on real PCO images demonstrated the robustness and stability of the proposed algorithm. Finally, the comparison of our method’s assessment with medical expert evaluation reveals a very reasonable concordance.     

Stabilizing maximum matching in bipartite networks

A matching ${E_\mathcal{M}}$ of graph G =  (V, E) is a subset of the edges E, such that no vertex in V is incident to more than one edge in ${E_\mathcal{M}}$ . The matching ${E_\mathcal{M}}$ is maximum if there is no matching in G with size strictly larger than the size of ${E_\mathcal{M}}$ . In this paper, we present a distributed stabilizing algorithm for finding maximum matching in bipartite graphs based on the stabilizing PIF algorithm of Cournier et al. (Proceedings of 21st IEEE international conference on distributed computing systems, 91–98, 2001). Since our algorithm is stabilizing, it does not require initialization and withstands transient faults. The complexity of the proposed algorithm is O(d × n) rounds, where d is the diameter of the communication network and n is the number of nodes in the network. The space complexity is O(log Δ +  log d), where Δ is the largest degree of all the nodes in the communication network. In addition, an optimal version of the proposed algorithm finding maximum matching in linear time is also presented.