Performance of Pipelined Asynchronous Systems

Abstract. A testing-based faster-than relation has previously been de-veloped that compares the worst-case efficiency of asynchronous systems. This approach reveals that pipelining does not improve efficiency in gen-eral; that it does so in practice depends on assumptions about the user behaviour. Accordingly, the approach was adapted to a setting where user behaviour is known to belong to a specific, but often occurring class of request-response behaviours; some quantitative results on the efficiency of the respective so-called response processes were given. In particular, it was shown that in the adapted setting a very simple case of pipelined process with two stages is faster than a comparable atomic processing. In this paper, we determine the performance of general pipelines, study whether the adapted faster-than relation is compatible with chaining (used to build pipelines) and two other operators, and give results on the performance of the resp. compositions, demonstrating also how rich the request-respond setting is.