Source author record

Sahil Dhoked

Sahil Dhoked appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Distributed, Parallel, and Cluster Computing Data Structures and Algorithms Operating Systems

Catalog footprint

What is connected

2works

3topics

1close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2021arXiv

Memory Reclamation for Recoverable Mutual Exclusion

Mutual exclusion (ME) is a commonly used technique to handle conflicts in concurrent systems. With recent advancements in non-volatile memory technology, there is an increased focus on the problem of recoverable mutual exclusion (RME), a special case of ME where processes can fail and recover. However, in order to ensure that the problem of RME is also of practical interest, and not just a theoretical one, memory reclamation poses as a major obstacle in several RME algorithms. Often RME algorithms need to allocate memory dynamically, which increases the memory footprint of the algorithm over time. These algorithms are typically not equipped with suitable garbage collection due to concurrency and failures. In this work, we present the first "general" recoverable algorithm for memory reclamation in the context of recoverable mutual exclusion. Our algorithm can be plugged into any RME algorithm very easily and preserves all correctness property and most desirable properties of the algorithm. The space overhead of our algorithm is $\mathcal{O}(n^2 * sizeof(node)\ )$, where $n$ is the total number of processes in the system. In terms of remote memory references (RMRs), our algorithm is RMR-optimal, i.e, it has a constant RMR overhead per passage. Our RMR and space complexities are applicable to both $CC$ and $DSM$ memory models.

preprint2020arXiv

An Adaptive Approach to Recoverable Mutual Exlcusion

Mutual exclusion (ME) is one of the most commonly used techniques to handle conflicts in concurrent systems. Traditionally, mutual exclusion algorithms have been designed under the assumption that a process does not fail while acquiring/releasing a lock or while executing its critical section. However, failures do occur in real life, potentially leaving the lock in an inconsistent state. This gives rise to the problem of \emph{recoverable mutual exclusion (RME)} that involves designing a mutual exclusion algorithm that can tolerate failures, while maintaining safety and liveness properties. One of the important measures of performance of any ME algorithm, including an RME algorithm, is the number of \emph{remote memory references (RMRs)} made by a process (for acquiring and releasing a lock as well as recovering the lock structure after a failure). The best known RME algorithm solves the problem for $n$ processes in sub-logarithmic number of RMRs, given by $\mathcal{O}(\frac{\log n}{\log \log n})$, irrespective of the number of failures in the system. In this work, we present a new algorithm for solving the RME problem whose RMR complexity gradually \emph{adapts} to the number of failures that have occurred in the system "recently". In the absence of failures, our algorithm generates only $\mathcal{O}(1)$ RMRs. Furthermore, its RMR complexity is given by $\mathcal{O}(\min\{ \sqrt{F}, \frac{\log n}{\log \log n} \})$ where $F$ is the total number of failures in the "recent" past. In addition to read and write instructions, our algorithm uses compare-and-swap (\CAS{}) and fetch-and-store (\FAS{}) hardware instructions, both of which are commonly available in most modern processors.