Using error-correcting codes to solve distributed agreement problems: a future direction in distributed computing?

摘要: The Consensus problem lies at the heart of many distributed computing problems one has to solve when designing reliable applications on top unreliable asynchronous systems. There is a large literature where theoretical and practical aspects this are studied1, that can be informally stated in terms three requirements. Each process proposes value, decide value (termination) such there single decided (agreement), proposed (validity). One most fundamental impossibility results says apparently simple no deterministic solution an system even if only may crash [3.9].To circumvent impossibility, known as FLP, two main approaches have been investigated. them consists relaxing requirements problem, by either allowing for probabilistic solutions (e.g., [3.4]), or approximate (e-agreement [3.8], k-set agreement [3.6]). Another approach enriching with synchrony assumptions until they allow solved [3.7]. This abstracted notion failure detectors [3.5]. also studies hybrid approaches, like combining detection randomization [3.2], 3.21].