{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T20:55:36Z","timestamp":1740171336622,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T00:00:00Z","timestamp":1684108800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T00:00:00Z","timestamp":1684108800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Netw Distrib Comput"],"published-print":{"date-parts":[[2023,12]]},"abstract":"Abstract<\/jats:title>This paper tackles the asynchronous signature-free Byzantine consensus. One way to circumvent the FLP impossibility result consists in adding a Time-free assumption. This assumption is based on the pattern of messages that are exchanged. In the context of authenticated asynchronous Byzantine systems where at most t<\/jats:italic> processes may exhibit a Byzantine behavior, Moumen and Most\u00e9faoui provide the main result. They assume at least one correct process $$p_i$$<\/jats:tex-math>\n \n p<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, called $$\\diamond \\langle t+1\\rangle \\text {-winning}$$<\/jats:tex-math>\n \n \u22c4<\/mml:mo>\n \u27e8<\/mml:mo>\n t<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n \u27e9<\/mml:mo>\n -winning<\/mml:mtext>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and a set Q<\/jats:italic> of t<\/jats:italic> correct processes such that, eventually, for each query issued by $$p_i$$<\/jats:tex-math>\n \n p<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, any process $$p_j$$<\/jats:tex-math>\n \n p<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of Q<\/jats:italic> receives a response from $$p_i$$<\/jats:tex-math>\n \n p<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> among the $$(n-t)$$<\/jats:tex-math>\n \n (<\/mml:mo>\n n<\/mml:mi>\n -<\/mml:mo>\n t<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> first responses to that query. The main contribution of this paper is to show that a deterministic solution for the Signature-free Byzantine consensus problem is possible if the system model satisfies an additional assumption that relies on the pattern of exchanged messages. To solve the Consensus problem, we assume a correct process $$p_i$$<\/jats:tex-math>\n \n p<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, called $$\\diamond \\langle 2t+1\\rangle \\text {-winning}$$<\/jats:tex-math>\n \n \u22c4<\/mml:mo>\n \u27e8<\/mml:mo>\n 2<\/mml:mn>\n t<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n \u27e9<\/mml:mo>\n -winning<\/mml:mtext>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and a set Q<\/jats:italic> of $$(2t+1)$$<\/jats:tex-math>\n \n (<\/mml:mo>\n 2<\/mml:mn>\n t<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> correct processes (including $$p_i$$<\/jats:tex-math>\n \n p<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> itself) such that, eventually, for each query issued by $$p_i$$<\/jats:tex-math>\n \n p<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, any process $$p_j$$<\/jats:tex-math>\n \n p<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of Q<\/jats:italic> receives a response from $$p_i$$<\/jats:tex-math>\n \n p<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> among the $$(n - t)$$<\/jats:tex-math>\n \n (<\/mml:mo>\n n<\/mml:mi>\n -<\/mml:mo>\n t<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> first responses to that query. The processes of the set Q<\/jats:italic> may change over time. Based on this assumption, a Signature-free Multivalued Byzantine consensus protocol is proposed. Whereas many time-free protocols have been designed for the consensus problem in the crash model and in the Byzantine Authenticated model, this is, to our knowledge, the first time-free deterministic solution to the Signature-free Byzantine consensus Problem.<\/jats:p>","DOI":"10.1007\/s44227-023-00009-6","type":"journal-article","created":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T15:42:08Z","timestamp":1684165328000},"page":"49-59","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Time-Free Assumption for Solving Signature-Free Asynchronous Multivalued Byzantine Consensus"],"prefix":"10.1007","volume":"11","author":[{"given":"Abderafik","family":"Nezzar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1986-7590","authenticated-orcid":false,"given":"Hamouma","family":"Moumen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chafik","family":"Arar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,15]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"Aguilera MK, Chen W, Toueg S (1997) Heartbeat: a timeout-free failure detector for quiescent reliable communication. In: Proc workshop on distributed algorithms (WDAG\u201997), pp 126\u2013140","DOI":"10.1007\/BFb0030680"},{"key":"9_CR2","unstructured":"Aguilera MK, Delporte-Gallet C, Fauconnier H, Toueg S (2006) Consensus with Byzantine failures and little system synchrony. In: Proc international conference on dependable systems and networks (DSN\u201906), Philadelphia"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Ben-Or M (1983) Another advantage of free choice: completely asynchronous agreement protocols. In: Proc 2nd ACM symposium on principles of distributed computing (PODC\u201983). ACM Press, pp 27\u201330","DOI":"10.1145\/800221.806707"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Basu A, Charron-Bost B, Toueg T (1996) Crash failures vs. crash + link failures. In: Proc 15th ACM symposium on principles of distributed computing (PODC\u201996), Philadelphia, Pennsylvania","DOI":"10.1145\/248052.248102"},{"issue":"4","key":"9_CR5","doi-asserted-by":"publisher","DOI":"10.1145\/4221.214134","volume":"32","author":"G Bracha","year":"1985","unstructured":"Bracha G, Toueg S (1985) Asynchronous consensus and broadcast protocols. J ACM 32(4):824840","journal-title":"J ACM"},{"issue":"2","key":"9_CR6","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1145\/226643.226647","volume":"43","author":"TD Chandra","year":"1996","unstructured":"Chandra TD, Toueg S (1996) Unreliable failure detectors for reliable distributed systems. J ACM 43(2):225\u2013267","journal-title":"J ACM"},{"issue":"2","key":"9_CR7","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1145\/42282.42283","volume":"35","author":"C Dwork","year":"1988","unstructured":"Dwork C, Lynch NA, Stockmeyer L (1988) Consensus in the presence of partial synchrony. J ACM 35(2):288\u2013323","journal-title":"J ACM"},{"issue":"2","key":"9_CR8","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1145\/3149.214121","volume":"32","author":"MJ Fischer","year":"1985","unstructured":"Fischer MJ, Lynch N, Paterson MS (1985) Impossibility of distributed consensus with one faulty process. J ACM 32(2):374\u2013382","journal-title":"J ACM"},{"key":"9_CR9","unstructured":"Hutle M, Malkhi D, Schmid U, Zhou L (2006) Chasing the weakest system model for implementing. Research Report 74\/2005, Technische Universit\u00e4t Wien, Institut f\u00fcr Technische Informatik, July"},{"issue":"3","key":"9_CR10","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/357172.357176","volume":"4","author":"L Lamport","year":"1982","unstructured":"Lamport L, Shostack R, Pease M (1982) The Byzantine generals problem. ACM Trans Program Lang Syst 4(3):382\u2013401","journal-title":"ACM Trans Program Lang Syst"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Moumen H, Mostefaoui A (2010) Time-free authenticated byzantine consensus. In: Proc on the ninth IEEE international symposium on network computing and applications, Cambridge, pp 140\u2013146","DOI":"10.1109\/NCA.2010.25"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Most\u00e9faoui A, Moumen H, Raynal M (2015) Signature-free asynchronous binary Byzantine consensus with t n\/3, O(n2) messages, and O(1) expected time. J ACM 62(4), Article 31, 21 pp","DOI":"10.1145\/2785953"},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"Mostefaoui A, Mourgaya E, Raynal M (2003) Asynchronous implementation of failure detectors. In: Proc. Int\u2019l IEEE conf dependable systems and networks (DSN \u201903), pp 351\u2013360","DOI":"10.1109\/DSN.2003.1209946"},{"issue":"2","key":"9_CR14","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1142\/S0129626406002575","volume":"16","author":"A Mostefaoui","year":"2006","unstructured":"Mostefaoui A, Mourgaya E, Raynal M, Travers C (2006) A time-free assumption to implement eventual leadership. Parallel Process Lett 16(2):189\u2013208","journal-title":"Parallel Process Lett"},{"key":"9_CR15","unstructured":"Moumen H, Mostefaoui A, Tredan G (2007) Byzantine consensus with few synchronous links. In: Proc of the int conference on principles of distributed systems (OPODIS), pp 76\u201389"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"Mostefaoui A, Powell D, Raynal M (2004) A hybrid approach for building eventually accurate failure detectors. PRDC 57\u201365","DOI":"10.1109\/PRDC.2004.1276553"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"Mostefaoui A, Raynal M, Travers C (2006) Time-free and timer-based assumptions can be combined to obtain eventual leadership. In: IEEE transactions on parallel and distributed systems, vol 17, no 7, pp 656\u2013666","DOI":"10.1109\/TPDS.2006.95"},{"key":"9_CR18","unstructured":"Nakamoto S (2008) Bitcoin: a peer-to-peer electronic cash system. [Online]. https:\/\/bitcoin.org\/bitcoin.pdf"},{"key":"9_CR20","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1145\/322186.322188","volume":"27","author":"M Pease","year":"1980","unstructured":"Pease M, Shostak R, Lamport L (1980) Reaching agreement in the presence of faults. J ACM 27:228\u2013234","journal-title":"J ACM"},{"key":"9_CR21","doi-asserted-by":"crossref","unstructured":"Rabin M (1983) Randomized byzantine generals. In: Proc 24th IEEE symposium on foundations of computer science (FOCS\u201983), pp 403\u2013409","DOI":"10.1109\/SFCS.1983.48"},{"issue":"1","key":"9_CR19","doi-asserted-by":"publisher","first-page":"73","DOI":"10.3233\/FI-2020-1916","volume":"173","author":"A Tioura","year":"2020","unstructured":"Tioura A, Moumen H, Kalla H, Ait Saidi A (2020) A hybrid protocol to solve authenticated byzantine consensus. Fundamentae Informaticae 173(1):73\u201389","journal-title":"Fundamentae Informaticae"},{"issue":"1","key":"9_CR22","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/s00446-009-0080-x","volume":"22","author":"J Widder","year":"2009","unstructured":"Widder J, Schmid U (2009) The theta-model: achieving synchrony without clocks. Distrib Comput 22(1):29\u201347","journal-title":"Distrib Comput"}],"container-title":["International Journal of Networked and Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s44227-023-00009-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s44227-023-00009-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s44227-023-00009-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,23]],"date-time":"2023-11-23T09:45:27Z","timestamp":1700732727000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s44227-023-00009-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,15]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["9"],"URL":"https:\/\/doi.org\/10.1007\/s44227-023-00009-6","relation":{},"ISSN":["2211-7938","2211-7946"],"issn-type":[{"type":"print","value":"2211-7938"},{"type":"electronic","value":"2211-7946"}],"subject":[],"published":{"date-parts":[[2023,5,15]]},"assertion":[{"value":"2 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 May 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}