Distributed computability in Byzantine asynchronous systems
From MaRDI portal
Publication:5259606
DOI10.1145/2591796.2591853zbMATH Open1315.68020arXiv1302.6224OpenAlexW2016408245MaRDI QIDQ5259606FDOQ5259606
Authors: Hammurabi Mendes, Christine Tasson, Maurice Herlihy 
Publication date: 26 June 2015
Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1302.6224
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
Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed systems (68M14)
Cites Work
- Theory of Cryptography
- The geometry of differential privacy: the sparse and approximate cases
- On the geometry of differential privacy
- Interactive privacy via the median mechanism
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Lower bounds in differential privacy
- Iterative Constructions and Private Data Release
- Differential privacy and the fat-shattering dimension of linear queries
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- On the complexity of differentially private data release, efficient algorithms and hardness results
- Title not available (Why is that?)
- Collusion-secure fingerprinting for digital data
- Advances in Cryptology – CRYPTO 2004
- Title not available (Why is that?)
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- Bounds on the sample complexity for private learning and private data release
- Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
- Characterizing the sample complexity of private learners
- Faster algorithms for privately releasing marginals
- Faster private release of marginals on small databases
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- Privately releasing conjunctions and the statistical query barrier
- Efficient algorithms for privately releasing marginals via convex relaxations
Cited In (21)
- A topological perspective on distributed network algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- Distributed computing in asynchronous networks with byzantine edges
- Asynchronous computability theorems for \(t\)-resilient systems
- Wait-free solvability of colorless tasks in anonymous shared-memory model
- Initial failures in distributed computations
- An asynchronous computability theorem for fair adversaries
- Invited paper: Cross-chain state machine replication
- Algebraic topology and distributed computing
- Wait-free approximate agreement on graphs
- Wait-free approximate agreement on graphs
- On the Validity of Consensus
- From wait-free to arbitrary concurrent solo executions in colorless distributed computing
- Distributed Computing
- The topology of randomized symmetry-breaking distributed computing
- Two distributed problems involving Byzantine processes
- Toward computability of trace distance discord
- Observing Distributed Computation. A Dynamic-Epistemic Approach
- A Sufficient Condition for Gaining Belief in Byzantine Fault-Tolerant Distributed Systems
- A characterization of \(t\)-resilient colorless task anonymous solvability
Uses Software
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)
