{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T00:34:41Z","timestamp":1759970081543,"version":"build-2065373602"},"reference-count":22,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T00:00:00Z","timestamp":1736035200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This paper considers the solvability of several fundamental problems in asynchronous message-passing distributed systems in the presence of Byzantine processes using distributed algorithms. These problems are the following: mutual exclusion, global snapshot recording, termination detection, deadlock detection, predicate detection, causal ordering, spanning tree construction, minimum spanning tree construction, all\u2013all shortest paths computation, and maximal independent set computation. In a distributed algorithm, each process has access only to its local variables and incident edge parameters. We show the impossibility of solving these fundamental problems by proving that they require a solution to the causality determination problem which has been shown to be unsolvable in asynchronous message-passing distributed systems.<\/jats:p>","DOI":"10.3390\/a18010026","type":"journal-article","created":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T06:43:04Z","timestamp":1736145784000},"page":"26","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Impossibility Results for Byzantine-Tolerant State Observation, Synchronization, and Graph Computation Problems"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2451-7306","authenticated-orcid":false,"given":"Ajay","family":"Kshemkalyani","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Illinois Chicago, Chicago, IL 60607, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3987-7945","authenticated-orcid":false,"given":"Anshuman","family":"Misra","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Purdue University Fort Wayne, Fort Wayne, IN 46805, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,1,5]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/BF02277859","article-title":"Detecting Causal Relationships in Distributed Computations: In Search of the Holy Grail","volume":"7","author":"Schwarz","year":"1994","journal-title":"Distrib. Comput."},{"key":"ref_2","unstructured":"Mattern, F. (, January October). Virtual Time and Global States of Distributed Systems. Proceedings of the Parallel and Distributed Algorithms, North-Holland, The Netherlands."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1109\/2.84874","article-title":"Logical Time in Distributed Computing Systems","volume":"24","author":"Fidge","year":"1991","journal-title":"IEEE Comput."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Misra, A., and Kshemkalyani, A.D. (2022, January 14\u201316). Detecting Causality in the Presence of Byzantine Processes: There is No Holy Grail. Proceedings of the 21st IEEE International Symposium on Network Computing and Applications (NCA), Boston, MA, USA.","DOI":"10.1109\/NCA57778.2022.10013644"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1145\/359545.359563","article-title":"Time, clocks, and the ordering of events in a distributed system","volume":"21","author":"Lamport","year":"1978","journal-title":"Commun. ACM"},{"key":"ref_6","unstructured":"Kshemkalyani, A.D., and Singhal, M. (2011). Distributed Computing: Principles, Algorithms, and Systems, Cambridge University Press."},{"key":"ref_7","unstructured":"Garg, V.K. (2002). Elements of Distributed Computing, Wiley."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Raynal, M. (2013). Distributed Algorithms for Message-Passing Systems, Springer.","DOI":"10.1007\/978-3-642-38123-2"},{"key":"ref_9","unstructured":"Tanenbaum, A.S., and van Steen, M. (2007). Distributed Systems\u2014Principles and Paradigms, Pearson Education. [2nd ed.]."},{"key":"ref_10","unstructured":"Coulouris, G., Dollimore, J., and Kindberg, T. (2002). Distributed Systems\u2014Concepts and Designs, Addison-Wesley-Longman. [3rd ed.]."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1145\/3149.214121","article-title":"Impossibility of distributed consensus with one faulty process","volume":"32","author":"Fischer","year":"1985","journal-title":"J. ACM (JACM)"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Lynch, N. (1989). A Hundred Impossibility Results for Distributed Computing. MIT Technical Report MIT\/LCS\/TM\/394, Laboratory for Computer Science, Massachusetts Institute of Technology.","DOI":"10.1145\/72981.72982"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Lynch, N.A. (1989, January 14\u201316). A Hundred Impossibility Proofs for Distributed Computing. Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, Edmonton, AB, Canada.","DOI":"10.1145\/72981.72982"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Attiya, H., and Ellen, F. (2014). Impossibility Results for Distributed Computing, Morgan & Claypool Publishers. Synthesis Lectures on Distributed Computing Theory.","DOI":"10.1007\/978-3-031-02010-0"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/s00446-003-0091-y","article-title":"Hundreds of impossibility results for distributed computing","volume":"16","author":"Fich","year":"2003","journal-title":"Distrib. Comput."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1007\/BF01843569","article-title":"How Processes Learn","volume":"1","author":"Chandy","year":"1986","journal-title":"Distrib. Comput."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1145\/357172.357176","article-title":"The Byzantine Generals Problem","volume":"4","author":"Lamport","year":"1982","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1145\/42282.42283","article-title":"Consensus in the presence of partial synchrony","volume":"35","author":"Dwork","year":"1988","journal-title":"J. ACM"},{"key":"ref_19","first-page":"87","article-title":"Solvability of Byzantine Fault-Tolerant Causal Ordering Problems","volume":"Volume 13464","author":"Misra","year":"2022","journal-title":"Proceedings of the Networked Systems\u201410th International Conference, NETYS 2022"},{"key":"ref_20","unstructured":"Misra, A., and Kshemkalyani, A.D. (2022, January 10\u201312). Causal Ordering in the Presence of Byzantine Processes. Proceedings of the 28th IEEE International Conference on Parallel and Distributed Systems ICPADS, Nanjing, China."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Misra, A., and Kshemkalyani, A.D. (2023, January 4\u20137). Byzantine Fault-Tolerant Causal Ordering. Proceedings of the 24th International Conference on Distributed Computing and Networking, ICDCN 2023, Kharagpur, India.","DOI":"10.1145\/3571306.3571395"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"814","DOI":"10.1109\/TPDS.2024.3368280","article-title":"Byzantine-Tolerant Causal Ordering for Unicasts, Multicasts, and Broadcasts","volume":"35","author":"Misra","year":"2024","journal-title":"IEEE Trans. Parallel Distrib. Syst."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/1\/26\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T10:23:11Z","timestamp":1759918991000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/1\/26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,5]]},"references-count":22,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,1]]}},"alternative-id":["a18010026"],"URL":"https:\/\/doi.org\/10.3390\/a18010026","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2025,1,5]]}}}