journal_pinwheel abstract

We describe two families of asynchronous atomic broadcast protocols that provide good delivery and stability times, use a small number of messages to accomplish a broadcast, distribute evenly the load of ordering messages among group members, use efficient flow control techniques, and provide gracefully degraded performance in the presence of communication failures. The pinwheel protocols are designed for applications characterized by a uniform message arrival pattern. The on-demand protocol is designed for applications characterized by a non-uniform, bursty message arrival pattern. The protocols tolerate omission/performance communication failures and crash/performance process failures. Simulation studies on the pinwheel protocols demonstrate that they have superior performance over other well-known atomic broadcast protocols, for uniform message arrival rates. We also report the measurements taken on prototype implementations of the protocols, that show very good results and a substantial performance advantage of the on-demand protocol for non-uniform and intermediate message arrival patterns.