Byzantine Generals and Transaction Commit Protocols

I visited Michael Fischer at Yale in the spring of 1982. It was known that solutions to the Byzantine generals problem that can handle n Byzantine failures require n+1 rounds of communication. While I was at Yale, Fischer and I proved that this number of rounds were needed even to handle more benign failures.

On the trip back home to California, I got on an airplane at Laguardia Airport in the morning with a snowstorm coming in. I got off the airplane about eight hours later, still at Laguardia Airport, having written this paper. I then sent it to Fischer for his comments. I waited about a year and a half. By the time he finally decided that he wasn’t going to do any more work on the paper, subsequent work by others had been published that superseded it.