2PC (Two Phase Commit)

In this post, I will discuss two phase commit (aka 2PC) distributed transaction commit protocol and some of the problems associated with it. What is a distributed commit protocol? A commit protocol is an algorithm used for atomically committing a transaction. Atomicity implies that either all the changes (writes / updates) in the transaction will... Continue Reading →

Optimistic Locking

In this post, I will briefly discuss optimistic locking technique, its advantages and potential use cases. Pessimistic locking protocol Let's first discuss the opposite of optimistic locking to setup the context. Pessimistic locking is the main locking paradigm used for guaranteeing mutual exclusion for a given piece of code subject to execution by reader and... Continue Reading →

Notes on Lock Free Programming (Part 1)

With the advent of multi-core architectures, it is becoming increasingly important to build scalable data structures that support the basic operations (insert, search) without taking coarse grained locks. Coarse grained locks are usually taken on the entire data structure and prevent any other concurrent thread(s) from operating even on other disjoint/orthogonal parts of the data... Continue Reading →

Extendible Hashing

In the previous post, I had given a brief description of Linear Hashing technique. In this post, I will talk about Extendible Hashing. Like Linear Hashing, Extendible Hashing is also a dynamic hashing scheme. First let's talk a little bit about static and dynamic hashing as I had skipped this part in my previous post.... Continue Reading →

Linear Hashing

In this blog post, I will give an introduction to a hashing methodology called Linear Hashing. Hash Table Detour A hash table is a well known in-memory structure that supports key-value access with lookup cost being amortized O(1). The hash table is just an array, and each location/index in the array stores a <KEY,VALUE> item.... Continue Reading →

Fenwick Trees

In this post I will talk about Fenwick Trees aka Binary Indexed Trees. I got to use them recently while solving a problem in a coding challenge. Problem: Let's say we have an array of N positive integers. We need to be able to serve the following two operations efficiently: GetPrefixSum(i) - Gets the cumulative... Continue Reading →

Create a free website or blog at WordPress.com.

Up ↑

%d bloggers like this: