Performance Evaluation of a Multi-Folder Ring Protocol for Total Ordering of Messages

Abstract

In a system containing several distributed servers, messages of random sizes generated at different locations must be disseminated and processed in the same order by all hosts. A ring protocol is defined, where a number of folders carrying messages circulate in one direction without overtaking each other. A model involving parallel queues is analysed in the steady state and is solved approximately, allowing the computation of performance measures. A number of example systems are evaluated numerically and by simulations, leading to a heuristic for choosing the optimal number of folders.