PolitePaxos: A New Consensus Variant Where the Proposer Just Asks Nicely
Paxos consensus protocol, despite its many theoretical virtues, is fundamentally rude. One need only look at the way it behaves to see the problem.
A leader seizes power. It dictates values. When two leaders happen to propose simultaneously, they do not pause, tip their hats, and work things out over tea. No, they duel, each furiously incrementing ballot numbers at the other like barbarians engaging in a perpetual pissing contest (please excuse my language). The follower nodes, meanwhile, are reduced to the role of obedient subjects, promising their allegiance to whichever proposer shouts loudest and most recently.
Having spent decades studying this rude behavior (with WPaxos, PigPaxos, and through a great many posts on this very blog) I became convinced that the field had made a fundamental error. We had been asking "how do we reach agreement?" when the real question we should have been asking, all along, was "would it kill you to ask nicely?"
It is therefore with considerable pride that I present PolitePaxos, which we believe to be the first consensus protocol that could be used in polite company. In PolitePaxos the Prepare and Promise phases are replaced with a single Polite Request phase. The proposer does not demand promises. It introduces itself, compliments the acceptors on their uptime. (In testing, the compliment "you have lovely page cache hit rates" proved most effective. "Is that a new kernel?" was also well-received.) It then explains why it believes this particular value might be rather nice if it isn't too much trouble, and then waits. We formalize politeness as a tuple (courtesy_level, sincerity_score, compliment_quality) and prove that when all three exceed a threshold Ï„, consensus is reached in a single round, assuming no sociopathic nodes.
Early results were extremely encouraging... right up until the moment they became catastrophic. The problem arose when two nodes happened to submit concurrent Polite Proposals. What followed was not a leader duel but something far worse: an infinite loop of mutual deference. "Oh no, please, your value is far more deserving." "I couldn't possibly, yours is clearly the superior proposal." "I absolutely insist." "No, I absolutely insist." Both nodes continued doing so with increasing sincerity until the cluster ground to a halt. Anyone who has ever tried to enter a doorway at the same time as another British person, or anyone familiar with the Persian social protocol of taarof, will recognize this failure mode immediately: an infinite, perfectly symmetrical, exquisitely polite livelock! The logs were the most courteous system failure we had ever witnessed.
Our solution, after considerable anguish and several pots of tea, was the introduction of a Pre-Pre-Pre-Polite Vibecheck Phase. Before a node so much as thinks about proposing a value, it sends a tentative, noncommittal, almost apologetic probe to the cluster. Not a proposal, not even a pre-proposal, but a sort of gentle clearing of the throat, a conversational "I don't suppose anyone would mind terribly if I were to, at some point, perhaps, maybe, suggest something?" If the vibes come back favorable, the node proceeds to the Polite Request. If another node is already vibechecking, the node with the lower timestamp gracefully withdraws, muttering that it wasn't that important anyway.
This resolved the taarof livelock entirely and restored liveness, though we note that the three additional sub-rounds of pre-politeness have increased latency to what we describe in the paper as leisurely. I had previously built a BeatPaxos simulator for classic Paxos. You can go play with it to see just how boorish the original protocol is. We intend to build a PolitePaxos simulator as well, just as soon as we can figure out how to animate a node looking embarrassed. The full paper is available on our website, but only if you ask nicely.
Happy April Fools' Day.
Comments