3 ms·
The family of problems where computing is non-deterministic and there is no single right answer is very large. Many gossiping algorithms belong to that family,
by dxbydt 15y ago
The family of problems where computing is non-deterministic and there is no single right answer is very large. Many gossiping algorithms belong to that family, as do several finance problems with an underlying stochastic model. Here's a very practical problem that I solve everyday that can benefit hugely from Ungar's model of nondeterministic concurrent computation : a bank makes n loans, with each loan having a different probability of default. The loans are all connected by a covariance matrix ie. given any two loans (p,q), we have a best guess of the chances of p defaulting if q defaults. At the end of 1 year, m of those n loans will default. But today, right now, the bank has to submit to the Fed its best guess of how much money it might lose at the end of next year! In finance, we call this "estimation of the conditional value at risk" aka cvar estimation. There is no right answer, m and n are in the millions, the covariance matrix is huge, the number of possible losses is scala.math.pow(2,m) which is essentially un-computable for even a very small m like 100 loans, so it is out of the question if m is millions of loans. Yet I perform this very calculation using a modest 100,000 simulations ( via Actors in Scala, 1 Monte Carlo simulation becomes 1 Actor iterating over a list of loans & computing their losses concurrently ). While I sort of converge to an answer, the computation is non-deterministic, there is no real right answer, and Ungar's model would be a clear win for this problem.