Transaction Internals: Recovery

A transaction must be always consistent and durable. This is straightforward when everything is normal, whereas maintaining such properties despite of failures becomes nontrivial. Failures like system crashes can leave a system in an inconsistent state. Today we are treating failures as the norm. It’s critical to possess the capability of fault tolerance. One important remedy is to recover transactions after crashes.

Read More

Algorithm Cheat Sheet: Majority Element

A majority element over a collection is the one that occurs more than half of all the elements in the collection. When there exists a majority, a sorted array has that majority element placed in the middle position. For an unsorted array, a majority element can be identified by the times of its appearance (a hash table can be used to track the appearance of each unique element). Both sorting and hash tables involve certain overhead of time and space. Here we are studying Boyer–Moore majority vote algorithm which identifies the majority element in linear time with constant space.

Read More