Skip to main content
Top

2019 | OriginalPaper | Chapter

Self-stabilization Overhead: A Case Study on Coded Atomic Storage

Authors : Chryssis Georgiou, Robert Gustafsson, Andreas Lindhé, Elad Michael Schiller

Published in: Networked Systems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Shared memory emulation on distributed message-passing systems can be used as a fault-tolerant and highly available distributed storage solution or as a low-level synchronization primitive. Cadambe et al. proposed the Coded Atomic Storage (CAS) algorithm, which uses erasure coding to achieve data redundancy with much lower communication cost than previous algorithmic solutions. Recently, Dolev et al. introduced a version of CAS where transient faults are included in the fault model, making it self-stabilizing. But self-stabilization comes at a cost, so in this work we examine the overhead of the algorithm by implementing a system we call CASSS (CAS Self-Stabilizing). Our system builds on the self-stabilizing version of CAS, along with several other self-stabilizing building blocks. This provides us with a powerful platform to evaluate the overhead and other aspects of the real-world applicability of the algorithm.
In our case-study, we evaluated the system performance by running it on the world-wide distributed platform PlanetLab. Our study shows that CASSS scales very well in terms of the number of servers, the number of concurrent clients, as well as the size of the replicated object. More importantly, it shows (a) to have only a constant overhead compared to the traditional CAS algorithm and (b) the recovery period (after the last occurrence of a transient fault) is no more than the time it takes to perform a few client (read/write) operations. Our results suggest that the self-stabilizing variation of CAS, which is CASSS, does not significantly impact efficiency while dealing with automatic recovery from transient faults.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Herlihy, M.P., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463–492 (1990)CrossRef Herlihy, M.P., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463–492 (1990)CrossRef
2.
go back to reference Attiya, H., Bar-Noy, A., Dolev, D.: Sharing memory robustly in message-passing systems. J. ACM 42(1), 124–142 (1995)CrossRef Attiya, H., Bar-Noy, A., Dolev, D.: Sharing memory robustly in message-passing systems. J. ACM 42(1), 124–142 (1995)CrossRef
4.
go back to reference Cadambe, V.R., Lynch, N., Medard, M., Musial, P.: A coded shared atomic memory algorithm for message passing architectures. Distrib. Comput. 30(1), 49–73 (2017)MathSciNetCrossRef Cadambe, V.R., Lynch, N., Medard, M., Musial, P.: A coded shared atomic memory algorithm for message passing architectures. Distrib. Comput. 30(1), 49–73 (2017)MathSciNetCrossRef
5.
go back to reference Dolev, S., Petig, T., Schiller, E.M.: Self-stabilizing and private distributed shared atomic memory in seldomly fair message passing networks. CoRR abs/1806.03498 (2018) Dolev, S., Petig, T., Schiller, E.M.: Self-stabilizing and private distributed shared atomic memory in seldomly fair message passing networks. CoRR abs/1806.03498 (2018)
6.
go back to reference Dolev, S., Petig, T., Schiller, E.M.: Brief announcement: robust and private distributed shared atomic memory in message passing networks. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 311–313. ACM (2015) Dolev, S., Petig, T., Schiller, E.M.: Brief announcement: robust and private distributed shared atomic memory in message passing networks. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 311–313. ACM (2015)
7.
go back to reference Dolev, S., Georgiou, C., Marcoullis, I., Schiller, E.M.: Self-stabilizing reconfiguration. In: Networked Systems NETYS, pp. 51–68 (2017)CrossRef Dolev, S., Georgiou, C., Marcoullis, I., Schiller, E.M.: Self-stabilizing reconfiguration. In: Networked Systems NETYS, pp. 51–68 (2017)CrossRef
8.
go back to reference Dijkstra, E.W.: Self-stabilizing systems in spite of distributed control. Commun. ACM 17(11), 643–644 (1974)CrossRef Dijkstra, E.W.: Self-stabilizing systems in spite of distributed control. Commun. ACM 17(11), 643–644 (1974)CrossRef
9.
11.
go back to reference Musial, P.M., Nicolaou, N.C., Shvartsman, A.A.: Implementing distributed shared memory for dynamic networks. Commun. ACM 57(6), 88–98 (2014)CrossRef Musial, P.M., Nicolaou, N.C., Shvartsman, A.A.: Implementing distributed shared memory for dynamic networks. Commun. ACM 57(6), 88–98 (2014)CrossRef
12.
go back to reference Cadambe, V.R., Nicolaou, N.C., Konwar, K.M., Prakash, N., Lynch, N.A., Médard, M.: ARES: adaptive, reconfigurable, erasure coded, atomic storage. CoRR abs/1805.03727 (2018) Cadambe, V.R., Nicolaou, N.C., Konwar, K.M., Prakash, N., Lynch, N.A., Médard, M.: ARES: adaptive, reconfigurable, erasure coded, atomic storage. CoRR abs/1805.03727 (2018)
13.
go back to reference Nicolaou, N.C., Georgiou, C.: On the practicality of atomic MWMR register implementations. In: 10th IEEE Parallel and Distributed Processing with Applications, ISPA, pp. 340–347 (2012) Nicolaou, N.C., Georgiou, C.: On the practicality of atomic MWMR register implementations. In: 10th IEEE Parallel and Distributed Processing with Applications, ISPA, pp. 340–347 (2012)
15.
go back to reference Lynch, N.A., Shvartsman, A.A.: Robust emulation of shared memory using dynamic quorum-acknowledged broadcasts. In: 27th Fault-Tolerant Computing, pp. 272–281 (1997) Lynch, N.A., Shvartsman, A.A.: Robust emulation of shared memory using dynamic quorum-acknowledged broadcasts. In: 27th Fault-Tolerant Computing, pp. 272–281 (1997)
18.
go back to reference Canini, M., Salem, I., Schiff, L., Schiller, E.M., Schmid, S.: A self-organizing distributed and in-band SDN control plane. In: ICDCS, IEEE Computer Society, pp. 2656–2657 (2017) Canini, M., Salem, I., Schiff, L., Schiller, E.M., Schmid, S.: A self-organizing distributed and in-band SDN control plane. In: ICDCS, IEEE Computer Society, pp. 2656–2657 (2017)
19.
go back to reference Canini, M., Salem, I., Schiff, L., Schiller, E.M., Schmid, S.: Renaissance: a self-stabilizing distributed SDN control plane. In: ICDCS, IEEE Computer Society, pp. 233–243 (2018) Canini, M., Salem, I., Schiff, L., Schiller, E.M., Schmid, S.: Renaissance: a self-stabilizing distributed SDN control plane. In: ICDCS, IEEE Computer Society, pp. 233–243 (2018)
22.
Metadata
Title
Self-stabilization Overhead: A Case Study on Coded Atomic Storage
Authors
Chryssis Georgiou
Robert Gustafsson
Andreas Lindhé
Elad Michael Schiller
Copyright Year
2019
DOI
https://doi.org/10.1007/978-3-030-31277-0_9

Premium Partner