A TMR scheduler guarantees that nonfaulty nodes execute the same transactions in the same order. The authors propose a high-performance scheduler that uses premature scheduling, null transactions, and message batching to support dynamic policy changes as load varies. A TMR scheduler guarantees that transactions submitted to perfect nodes are eventually scheduled at all perfect nodes and that transactions submitted to faulty nodes are either scheduled at all perfect nodes or never scheduled at any perfect node. The scheduler depends on a reliable broadcast algorithm that guarantees determinism and prevents faulty nodes from spoofing remote schedulers. The scheduler prevents a faulty node from swamping the system with a stream of spoofed messages by dropping excess messages.
Perfect nodes obey a backoff discipline that limits the messages they initiate.
The scheduler uses a fixed delay backoff, but it appears that a variable delay could be used if needed. A sequence number discipline allows premature scheduling when there are no faulty nodes. Premature scheduling depends on a steady stream of transactions, so for light loads null transactions are generated to induce premature scheduling. Each transaction generates four messages, so at heavy loads transaction batching improves performance. The cumulative improvement amounts to a factor of five in throughput and response.