Top

The Journal of Supercomputing

Published in:

07-09-2022

A randomized algorithm for the wait-free consensus problem

Authors: Radha Rani, Dharmendra Prasad Mahato

Published in: The Journal of Supercomputing | Issue 4/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

A wait-free consensus technique is provided with endless processes utilizing a shared memory model. When a powerful adversary is allowed to view and destroy infinite number of votes, the approach weighted voting can be used to reach consensus with at least constant probability. In asynchronous system, there is no known upper bound to transmit the message from source to destination processor. This paper presents a resilient and message-efficient algorithm by aggregating the votes of individual processors to solve the wait-free consensus in asynchronous systems. We considered an adaptive adversary and message-passing communication system. Our aim is to construct a message-passing algorithm equivalent to a weak shared coin and to provide a message-efficient algorithm for aggregating the votes of individual processors. A processor announces votes to smaller groups before propagating them to larger ones. To limit generated, received, or sent, vote weights are gradually increased. The wait-free consensus problem is optimally solved by our algorithm, which demonstrates an effective message-passing execution of the shared coin. When less than n/2 processes are faulty or crashed, the predicted message complexity of this randomized consensus procedure is O (n² (log log n)²). This is a linear improvement over the previous best protocol and is close to a message lower bound.

previous article Low-latency and High-Reliability FBMC Modulation scheme using Optimized Filter design for enabling NextG Real-time Smart Healthcare Applications

next article Archimedes optimizer-based fast and robust fuzzy clustering for noisy image segmentation

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Baliga A (2017) Understanding Blockchain Consensus Models [White Paper]. Semanticscholar.org, 4:1–14, [Online]. Available: https://www.persistent.com/wp-content/uploads/2017/04/WP-Understanding-Blockchain-Consensus-Models.pdf

Nawab F, Sadoghi M (2019) Blockplane: a global-scale byzantizing middleware. In: Proc Int Conf Data Eng, pp 124–135. Doi: https://doi.org/10.1109/ICDE.2019.00020

Fischer MJ, Lynch NA, Paterson MS (1985) Impossibility of distributed consensus with one faulty process. J Assccktion Comput Mach 32(2):374–382CrossRefMATH

Loui M, Abu-Amara H (1987) Memory requirements for agreement among unreliable asynchronous processes. Adv Comput Res 4:163–183

Srinivasan S, Kandukuri R (2022) Solving consensus in true partial synchrony. IEEE Trans Parallel Distrib Syst 33(12):3478–3490. https://doi.org/10.1109/TPDS.2022.3156925CrossRef

Aguilera MK, Toueg S (2012) The correctness proof of Ben-Or’s randomized consensus algorithm. Distrib Comput 25(5):371–381. https://doi.org/10.1007/s00446-012-0162-zCrossRefMATH

Aspnes J (1998) Lower bounds for distributed coin-flipping and randomized consensus.pdf. J ACM 45(3):415–450CrossRefMATH

Pease M, Shostak R, Lamport L (1980) Reaching agreement in the presence of faults. J ACM 27(2):228–234. https://doi.org/10.1145/322186.322188CrossRefMATH

Pirnazar M et al (2018) The evaluation of the usage of the fuzzy algorithms in increasing the accuracy of the extracted land use maps. Int J Glob Environ Issues 17(4):307–321. https://doi.org/10.1504/IJGENVI.2018.095063CrossRef

10.

Trivedi SA, Pattanaik KK (2020) A sensor-actor coordination protocol for variable rate irrigation. In: 14th IEEE Int Conf Appl Inf Commun Technol AICT 2020—Proc, pp 1–6, Doi: https://doi.org/10.1109/AICT50176.2020.9368742

11.

Aspnes J (2003) Randomized protocols for asynchronous consensus. Distrib Comput 16(2–3):165–175. https://doi.org/10.1007/s00446-002-0081-5CrossRefMATH

12.

Aspnes J, Attiya H, Censor K (2008) Randomized consensus in expected O(n log n) individual work. Proc Annu ACM Symp Princ Distrib Comput, pp 325–333. Doi: https://doi.org/10.1145/1400751.1400794

13.

Aspnes J, Attiya H, Censor K (2012) Polylogarithmic concurrent data structures from monotone circuits. J ACM 59(1), 24

14.

Aspnes J, Herlihy M (1990) Fast randomized shared consensus memory * using. J Alg, vol 461

15.

Aspnes J , Waarts O (1996) Randomized consensus in expected o(nlog2n) operations per processor* 25(5):1024–1044

16.

Attiya H (2008) Tight bounds for asynchronous randomized consensus.pdf 55(5):26

17.

Bracha G, Rachman O (1992) Randomized consensus in expected O(n2 log n) operations. Lect Notes Comput Sci (including Subser Lect Notes Artif Intell Lect Notes Bioinf), vol 579 LNCS, pp 143–150. Doi: https://doi.org/10.1007/BFb0022443

18.

Fich F, Herlihy M, Shavit N (1998) On the space complexity of randomized synchronization. J ACM 45(5):843–862. https://doi.org/10.1145/290179.290183CrossRefMATH

19.

