Distributed computability in Byzantine asynchronous systems
From MaRDI portal
Publication:5259606
Abstract: In this work, we extend the topology-based approach for characterizing computability in asynchronous crash-failure distributed systems to asynchronous Byzantine systems. We give the first theorem with necessary and sufficient conditions to solve arbitrary tasks in asynchronous Byzantine systems where an adversary chooses faulty processes. In our adversarial formulation, outputs of non-faulty processes are constrained in terms of inputs of non-faulty processes only. For colorless tasks, an important subclass of distributed problems, the general result reduces to an elegant model that effectively captures the relation between the number of processes, the number of failures, as well as the topological structure of the task's simplicial complexes.
Recommendations
- An asynchronous computability theorem for fair adversaries
- A generalized asynchronous computability theorem
- Asynchronous computability theorems for \(t\)-resilient systems
- The topological structure of asynchronous computability
- A characterization of \(t\)-resilient colorless task anonymous solvability
Cites work
- scientific article; zbMATH DE number 5485440 (Why is no real title available?)
- scientific article; zbMATH DE number 5485574 (Why is no real title available?)
- Advances in Cryptology – CRYPTO 2004
- Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
- Bounds on the sample complexity for private learning and private data release
- Characterizing the sample complexity of private learners
- Collusion-secure fingerprinting for digital data
- Differential privacy and the fat-shattering dimension of linear queries
- Efficient algorithms for privately releasing marginals via convex relaxations
- Faster algorithms for privately releasing marginals
- Faster private release of marginals on small databases
- Interactive privacy via the median mechanism
- Iterative Constructions and Private Data Release
- Lower bounds in differential privacy
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- On the complexity of differentially private data release, efficient algorithms and hardness results
- On the geometry of differential privacy
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Theory of Cryptography
Cited in
(21)- Algebraic topology and distributed computing
- Observing Distributed Computation. A Dynamic-Epistemic Approach
- A topological perspective on distributed network algorithms
- On the Validity of Consensus
- The topology of randomized symmetry-breaking distributed computing
- scientific article; zbMATH DE number 7724201 (Why is no real title available?)
- Wait-free solvability of colorless tasks in anonymous shared-memory model
- Two distributed problems involving Byzantine processes
- Invited paper: Cross-chain state machine replication
- Distributed computing in asynchronous networks with byzantine edges
- A characterization of \(t\)-resilient colorless task anonymous solvability
- From wait-free to arbitrary concurrent solo executions in colorless distributed computing
- Initial failures in distributed computations
- An asynchronous computability theorem for fair adversaries
- Asynchronous computability theorems for \(t\)-resilient systems
- Distributed Computing
- A Sufficient Condition for Gaining Belief in Byzantine Fault-Tolerant Distributed Systems
- Wait-free approximate agreement on graphs
- Toward computability of trace distance discord
- scientific article; zbMATH DE number 1696685 (Why is no real title available?)
- Wait-free approximate agreement on graphs
This page was built for publication: Distributed computability in Byzantine asynchronous systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259606)
