AWhat changed
Ben-Or presents randomized binary-agreement protocols for fully asynchronous message-passing systems: crash tolerance with N>2t and a Byzantine construction with N>5t, with probability-one termination under the stated admissible scheduling model.
Scientific scope
Ben-Or presents randomized binary-agreement protocols for fully asynchronous message-passing systems: crash tolerance with N>2t and a Byzantine construction with N>5t, with probability-one termination under the stated admissible scheduling model. The 1983 target is a four-page extended abstract, not a full proof article. N is a fixed process population and t a fault bound; fair admissible schedules eventually deliver messages to continuing correct receivers. Crash and Byzantine protocols have different sufficient thresholds, N>2 t and N>5 t. Byzantine senders must be identifiable; no Sybil/open-membership guarantee follows. The scheduler may use past/current state, not unspecified foreknowledge of future random choices. Probability-one termination does not mean every random tape terminates or impose a wall-clock deadline. The efficiency discussion allows exponential expected rounds; the introduction explicitly limits constant expected rounds for t=O(sqrt(N)) to synchronous execution. Source theorem wording sometimes says all processes in the crash case, but already crashed processes need not decide. The account does not certify a complete pseudocode transcription or reconstruct the omitted proof details. Its 1983 uncertainty about the 5 t bound is not a claim that this remains optimal or open today. No proof/model checking or live protocol replay was performed. FLP, prior randomized synchronization and later improved protocols retain separate ownership. Agreement does not establish scientific correctness.
Evidence
Source-linked, scoped account of the original work. The published scope states the scientific assumptions and remaining verification limits. WRS has not independently certified the full proof, experimental result or system benchmark.
Contributors
- Michael Ben-Or · SCIENCE: Original source-listed scientific author of this scoped work; byline does not determine effort fractions.
- Ben-Or, Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols, PODC 1983 extended abstract
- Hebrew University research output: Ben-Or 1983 original byline, year and pages
Provisional WRS assessment, edition 2026-10-16.1. Independent expert calibration is pending. This grade does not certify correctness or assign ownership.
Full scientific record · Browse contribution grades · Request a correction