A Machine Learning Approach to Performance Prediction of Total Order Broadcast Protocols

M. Couceiro, Paolo Romano and L. Rodrigues

Selected sections of this report were published in the proceedings of the 4th IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO), Budapest, Hungary, September 2010.


Total Order Broadcast (TOB) represents a fundamental component for building strongly consistent, fault-tolerant replicated systems. While it is widely known that the performance of existing algorithms varies greatly depending on the workload and deployment scenarios, the problem of how to forecast the performance of TOB protocols in realistic settings is, at current date, still largely unexplored. This represents a major impairment to the adoption of self-optimizing replication schemes.

In this paper we address this problem by exploring the possibility of leveraging on machine learning techniques for building, in a fully decentralized fashion, performance models of TOB protocols. Based on an extensive experimental study considering heterogeneous workloads and multiple TOB protocols, we assess the accuracy and efficiency of alternative machine learning methods including neural networks, support vector machines, and decision tree-based regression models. We also propose two heuristics for the feature selection phase, that allow to reduce its execution time up to two orders of magnitude, incurring in a very limited loss of prediction accuracy.

Also available extended report (pdf)

Luís Rodrigues