M.Sc Thesis

M.Sc StudentZamir Tal
SubjectSpeculative Lock Acquisition for Fault-Tolerant Distributed
DepartmentDepartment of Computer Science
Supervisors PROF. Assaf Schuster
DR. Michael Factor
Full Thesis textFull thesis text - English Version


The overhead of lock acquisitions in distributed runtime environments often becomes a significant performance bottleneck. Lock acquisitions are expensive because they may result in communication with remote processes, which is performed on the critical path of local application execution.

In many cases, system consistency is not violated even if a process does not block-waiting until the lock is acquired, but rather continues its execution as if the lock acquisition operation had already been completed.

While this observation had been exploited to increase performance of shared memory multi-processor systems at the micro-architecture level, it had never been applied to the domain of fault-tolerant distributed systems.

In this work, we apply the concept of speculative lock acquisition to the domain of fault-tolerant distributed systems, eliminating traditional lock acquisition overheads. Moreover, applying speculative locking allows applications running on these systems to achieve the highest possible degree of parallelism, by enabling concurrent execution of critical sections protected by the same lock.

The proposed scheme relies on the ability of the underlying system to checkpoint and reestablish a process state. This capability is common in existing distributed software shared memory systems with fault-tolerance support. This makes speculative locking highly attractive for these systems.

We evaluate the performance of the speculative lock acquisition technique by implementing it in JavaSplit, an existing fault-tolerant distributed shared memory runtime for Java.