Early-Reply Components: Concurrent Execution with Sequential Reasoning

Generic software components have a reputation for being inefficient. Parallel implementations may improve performance, but can thwart reuse by being architecture-dependent or by exposing concurrency to client-side reasoning about component interactions. To address performance, we present Early-Reply as an alternative to blocking method invocations. Component operations can be partitioned into a material computation required to satisfy the postcondition, and a residual computation required to reëstablish the component invariant, optimize its representation, etc. Early-Reply exploits opportunities for parallelism by forwarding final parameter values to the caller as soon as the material computation completes, thereby offloading the residual computation to execute in parallel with subsequent client activities. Proof obligations for Early-Reply support a synchronous calling model, so clients can still reason sequentially about component behavior. Also, since Early-Reply components do not depend on system-wide support for component synchronization, they can be deployed incrementally. Finally, Early-Reply can improve the response time of idle components by orders of magnitude; when composed hierarchically, performance benefits are magnified by the potential fan-out of concurrently executing components.