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.

Set up

First, set up an HTML file. Requiring the dcp-client library in the first script tag allows the app to distribute work. Some pre-written HTML displays the output, but the rest of the tutorial is in JavaScript within the second script tag.

<!DOCTYPE html>
<html>
  <head>
    <script src="https://scheduler.distributed.computer/dcp-client/dcp-client.js"></script>
    <script>
      // The rest of the code will go here!
    </script>
  </head>
  <body>
    <p>Input Size: <input type="text" id="input-size" value="25" /></p>
    <input type="button" id="deploy" value="Deploy" onclick="deploy()" />
    <p>Input: <span id="input"></span></p>
    <p>Output: <span id="output"></span></p>
  </body>
</html>

Input data

Next, create a function to generate random numbers to use as the input set.

/* INPUT SET */
function generateInputSet(size) {
  const set = [];
  for (let i = 0; i < size; i += 1) {
    set.push(Math.floor(Math.random() * 100));
  }
  return set;
}

Work function

Each worker runs the work function on one element of the input set. In this case, each worker takes one input value, and determine its index in the output set.

/* WORK FUNCTION */
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 set up the DCP job. The function deploy() launches the job using the compute.for() statement. Pass it an iterable that goes from 0 to inputSet.length - 1 so that each value in the input gets sent to one sandbox. Here,[arguments] sends the inputSet to each sandbox. Assign a public name for the job.

async function deploy() {
  // Some application-specific, HTML set up.  Not important to DCP
  const inputSize = document.getElementById('input-size').value;
  const inputSet = generateInputSet(inputSize);
  document
    .getElementById('input')
    .appendChild(document.createTextNode(inputSet));

  /* COMPUTE FOR */
  const { compute } = dcp;
  const job = compute.for(0, inputSet.length - 1, workFn, [inputSet]);
  job.public.name = 'dSort - Web';
}

Compute group

If you don’t need a compute group, skip this section. If you do, enter this line with the key information to join that group.

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

Process results

Next, await the results. The results, resultSet, are store in 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);
const outputSet = [];

The rest of this is app-specific, not DCP-specific. Next, use the results to fill a sorted array, outputSet. In general, outputSet[resultSet[i]] = inputSet[i]. When two(+) inputs have the same value, they have the same output index instead of two(+) unique ones. To account for this, push forward an index when arriving at an index that’s already full.

// 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];
  }
}

document
  .getElementById('output')
  .appendChild(document.createTextNode(outputSet));

Run it

Open your HTML file in a web browser, and press deploy.

Full code

Click to see full code
<!DOCTYPE html>
<html>
  <head>
    <script src="https://scheduler.distributed.computer/dcp-client/dcp-client.js"></script>
    <script>
      /* INPUT SET */
      function generateInputSet(size) {
        const set = [];
        for (let i = 0; i < size; i += 1) {
          set.push(Math.floor(Math.random() * 100));
        }
        return set;
      }

      /* WORK FUNCTION */
      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;
      }

      async function deploy() {
        // Some application-specific, HTML set up.  Not super important to DCP
        const inputSize = document.getElementById('input-size').value;
        const inputSet = generateInputSet(inputSize);
        document
          .getElementById('input')
          .appendChild(document.createTextNode(inputSet));

        /* COMPUTE FOR */
        const { compute } = dcp;
        const job = compute.for(0, inputSet.length - 1, workFn, [inputSet]);
        job.public.name = 'dSort - Web';
        // job.computeGroups = [{ joinKey: '', joinSecret: '' }];

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

        // Creates sorted list from results (non-distributed)
        for (let i = 0; i < resultSet.length; i += 1) {
          if (outputSet[resultSet[i]] === undefined) {
            outputSet[resultSet[i]] = inputSet[i];
          } else {
            let next = 1;
            while (outputSet[resultSet[i] + next] !== undefined) {
              next += 1;
            }
            outputSet[resultSet[i] + next] = inputSet[i];
          }
        }
        document
          .getElementById('output')
          .appendChild(document.createTextNode(outputSet));
      }
    </script>
  </head>
  <body>
    <p>Input Size: <input type="text" id="input-size" value="25" /></p>
    <input type="button" id="deploy" value="Deploy" onclick="deploy()" />
    <p>Input: <span id="input"></span></p>
    <p>Output: <span id="output"></span></p>
  </body>
</html>