Search

The pervasive deployment of cloud services poses an ever-increasing demand for cross-client deduplication solutions to save network bandwidth, lower storage costs, and improve backup speeds. However, existing solutions typically depend on lock based approaches relying on a centralized chunk database, which tends to hinder performance scalability. In this work, we present a new cross-client cloud backup solution, named Duplicacy, based on a Lock-Free Deduplication approach. Lock-Free Deduplication stores chunks to network or cloud storage using content hashes as file names. It then adopts a two-step fossil deletion algorithm to solve the hard problem of deleting unreferenced chunks in the presence of concurrent backups, without the need for any locks. Experiments demonstrate that Duplicacy enables significant performance improvement for backups over previous well-known backup tools. In addition, Duplicacy can work with many general-purpose network or cloud storage services which only support a basic set of file operations, and turn them into sophisticated deduplication-aware storage servers without server-side changes.

Concurrent FIFO queues can be generally classified into lock-free queues and combining-based queues. Lock-free queues require manual parameter tuning to control the contention level of parallel execution, while combining-based queues encounter a bottleneck of single-threaded sequential combiner executions at a high concurrency level. In this paper, we introduce a different approach using both lock-free techniques and combining techniques synergistically to design a practical and scalable concurrent queue algorithm. As a result, we have achieved high scalability without any parameter tuning: on an 80-thread average throughput in our experimental results, our queue algorithm outperforms the most widely used Michael and Scott queue by 14.3 times, the best-performing combining-based queue by 1.6 times, and the best performing $\times$ 86-dependent lock-free queue by 1.7 percent. In addition, we designed our algorithm in such a way that the life cycle of a node is the same as that of its element. This has huge advantages over prior work: efficient implementation is possible without dedicated memory management schemes, which are supported only in some languages, may cause a performance bottleneck, or are patented. Moreover, the synchronized life cycle between an element and its node enables application developers to further optimize memory management.

This brief describes a wide-range operating false-lock-free delay-locked loop (DLL) for a low-voltage differential signaling (LVDS) display interface. A false-lock detector circuit and a self-reset circuit internally prevent any possible false locks in a robust way. The proposed DLL immediately removes stuck false locks caused by an improper phase detector state. The DLL circuit does not require the duty ratio of the input clock to be 50%. The proposed circuit has been fabricated using the 0.15-μm 1P-6M mixed-mode CMOS technology. The proposed DLL is implemented for an LVDS display interface and supports operating from 20 to 135 MHz without any error. It consumes 2.2 mW under a 130-MHz operation.

Lock-free data objects offer several advantages over their blocking counterparts, such as being immune to deadlocks, priority inversion, and convoying. They have also been shown to work well in practice. However, composing the operations they provide into larger atomic operations, while still guaranteeing efficiency and lock-freedom, is a challenging algorithmic task. We present a lock-free methodology for composing a wide variety of concurrent linearizable objects together by unifying their linearization points. This makes it possible to relatively easily introduce atomic lock-free move operations to a wide range of concurrent lock-free containers. This move operation allows data to be transferred from one container to another, in a lock-free way, without blocking any of the operations supported by the original container. For a data object to be suitable for composition using our methodology it needs to fulfill a set of requirements. These requirement are, however, generic enough to be fulfilled by a large set of objects. To show this we have performed case studies on six commonly used lock-free objects (a stack, a queue, a skip list, a deque, a doubly linked list and a hash table) to demonstrate the general applicability of the methodology. We also show that the operations originally supported by the data objects keep their performance behavior under our methodology.

Exploiting the parallelism in multiprocessor systems is a major challenge in modern computer science. Multicore programming demands a change in the way we design and use fundamental data structures. The standard collection of data structures and algorithms in C++11 is the sequential standard template library (STL). In this paper, we present their vision for the theory and practice for the design and implementation of a collection of highly concurrent fundamental data structures for multiprocessor application development with associated programming interface and advanced optimization support. Specifically, the proposed approach will provide a familiar, easy-to-use, and composable interface, similar to that of C++ STL. Each container type will be enhanced with internal support for nonblocking synchronization of its data access, thereby providing better safety and performance than traditional blocking synchronization by: 1) eliminating hazards such as deadlock, livelock, and priority inversion and 2) by being highly scalable in supporting large numbers of threads. The new library, lockless containers/data concurrency, will provide algorithms for handling fundamental computations in multithreaded contexts, and will incorporate these into libraries with familiar look and feel. The proposed approach will provide an immense boost in performance and software reuse, consequently productivity, for developers of scientific and systems applications, which are predominantly in C/C++. STL is widely used and a concurrent replacement library will have an immediate practical relevance and a significant impact on a variety of parallel programming domains including simulation, massive data mining, computational biology, financial engineering, and embedded control systems. As a proof-of-concept, this paper discusses the first design and implementation of a wait-free hash table.

In this paper, we present a novel asynchronous multithreaded algorithm for the maximum network flow problem. The algorithm is based on the classical push-relabel algorithm, which is essentially sequential and requires intensive and costly lock usages to parallelize it. The novelty of the algorithm is in the removal of lock and barrier usages, thereby enabling a much more efficient multithreaded implementation. The newly designed push and relabel operations are executed completely asynchronously and each individual process/thread independently decides when to terminate itself. We further propose an asynchronous global relabeling heuristic to speed up the algorithm. We prove that our algorithm finds a maximum flow with O(|V|2||-E|) operations, where |V| is the number of vertices and |E| is the number of edges in the graph. We also prove the correctness of the relabeling heuristic. Extensive experiments show that our algorithm exhibits better scalability and faster execution speed than the lock-based parallel push-relabel algorithm.

Garbage collection algorithms for shared-memory multiprocessors typically rely on some form of global synchro- nization to preserve consistency. Such global synchronization may lead to problems on asynchronous architectures: if one process is halted or delayed, other, nonfaulty processes will be unable to progress. By contrast, a storage management algorithm is lock- free if (in the absence of resource exhaustion) a process that is allocating or collecting memory can be delayed at any point without forcing other processes to block. This paper presents the first algorithm for lock-free garbage collection in a realistic model. The algorithm assumes that processes synchronize by applying read, write, and cornpre&swap operations to shared memory. This algorithm uses no locks, busy-waiting, or barrier synchronization, it does not assume that processes can observe or modify one another's local variables or registers, and it does not use inter-process interrupts. Index Terms-Garbage collection, lock-free algorithms, mem- ory management, multiprocessors, shared memory, wait-free al- gorithms.