Alistarh D, Aspnes J, King V, Saia J (2018) Communication-efficient randomized consensus. Distrib Comput 31(6):489–501. https://doi.org/10.1007/s00446-017-0315-1CrossRefMATH

20.

Chandra TD (1996) Polylog randomized wait-free consensus. Proc Annu ACM Symp Princ Distrib Comput, pp 166–175. Doi: https://doi.org/10.1145/248052.248083

21.

Attiya H, Bar-Noy A, Dolev D (1995) Sharing memory robustly in message-passing systems. J ACM 42(1):124–142. https://doi.org/10.1145/200836.200869CrossRefMATH

22.

Wang H, Lin B (2007) Pipelined van emde boas tree: algorithms, analysis, and applications. Proc IEEE INFOCOM, pp2471–2475. Doi: https://doi.org/10.1109/INFCOM.2007.303

23.

Aspnes J, Censor K (2010) Approximate shared-memory counting despite a strong adversary. ACM Trans Algo 6(2):25

24.

Chor B, Israeli A, Li M (1987) On processor coordination using asynchronous hardware. Proc Annu ACM Symp Princ Distrib Comput, vol Part F1302, pp 86–97. Doi: https://doi.org/10.1145/41840.41848

25.

Abrahamson K (1988) On achieving consensus using a shared memory. Proc Annu ACM Symp Princ Distrib Comput, vol Part F1301, pp 291–302. Doi: https://doi.org/10.1145/62546.62593

26.

Saks M, Shavit N, Woll H (1991) Optimal time randomized consensus—Making resilient algorithms fast in practice. Proc Annu ACM-SIAM Symp Discret Algo, pp 351–362

27.

Lundstrom O, Raynal M, Schiller EM (2021) Self-stabilizing multivalued consensus in asynchronous crash-prone systems. Proc 2021 17th Eur Dependable Comput Conf EDCC, pp 111–118. Doi: https://doi.org/10.1109/EDCC53658.2021.00023

28.

Alistarh D, Ellen F, Rybicki J (2021) Wait-free approximate agreement on graphs. Lect Notes Comput Sci, 12810

29.

Guerraoui R, Kuznetsov P, Monti M, Pavlovic M, Seredinschi DA (2022) The consensus number of a cryptocurrency. Distrib Comput 35(1):1–15. https://doi.org/10.1007/s00446-021-00399-2CrossRefMATH

30.

Lamport L, Shostak R, Pease M (1982) The byzantine generals problem. ACM Trans 4(3):382–401MATH

31.

Raynal M, Taubenfeld G (2021) Fully anonymous consensus and set greement algorithms. Netw Syst. pp 314–328

32.

Herlihy M (1991) Wait-free synchronization. ACM Trans Program Lang Syst 13(1):124–149. https://doi.org/10.1145/114005.102808CrossRef

33.

Perrin M, Mostéfaoui A, Bonin G, Courtillat-Piazza L (2022) Extending the wait-free hierarchy to multi-threaded systems. Distrib Comput. https://doi.org/10.1007/s00446-022-00425-xCrossRefMATH

34.

Heydari H, Silvestre G, Arantes L (2021) Efficient consensus-free weight reassignment for atomic storage. 2021 IEEE 20th Int Symp Netw Comput Appl NCA 2021. Doi: https://doi.org/10.1109/NCA53618.2021.9685401.

35.

Chlebus BS, Kowalski DR (2006) Time and communication efficient consensus for crash failures. Distrib Comput, vol 4167

36.

Chlebus BS, Kowalski DR (2006) Robust gossiping with an application to consensus. J Comput Syst Sci 72(8):1262–1281. https://doi.org/10.1016/j.jcss.2006.08.001CrossRefMATH

37.

Chlebus BS, Kowalski DR (2009) Fast scalable deterministic consensus for crash failures categories and subject descriptors. Science(80):111–120

38.

Biswas A, Tripathi AK, Aknine S (2021) Lea-TN: leader election algorithm considering node and link failures in a torus network. J Supercomput 77(11):13292–13329. https://doi.org/10.1007/s11227-021-03803-7CrossRef

39.

Hu C, Liu P, Guo S (2016) Public key encryption secure against related-key attacks and key-leakage attacks from extractable hash proofs J. Ambient Intell Humaniz Comput 7(5):681–692. https://doi.org/10.1007/s12652-015-0329-0CrossRef

40.

Taloba AI, Elhadad A, El-Aziz RMA, Shahin OR (2021) Prediction of data threats over web medium using advanced blockchain based information security with crypto strategies. J Ambient Intell Humaniz Comput. https://doi.org/10.1007/s12652-021-03109-9CrossRef

41.

Eom S, Huh JH (2018) Group signature with restrictive linkability: minimizing privacy exposure in ubiquitous environment. J Ambient Intell Humaniz Comput 1–11. https://doi.org/10.1007/s12652-018-0698-2

42.

Ramesh D, Mishra R, Trivedi MC (2021) PCS-ABE (t, n): a secure threshold multi authority CP-ABE scheme based efficient access control systems for cloud environment. J Ambient Intell Humaniz Comput 12(10):9303–9322. https://doi.org/10.1007/s12652-020-02643-2CrossRef

