In the context of distributed system, transaction basically means a series of RPC operations executed by client. The idea here is similar to the transaction in RDBMS.

RPC is a important abstraction for processes to call functions in other processes. In the context of distributed system, it is heavily used and are crucial.

For mutual Exclusion in Distributed System, we need to guarantee 3 propterties:

1. Safety (essential): Nothing bad happens
2. Liveness (essential): Every request is granted eventually
3. Ordering (desirable): Requests are in order of they made

Common solution such as semaphore is not plausible in DS since there is not shared resources in DS.

So, we have different solution for this problem:

The Leader Election Problem is classical and has been useful in many variants of systems, including cloud computing systems.

What is leader ?

leader, in the context of solving distributed system problem, refers to a server who is responsible for receiving all reads and writes. It is useful for coordination among distributed systems.

Leader detection problem

In a group of processes, elect a leader and let everyone know in the group about this leader.

When a leader fails, by using failure detector, some process will detect this. The focus of election algorithm is to ensure:

1. Elect one leader only among the non-failed processes.

2. All non-failed processes in the group agree on the (new) leader.

Binary Search is one of the most common techniques being used in scenarios of searching. It has many types of variants and I would like to discuss some of it and why the edge cases are designed like this.

1.Search for a element in array (familiar)

This is probably the most common way to use binary search. It involves finding mid point within a range and thus divides the range (smaller the search range) based on the midpoint. Common implementation is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // key criterion 

    while(left <= right) { // key criteria
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; // key criterion, directly return
        else if (nums[mid] < target)
            left = mid + 1; // key criterion
        else if (nums[mid] > target)
            right = mid - 1; // key criterion
    }
    return -1;
}

Some important value includes: value of initial right, different value assignment in three different cases (less than, larger than, or equal to), and the criterion of while loop (< or <= ?).

1. value of right: By assigning “nums.length - 1”, we means that we are searching in range [left, right] (right boundary inclusive).If “nums.length”, then we are saying [left, right) (right boundary inclusive)

2. while loop criterion (< or <=) : By assigning <, we should jump out of the loop when left == right, which means that [left, right] will results in a omitted value, and [left, right) will not omit. Therefore when we pick the criterion, we should adjust the initial value of right accordingly to avoid unexpected behavior.

In short: (right = nums.length - 1, then while <=), (right = nums.length, then while <)

The experience of implementing Gossip/SWIM in Multicast through Coursera Cloud Computing course.

Virtual Memory Concepts

Virtual Memory

When process runs, page containing data that currently accessing (working set) will be mapped to physical ram.

RPC stands for remote procedure calls.

Complexity and latency of RPC vs. local calls?