Impossibility Results for Byzantine-Tolerant State Observation, Synchronization, and Graph Computation Problems
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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-01-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/18/1/26 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832589382805094400 |
|---|---|
| author | Ajay D. Kshemkalyani Anshuman Misra |
| author_facet | Ajay D. Kshemkalyani Anshuman Misra |
| author_sort | Ajay D. Kshemkalyani |
| collection | DOAJ |
| description | 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–all 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. |
| format | Article |
| id | doaj-art-203212ea3a4847ca856b21afee3f139a |
| institution | Kabale University |
| issn | 1999-4893 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj-art-203212ea3a4847ca856b21afee3f139a2025-01-24T13:17:31ZengMDPI AGAlgorithms1999-48932025-01-011812610.3390/a18010026Impossibility Results for Byzantine-Tolerant State Observation, Synchronization, and Graph Computation ProblemsAjay D. Kshemkalyani0Anshuman Misra1Department of Computer Science, University of Illinois Chicago, Chicago, IL 60607, USADepartment of Computer Science, Purdue University Fort Wayne, Fort Wayne, IN 46805, USAThis 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–all 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.https://www.mdpi.com/1999-4893/18/1/26Byzantine fault-tolerance“happened before” relationcausalitystate observationsynchronizationgraph computation |
| spellingShingle | Ajay D. Kshemkalyani Anshuman Misra Impossibility Results for Byzantine-Tolerant State Observation, Synchronization, and Graph Computation Problems Algorithms Byzantine fault-tolerance “happened before” relation causality state observation synchronization graph computation |
| title | Impossibility Results for Byzantine-Tolerant State Observation, Synchronization, and Graph Computation Problems |
| title_full | Impossibility Results for Byzantine-Tolerant State Observation, Synchronization, and Graph Computation Problems |
| title_fullStr | Impossibility Results for Byzantine-Tolerant State Observation, Synchronization, and Graph Computation Problems |
| title_full_unstemmed | Impossibility Results for Byzantine-Tolerant State Observation, Synchronization, and Graph Computation Problems |
| title_short | Impossibility Results for Byzantine-Tolerant State Observation, Synchronization, and Graph Computation Problems |
| title_sort | impossibility results for byzantine tolerant state observation synchronization and graph computation problems |
| topic | Byzantine fault-tolerance “happened before” relation causality state observation synchronization graph computation |
| url | https://www.mdpi.com/1999-4893/18/1/26 |
| work_keys_str_mv | AT ajaydkshemkalyani impossibilityresultsforbyzantinetolerantstateobservationsynchronizationandgraphcomputationproblems AT anshumanmisra impossibilityresultsforbyzantinetolerantstateobservationsynchronizationandgraphcomputationproblems |