×

zbMATH — the first resource for mathematics

Atomic read/write memory in signature-free Byzantine asynchronous message-passing systems. (English) Zbl 1371.68040
Summary: This article presents a signature-free distributed algorithm which builds an atomic read/write shared memory on top of a fully connected peer-to-peer \(n\)-process asynchronous message-passing system in which up to \(t<n/3\) processes may commit Byzantine failures. From a conceptual point of view, this algorithm is designed to be as close as possible to the algorithm proposed by H. Attiya et al. [J. Assoc. Comput. Mach. 42, No. 1, 124–142 (1995; Zbl 0886.68018)], which builds an atomic register in an \(n\)-process asynchronous message-passing system where up to \(t<n/2\) processes may crash. The proposed algorithm is particularly simple. It does not use cryptography to cope with Byzantine processes, and is optimal from a \(t\)-resilience point of view \((t<n/3)\). A read operation requires \(O(n)\) messages, and a write operation requires \(O(n^{2})\) messages.
MSC:
68M14 Distributed systems
68W15 Distributed algorithms
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aiyer, A.S., Alvisi, L., Bazzi, R.A.: Bounded wait-free implementation of optimally resilient Byzantine storage without (unproven) cryptographic assumptions. In: Proceedings 21st Int?l Symposium on Distributed Computing (DISC?07), pp 7-19. Springer LNCS 4731 (2007) · Zbl 1145.68340
[2] Attiya, H, Efficient and robust sharing of memory in message-passing systems, J. Algorithm., 34, 109-127, (2000) · Zbl 0958.68014
[3] Attiya, H; Bar-Noy, A; Dolev, D, Sharing memory robustly in message passing systems, J. ACM, 42, 121-132, (1995) · Zbl 0886.68018
[4] Attiya, H; Bar-Or, A, Sharing memory with semi-Byzantine clients and faulty storage servers, Parallel Process. Lett., 16, 419-428, (2006)
[5] Attiya, H., Welch, J.L.: Distributed computing: fundamentals, simulations and advanced topics, 2nd edn., p 414. Wiley-Interscience (2004). (ISBN 0-471-45324-2) · Zbl 0910.68077
[6] Bracha, G, Asynchronous Byzantine agreement protocols, Inf. Comput., 75, 130-143, (1987) · Zbl 0622.68032
[7] Chaudhuri, S; Kosa, MJ; Welch, JL, One-write algorithms for multivalued regular and atomic registers, Acta Inf., 37, 161-192, (2000) · Zbl 0962.68175
[8] Chockler, G; Malkhi, D, Active disk paxos with infinitely many processes, Distrib. Comput., 18, 73-84, (2005) · Zbl 1264.68074
[9] Dobre, D., Guerraoui, R., Majuntke, M., Suri, N., Vukolic, M.: The complexity of robust atomic storage. In: Proceedings 30th ACM Symposium on Principles of Distributed Computing (PODC?11), pp 59-68. ACM Press (2011) · Zbl 1321.68306
[10] Guerraoui, R., Vukolic, M.: How fast can a very robust read be?. In: Proceedings 25th ACM Symposium on Principles of Distributed Computing (PODC’06), pp 248-257. ACM Press (2006) · Zbl 1314.68157
[11] Herlihy, MP; Wing, J, Linearizability: a correctness condition for concurrent objects, ACM Trans. Programm. Lang. Syst., 12, 463-492, (1990)
[12] Imbs, D; Rajsbaum, S; Raynal, M; Stainer, J, Read/write shared memory abstraction on top of asynchronous Byzantine message-passing systems, J. Parallel Distrib. Comput., 93-94, 1-9, (2016) · Zbl 1416.68024
[13] Ittai, A; Chockler, G; Keidar, I; Malkhi, D, Byzantine disk paxos: optimal resilience with Byzantine shared memory, Distrib. Comput., 18, 387-408, (2006) · Zbl 1266.68203
[14] Lamport, L, On interprocess communication, part I: basic formalism, Distrib. Comput., 1, 77-85, (1986) · Zbl 0598.68022
[15] Lamport, L, On interprocess communication, part II: algorithms, Distrib. Comput., 1, 77-101, (1986) · Zbl 0598.68022
[16] Lamport, L; Shostack, R; Pease, M, The Byzantine generals problem, ACM Trans. Programm. Lang. Syst., 4, 382-401, (1982) · Zbl 0483.68021
[17] Malkhi, D., Reiter, M.: Secure and scalable replication in Phalanx. In: Proceedings 17th IEEE Symposium on Reliable Distributed Systems (SRDS’98), pp 51-58. IEEE Press (1998) · Zbl 0434.68031
[18] Martin, J.-P.H., Alvisi, L.: A framework for dynamic Byzantine storage. In: Proceedings International Conference on Dependable Systems and Networks (DSN’04), pp 325-334. IEEE Press (2004)
[19] Misra, J, Axioms for memory access in asynchronous hardware systems, ACM Trans. Programm. Lang. Syst., 8, 142-153, (1986) · Zbl 0593.68017
[20] Mostéfaoui, A; Raynal, M, Intrusion-tolerant broadcast and agreement abstractions in the presence of Byzantine processes, IEEE Trans. Parallel Distrib. Syst., 27, 1085-1097, (2016)
[21] Pease, M; Shostak, RR; Lamport, L, Reaching agreement in the presence of faults, J. ACM, 27, 228-234, (1980) · Zbl 0434.68031
[22] Raynal, M.: Communication and agreement abstractions for fault-tolerant asynchronous distributed systems, p 251. Morgan & Claypool Publishers (2010). (ISBN 978-1-60845-293-4)
[23] Raynal, M.: Concurrent programming: algorithms, principles and foundations, p 515. Springer (2013). (ISBN 978-3-642-32026-2) · Zbl 1276.68001
[24] Raynal, M.: Distributed algorithms for message-passing systems, p 510. Springer (2013). (ISBN: 978-3-642-38122-5) · Zbl 1282.68004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.