dSort

An example of a distributed brute force sorting algorithm:

First, sign up for a DCP account at https://portal.distributed.computer and download your id.keystore and default.keystore associated with your account. For more information on how to do that, refer to this tutorial.

Setup

Create a directory for your project, and download the DCP packages.

npm i dcp-client

Next, make a JavaScript file and create the asynchronous main function. The program requires the dcp-client module to initialize access to the Compute API.

async function main() {
  const compute = require('dcp/compute');
  // Rest of our code will go in the following sections:
  /* INPUT DATA */

  /* WORK FUNCTION */

  /* COMPUTE FOR */

  /* PROCESS RESULTS */
}

require('dcp-client').init('https://scheduler.distributed.computer').then(main);

Input data

Within main(), the input data in this example is an array with length NUM, containing integers generated using Math.random, but feel free to replace this section with your own data.

/* INPUT DATA */
// Generate NUM random numbers between -49 and +50
const inputSet = [];
const outputSet = [];
const NUM = 50;

for (let i = 0; i < NUM; i += 1) {
  inputSet[i] = Math.floor(Math.random() * 100) - 49;
}

Work function

Still within main(), this is the function that each sandbox runs in parallel. DCP sends each value from the inputSet to a sandbox. The work function then compares this value to the rest of the array and return the index of that value in the outputSet.

/* WORK FUNCTION */
// Run by each sandbox for one value from the set
function workFn(value, set) {
  let index = 0;
  for (let j = 0; j < set.length; j += 1) {
    progress(j / set.length);
    if (set[value] > set[j]) index += 1;
  }
  return index;
}

compute.for

Now to set up the job. It’s passed an iterable that goes from 0 to inputSet.length - 1 so that DCP can send each value in the input to one sandbox. Passing [arguments] sends the inputSet to each sandbox. Then assign a public name for the job.

/* COMPUTE FOR */
// Set up compute.for with an iterable, a work function, and any arguments.
const job = compute.for(0, inputSet.length - 1, workFn, [inputSet]);
job.public.name = 'dSort';

Compute group

If you don’t need a compute group, skip this section. If you do need a group, enter this line with the join information for the group you have the authority to deploy to.

// SKIP IF: you don't need a compute group
job.computeGroups = [{ joinKey: 'Your Key', joinSecret: 'Your Key' }];

Process results

Next, the program waits for the results to come back. In resultSet, there is an array whose indices correspond to the indices of the input, but whose values correspond to the indices of the output.

/* PROCESS RESULTS */
let resultSet = await job.exec();
resultSet = Array.from(resultSet);

Now use the results to fill the sorted array, outputSet. In general, outputSet[resultSet[i]] = inputSet[i]. But, when there are two(+) inputs of the same value, they have the same output index instead of two(+) unique ones. To account for this, the algorithm pushes an index forward when it encounters an index that has already has a value.

// Creates sorted list from results (non-distributed)
for (let i = 0; i < resultSet.length; i += 1) {
  // First instance of value
  if (outputSet[resultSet[i]] === undefined) {
    outputSet[resultSet[i]] = inputSet[i];
  } else {
    // Further duplicates
    let next = 1;
    while (outputSet[resultSet[i] + next] !== undefined) {
      next += 1;
    }
    outputSet[resultSet[i] + next] = inputSet[i];
  }
}

Lastly, the program logs the results to the console.

console.log(inputSet);
console.log(outputSet);
console.log('Job Complete');

Full code

Click to see full code
async function main() {
  const compute = require('dcp/compute');
  const inputSet = [];
  const outputSet = [];
  const NUM = 100;

  // Fill input set with NUM random numbers
  for (let i = 0; i < NUM; i += 1) {
    inputSet[i] = Math.floor(Math.random() * 100) - 49;
  }

  // Distributed Work Function
  // Each slice loops once through the dataset and counts values below current slice value
  async function workFn(value, set) {
    let index = 0;
    for (let j = 0; j < set.length; j += 1) {
      progress(j / set.length);
      if (set[value] > set[j]) index += 1;
    }
    return index;
  }

  // Set up compute.for with an iterable, a work function, and any arguments.
  const job = compute.for(0, inputSet.length - 1, workFn, [inputSet]);
  job.public.name = 'dSort';

  // SKIP IF: you don't need a compute group
  // job.computeGroups = [{ joinKey: 'Your Key', joinSecret: 'Your Key' }];

  let resultSet = await job.exec();
  resultSet = Array.from(resultSet);

  // Creates sorted list from results (non-distributed)
  for (let i = 0; i < resultSet.length; i += 1) {
    // First instance of value
    if (outputSet[resultSet[i]] === undefined) {
      outputSet[resultSet[i]] = inputSet[i];
    } else {
      // Further duplicates
      let next = 1;
      while (outputSet[resultSet[i] + next] !== undefined) {
        next += 1;
      }
      outputSet[resultSet[i] + next] = inputSet[i];
    }
  }

  console.log(inputSet);
  console.log(outputSet);
  console.log('Job Complete');
}

require('dcp-client').init('https://scheduler.distributed.computer').then(main);