43.

Bojjagani S, Sastry VN, Chen CM, Kumari S, Khan MK (2021) Systematic survey of mobile payments, protocols, and security infrastructure. Springer, Berlin Heidelberg

44.

Alotaibi B, Alotaibi M (2021) Consensus and majority vote feature selection methods and a detection technique for web phishing. J Ambient Intell Humaniz Comput 12(1):717–727. https://doi.org/10.1007/s12652-020-02054-3CrossRef

45.

Ulukaya S, Sandıkçı EN, Eroğlu Erdem Ç (2022) Consensus and stacking based fusion and survey of facial feature point detectors. J Ambient Intell Humaniz Comput. Doi: https://doi.org/10.1007/s12652-021-03662-3

46.

Li W, Duan P, Su J (2021) The effectiveness of project management construction with data mining and blockchain consensus. J Ambient Intell Humaniz Comput. Doi: https://doi.org/10.1007/s12652-020-02668-7

47.

Formato G, Troiano L, Vaccaro A (2014) Achieving consensus in self-organizing multi agent systems for smart microgrids computing in the presence of interval uncertainty. J Ambient Intell Humaniz Comput 5(6):821–828. https://doi.org/10.1007/s12652-014-0231-1CrossRef

48.

Pournaghi SM, Bayat M, Farjami Y (2020) MedSBA: a novel and secure scheme to share medical data based on blockchain technology and attribute-based encryption. J Ambient Intell Humaniz Comput 11(11):4613–4641. https://doi.org/10.1007/s12652-020-01710-yCrossRef

49.

Mayuranathan M, Murugan M, Dhanakoti V (2020) Enhanced security in cloud applications using emerging blockchain security algorithm J. Ambient Intell Humaniz Comput 12(7):6933–6945. https://doi.org/10.1007/s12652-020-02339-7CrossRef

50.

Rakkini MJJ, Geetha K (2021) Deep learning classification of bitcoin miners and exploration of upper confidence bound algorithm with less regret for the selection of honest mining. J Ambient Intell Humaniz Comput. Doi: https://doi.org/10.1007/s12652-021-03527-9

51.

Mubarakali A, Bose SC, Srinivasan K, Elsir A, Elsier O (2019) Design a secure and efficient health record transaction utilizing block chain (SEHRTB) algorithm for health record transaction in block chain. J Ambient Intell Humaniz Comput. Doi: https://doi.org/10.1007/s12652-019-01420-0

52.

Lee E, Yoon Y (2022) Trusted information project platform based on blockchain for sharing strategy. J Ambient Intell Humaniz Comput 13(3):1575–1585. https://doi.org/10.1007/s12652-019-01421-zCrossRef

53.

De Luca P, Fiscale S, Landolfi L, Di Mauro A (2019) Distributed genomic compression in MapReduce paradigm. Internet Distrib Comput Syst 11874 LNCS:369–378

54.

Martínez S (2010) Distributed interpolation schemes for field estimation by mobile sensor networks. IEEE Trans Control Syst Technol 18(2):491–500. https://doi.org/10.1109/TCST.2009.2017028CrossRef

55.

Palamuttam R et al. (2015) SciSpark: Applying in-memory distributed computing to weather event detection and tracking. Proc. 2015 IEEE Int Conf Big Data IEEE Big Data 2015, pp 2020–2026. Doi: https://doi.org/10.1109/BigData.2015.7363983

56.

Casavant TL, Kuhl JG (1988) A taxonomy of scheduling in general-purpose distributed computing systems. IEEE Trans Softw Eng 14(2):141–154. https://doi.org/10.1109/32.4634CrossRef

57.

Kelkar M, Zhang F, Steven G, Juels A (2020) Order-fairness for byzantine consensus. Adv Cryptol CRYPTO 2020 LNCS 12172:451–480CrossRefMATH

58.

Cachin C, Guerraoui R, Rodrigues L (2011) Introduction to reliable and secure distributed programming. Springer Sci Bus Media

59.

Hadzilacos V, Toueg S (1993) Reliable broadcast and related problems. Distrib Syst, pp 97–145

60.

Bracha G, Toueg S (1983) Asynchronous consensus and byzantine protocols in faulty environments. Tech Rep TR 559–83. [Online]. Available: http://ecommons.cornell.edu/handle/1813/6399

Title: A randomized algorithm for the wait-free consensus problem
Authors: Radha Rani
Dharmendra Prasad Mahato
Publication date: 07-09-2022
Publisher: Springer US
Published in: The Journal of Supercomputing / Issue 4/2023
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-022-04774-z

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 4/2023

Task offloading for edge computing in industrial Internet with joint data compression and security protection

HBI-LB: A Dependable Fault-Tolerant Load Balancing Approach for Fog based Internet-of-Things Environment

Predictive maintenance applied to mission critical supercomputing environments: remaining useful life estimation of a hydraulic cooling system using deep learning

Performance analysis of 5GMAKA: lightweight mutual authentication and key agreement scheme for 5G network

High-level power estimation techniques in embedded systems hardware: an overview

Quantifying DDS-cerberus network control overhead

Premium Partner