Proposed Optimizations For Distributed Consensus
Proposed optimizations for distributed consensus (from Distributed consensus revised , Howard) 1) Add negative responses (NACKs) to reduce wasted waiting/timeouts ==Classic Paxos can be improved by adding negative res...
Proposed optimizations for distributed consensus (from Distributed consensus revised , Howard) 1) Add negative responses (NACKs) to reduce wasted waiting/timeouts ==Classic Paxos can be improved by adding negative responses== such as no promise(e) and no accept(e) .[:cite[1]{ln=1}] These are sent by acceptors when they receive prepare / propose messages with an epoch e lower than their last promised epoch epro .[:cite[1]{ln=2}], [:cite[2]{ln=2}] When a proposer receives these negative responses, ==it can restart the proposal with a higher epoch== (rather than waiting for a timeout).[:cite[1]{ln=3}], [:cite[2]{ln=3}] The proposer can also ignore negative responses and wait for a majority of positive responses, but ==if it receives negative responses from a majority, the proposal will not succeed and it should restart==.[:cite[1]{ln=4}], [:cite[1]{ln=5}] The report also notes that ==it is safe for a proposer to abandon/restart at any stage==, equating it to a proposer failing and restarting.[:cite[1]{ln=6}] A further refinement is that acceptors can include extra metadata in negative responses—e.g., no promise(e,f) / no accept(e,f) (where f is the acceptor’s last promised epoch), or even include the last accepted proposal (g,v) —to help proposers advance more directly.[:cite[3]{ln=1}] 2) Use NACK information to skip unlikely to succeed epochs In the provided algorithm sketch, if the proposer receives no promise(e,f) or no accept(e,f) , it ==restarts and skips all epochs ≤ f == by restricting its candidate epoch set E to epochs greater than f .[:cite[4]{ln=3}] 3) Broad direction of optimizations: optimize/extend Paxos to mitigate limitations The report frames Paxos as “heavyweight, unscalable and unreliable in practice,” and explicitly states it has been the subject of extensive research to ==optimise its performance and mitigate its limitations==.[:cite[5]{ln=4}], [:cite[5]{ln=5}] It further positions its implications as ranging from ==“pragmatic optimisations to production systems”== to novel approaches affecting performance/scalability/reliability.[:cite[6]{ln=6}] Missing Content (could not be safely extracted here) The report’s table of contents indicates additional concrete “Known revisions” (e.g., “Bypassing phase two,” “Termination,” “Distinguished proposer,” “Multi Paxos,” “Proposal copying,” “Generalisation to quorums,” and “non majority quorums”).[:cite[7]{ln=35}], [:cite[7]{ln=61}], [:cite[7]{ln=91}], [:cite[7]{ln=126}], [:cite[7]{ln=188}], [:cite[8]{ln=33}], [:cite[9]{ln=96}] It also lists “Quorum intersection revised” implications such as “Co location of proposers and acceptors,” “Multi Paxos,” and “Voting for epochs.”[:cite[10]{ln=329}], [:cite[10]{ln=345}], [:cite[10]{ln=376}] However, in the accessible page views, many of these sections’ bodies were not retrievable (the tool output repeatedly returned mostly TOC/boilerplate rather than the actual section text), so I cannot summarize those optimizations without risking uncited or inaccurate claims.[:cite[7]{ln=35}], [:cite[11]{ln=1}], [:cite[12]{ln=1}]