Distributed algorithm to compute the balance of the parentheses

I would apply the map-reduce algorithm in which the map function would compute a part of the string return either an empty string if parentheses are balanced or a string with the last parenthesis remaining.

Then the reduce function would concatenate the result of two returned strings by map function and compute it again returning the same result than map. At the end of all computations, you'd either obtain an empty string or a string containing the un-balanced parenthesis.

You can break the string into chunks and process each separately, assuming you can read and send to the other machines in parallel. You need two numbers for each string.

1. The minimum nesting depth achieved relative to the start of the string.

2. The total gain or loss in nesting depth across the whole string.

With these values, you can compute the values for the concatenation of many chunks as follows:

minNest = 0
totGain = 0
for p in chunkResults
  minNest = min(minNest, totGain + p.minNest)
  totGain += p.totGain
return new ChunkResult(minNest, totGain)

The parentheses are matched if the final values of totGain and minNest are zero.