Concurrency bugs are easy to introduce but dif- ficult to detect, especially in implementations of distributed algorithms where concurrency non- determinism is an inherent problem. These bugs may only be identified under very specific order- ings of execution events, making them challenging to reproduce. Controlled concurrency testing tech- niques have been proposed to address the testing challenge, by taking over the scheduling of events, and effectively searching the state space of sched- ules to identify the concurrency bugs.
In this paper, we investigate and compare the per- formance of two concurrency exploration algo- rithms, probabilistic concurrency testing (PCT) and delay bounding strategy on our implementation of the HotStuff consensus protocol, which has been quite popular and was adopted by Meta for its Diem blockchain project. Our results suggest that can in- deed find concurrency bugs more frequently in our HotStuff implementation than the baseline random strategy. However, using different bound parame- ters for PCT and delay bounding does not have sig- nificant effect on bug finding performance on our benchmarks.

Consensus algorithms, as well as distributed systems in general, are vulnerable to concurrency bugs due to non-determinism. Such bugs are hard to detect since it is necessary to test using a lot of different scenarios and even then, there is no guarantee to find one.

Controlled concurrency testing is a proposed solution to that problem. Its main strength is allowing for more control over the order in which threads are executed, using controlled scheduling.

In this paper, we utilize Coyote, a concurrency testing framework, to test for concurrency bugs in PBFT, the seminal consensus algorithm. Random Walk, Delay-Bounding, Probabilistic Concurrency Testing (PCT) and Q-Learning are the exploration strategies we performed experiments with. The goal is to find schedules that lead to concurrency bugs. We test for 2 bugs that are seeded by us into the algorithm.

A comparison of the results shows that fair exploration strategies outperform their unfair variations. Finally, we conclude that PCT and fair PCT are the best-performing strategies for the benchmarks we use.

The testing of consensus systems has received growing attention and recent testing tools generate many faulty executions. However, there is a lack of methods that automatically analyze these outputs to identify the root causes of the bugs they found.
This paper presents Isolation, a statistical bug isolation algorithm that uses message-based predicates to discriminate between different faults. We applied our method to executions of the XRP Ledger blockchain and evaluated its performance. Our comparison shows that Isolation correctly separates bugs by their root cause and consistently outperforms the state-of-the-art with higher F-scores.