This paper describes a variety of techniques from over a decade of developing Aerospike (formerly Citrusleaf), a real-time DBMS that is being used in some of the world's largest mission-critical systems that require the highest levels of performance and availability. Such mission-critical systems have many requirements including the ability to make decisions within a strict real-time SLA (milliseconds) with no downtime, predictable performance so that the first and billionth customer gets the same experience, ability to scale up 10X (or even 100X) with no downtime, support strong consistency for applications that need it, synchronous and asynchronous replication with global transactional capabilities, and the ability to deploy in any public and private cloud environments. We describe how using efficient algorithms to optimize every area of the DBMS helps the system achieve these stringent requirements. Specifically, we describe, effective ways to shard, place and locate data across a set of nodes, efficient identification of cluster membership and cluster changes, efficiencies generated by using a 'smart' client, how to effectively use replications with two copies replication instead of three-copy, how to reduce the cost of the realtime data footprint by combining the use of memory with flash storage, self-managing clusters for ease of operation including elastic scaling, networking and CPU optimizations including NUMA pinning with multi-threading. The techniques and efficiencies described here have enabled hundreds of deployments to grow by many orders of magnitude with near complete uptime.

This paper discusses a parallel implementation of the e-relaxation algorithm for the rein-cost flow problem on the CM-5.There is considerable loss in et%ciency in going from one processor sequential implementation to one processor parallel implementation.While a naive parallelization is shown to have very low parallelism, we investigate the effectiveness of a set of algorithmic augmentations.These augmentations work by either eliminating non-parallel iterations or increasing the parallelism of the remaining iterations.Although the size of memory on the machine limits the size of problems used in our experiments, experimental scalability data shows that the parallel implementation may be able to beat the best sequential implementation on large enough problems.1 *Some of the performance data presented in this paper was derived using CMMD2.0-betaand CMOST7.2-betawhich are prerelease versions of system softwere for the CM-S from Thinking Machines Corp.

Using the ideas from the NC algorithm of Ben-Or and Tiwari [Journal of Complexity 6, 417-442, 1990], we develop a practical parallel algorithm that approximates the roots of a polynomial whose roots are all real.A new elementary proof of correctness is provided and the complexity of the algorithm is analyzed.A particular implementation of the algorithm that performs well in practice is described and its run-time behaviour is compared with the analytical predictions.Its performance is also compared with that of the root-finding algorithm in the PARI package.