In this article, we consider a special class of liveness properties for systems consisting of concurrent objects. These properties ensure the termination of methods calls under certain fairness assumptions and thus the progress of the execution. Liveness properties are defined for concurrent objects and they typically include lock-freedom , wait-freedom , deadlock-freedom , starvation-freedom, and obstruction-freedom . It is known that these five liveness properties are decidable for sequential consistency (SC) memory model of finite-state programs with a bounded number of processes. However, the problem of decidability of liveness for finite state concurrent programs running on relaxed memory models remains open. In this article, we address the decidability problem of liveness properties of concurrent objects for the total store order (TSO) memory model which is used in the x86 architecture. In particular, we prove that for a bounded number of processes, lock-freedom, wait-freedom, deadlock-freedom and starvation-freedom are undecidable, and that obstruction-freedom is decidable on TSO for a bounded number of processes. Further on, we investigate the verification problem of k -bounded wait-freedom , a bounded version of wait-freedom, and show that for each bound k , the problem of checking k -bounded wait-freedom is decidable on TSO for a bounded number of processes. We show that the complexity for checking obstruction-freedom and checking k -bounded wait-freedom are both non-primitive recursive. We also discover an interesting difference between liveness on TSO and that on SC. Our finding is that wait-freedom implies k -bounded wait-freedom for some k on SC memory model, but this implication does not hold on the TSO model. We prove this by generating a concrete object on TSO that is wait-free but not k -bounded wait-free for any k .

Sanitization is an effective approach for ensuring data security through scrubbing invalid but sensitive data pages, with the cost of impacts on storage performance due to moving out valid pages from the sanitization-required wordline, which is a logical read/write unit and consists of multiple pages in high-density SSDs. To minimize the impacts on I/O latency and data security, this article proposes a polling-based scheduling approach for data sanitization in high-density SSDs. Our method polls a specific SSD channel for completing data sanitization at the block granularity, meanwhile other channels can still service I/O requests. Furthermore, our method assigns a low priority to the blocks that are more likely to have future adjacent page invalidations inside sanitization-required wordlines, while selecting the sanitization block, to minimize the negative impacts of moving valid pages. Through a series of emulation experiments on several disk traces of real-world applications, we show that our proposal can decrease the negative effects of data sanitization in terms of the risk-performance index, which is a united time metric of I/O responsiveness and the unsafe time interval, by 16.34% , on average, compared to related sanitization methods.

Distributed systems often replicate data at multiple locations to achieve availability despite network partitions. These systems accept updates at any replica and propagate them asynchronously to every other replica. Conflict-Free Replicated Data Types (CRDTs) provide a principled approach to the problem of ensuring that replicas are eventually consistent despite the asynchronous delivery of updates.

Efficient implementations of concurrent objects such as atomic collections are essential to modern computing. Unfortunately their correctness criteria — linearizability with respect to given ADT specifications — are hard to verify. Verifying linearizability is undecidable in general, even on classes of implementations where the usual control-state reachability is decidable. In this work we consider concurrent priority queues which are fundamental to many multi-threaded applications like task scheduling or discrete event simulation, and show that verifying linearizability of such implementations is reducible to control-state reachability. This reduction entails the first decidability results for verifying concurrent priority queues with an unbounded number of threads, and it enables the application of existing safety-verification tools for establishing their correctness.