Early scheduling on steroids
boosting parallel state machine replication
Additional information
Authors
de Lima Batista E. R.,
Alchieri E.,
Dotti F.,
Pedone F.
Type
Journal Article
Year
2022
Language
English
Abstract
State machine replication (SMR) is a standard approach to fault tolerance in which replicas execute requests deterministically and often serially. For performance, some techniques allow concurrent execution of requests in SMR while keeping determinism. Such techniques exploit the fact that independent requests can execute concurrently. A promising category of early scheduling solutions trades scheduling freedom for simplicity, allowing to expedite decisions during scheduling. This paper generalizes early scheduling and proposes a general method to schedule requests to threads, restricting scheduling overhead. Moreover, it explores improvements to the original early scheduling mechanism, namely the use of busy-wait synchronization and work-stealing techniques. We integrate early scheduling and its proposed improvements to a popular SMR framework. Performance results of the basic mechanism and its improvements are presented and compared to more classic approaches, where it is shown that early scheduling with our proposed enhancements can outperform the original early scheduling and other systems by a large margin in many scenarios.
Keywords
State machine replication, Synchronization, Work-stealing, Scheduling
Journal
Journal of Parallel and Distributed Computing
Volume
163
Pages (or article number)
269–282
Diffusion
License
CC BY-NC-ND
Visibility
Public
Status open access
Hybrid
