Distributed Computing (proposal)

AY 20/21 Sem 2 CS4215 Project: Distributed Computing for Source

Idea: Introduce Promises in Source 2 to facilitate distributed computing.

User Stories

User Story 1: Simple Display

1. Student A executes:

function my_shared_function(x) {
   display(x);
}
share(my_shared_function); // returns access-token

2. REPL displays the access token "2e7d5196-bc90-4482-9b9f-749b6c23b089"

3. Student A sends the access token to Student B (e.g. through Telegram)

4. Student B executes:

const promise = connect("2e7d5196-bc90-4482-9b9f-749b6c23b089"); 
then(promise, shared_function_from_a =>
    shared_function_from_a("hi there");
}

5. Student A sees "hi there" in their REPL

Story 2: Promise Chaining with Prompt

1. Student A executes (whats_your_name could be from a library):

function whats_your_name() {
    return prompt("what's your name?");
}
share(whats_your_name);

2. A's REPL shows string "2e7d5196-bc90-4482-9b9f-749b6c23b089"

3. Student A sends string to Student B

4. Student B executes

const promise = connect("2e7d5196-bc90-4482-9b9f-749b6c23b089");
then(promise, shared_function_from_a => {
    const my_promise = shared_function_from_a();
    then(my_promise, name => display(name));
}

5. Student A gets a prompt: "what's your name?", and enters "Raivat"

6. Student B sees "Raivat" in the REPL

Story 3: Distributed Computing with Divide-and-Conquer Algorithms

1. Both Student A and Student B have their individual copies of the following:

function merge_sort(data) {
    if (length(data) <= 1) {
        return data;
    } else {
        const result = split(data);
        const left = merge_sort(head(result));
        const right = merge_sort(head(tail(result)));
        return merge(left, right);
    }
}

function split(data) {
    const median = math_floor(length(data) / 2);
    function split_helper(left, right, n) {
        if (n === 0) {
            return pair(reverse(left), right);
        } else {
            return split_helper(pair(head(right), left), tail(right), n-1);
        }
    }
    return split_helper(list(), data, median);
}

function merge(left, right) {
    if (length(left) === 0) {
        return right;
    } else if (length(right) === 0) {
        return left;
    } else if (head(left) < head(right)) {
        return pair(head(left), merge(tail(left), right));
    } else {
        return pair(head(right), merge(left, tail(right)));
    }
}

2. Student A executes the following

share(merge_sort);

3. A's REPL shows string "2e7d5196-bc90-4482-9b9f-749b6c23b089"

4. Student B executes the following

const data = list(10, 12, 5, 6, 7, 13, 19);
function start_distribution() {
    const result = split(data);
    const promise = connect("2e7d5196-bc90-4482-9b9f-749b6c23b089");
    const sorted_data = then(promise, shared_merge_sort => {
        const left = shared_merge_sort(head(result));
        const right = merge_sort(head(tail(result)));
        return then(my_promise, left_result => merge(left, right));
    }
    return sorted_data;
}
const sorted_data = start_distribution(); 

5. After computation, the sorted data is stored in stored_data. The computation on the initial left and right happens simultaneously and on their respective systems. B as the controller performs the final merge to merge the results.