Home > Research > Publications & Outputs > On the time-complexity of robust and amnesic st...

Research

Associated organisational units

Links

Text available via DOI:

Keywords

View graph of relations

On the time-complexity of robust and amnesic storage

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter

Published

Standard

On the time-complexity of robust and amnesic storage. / Dobre, D.; Majuntke, M.; Suri, Neeraj.
Principles of Distributed Systems: 12th International Conference, OPODIS 2008, Luxor, Egypt, December 15-18, 2008. Proceedings. Vol. 5401 LNCS Springer, 2008. p. 197-216.

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter

Harvard

Dobre, D, Majuntke, M & Suri, N 2008, On the time-complexity of robust and amnesic storage. in Principles of Distributed Systems: 12th International Conference, OPODIS 2008, Luxor, Egypt, December 15-18, 2008. Proceedings. vol. 5401 LNCS, Springer, pp. 197-216. https://doi.org/10.1007/978-3-540-92221-6_14

APA

Dobre, D., Majuntke, M., & Suri, N. (2008). On the time-complexity of robust and amnesic storage. In Principles of Distributed Systems: 12th International Conference, OPODIS 2008, Luxor, Egypt, December 15-18, 2008. Proceedings (Vol. 5401 LNCS, pp. 197-216). Springer. https://doi.org/10.1007/978-3-540-92221-6_14

Vancouver

Dobre D, Majuntke M, Suri N. On the time-complexity of robust and amnesic storage. In Principles of Distributed Systems: 12th International Conference, OPODIS 2008, Luxor, Egypt, December 15-18, 2008. Proceedings. Vol. 5401 LNCS. Springer. 2008. p. 197-216 doi: 10.1007/978-3-540-92221-6_14

Author

Dobre, D. ; Majuntke, M. ; Suri, Neeraj. / On the time-complexity of robust and amnesic storage. Principles of Distributed Systems: 12th International Conference, OPODIS 2008, Luxor, Egypt, December 15-18, 2008. Proceedings. Vol. 5401 LNCS Springer, 2008. pp. 197-216

Bibtex

@inbook{0408fdaca5194f1098e7264c2d8b234d,
title = "On the time-complexity of robust and amnesic storage",
abstract = "We consider wait-free implementations of a regular read/ write register for unauthenticated data using a collection of 3t∈+∈k base objects, t of which can be subject to Byzantine failures. We focus on amnesic algorithms that store only a limited number of values in the base objects. In contrast, non-amnesic algorithms store an unbounded number of values, which can eventually lead to problems of space exhaustion. Lower bounds on the time-complexity of read and write operations are currently met only by non-amnesic algorithms. In this paper, we show for the first time that amnesic algorithms can also meet these lower bounds. We do this by giving two amnesic constructions: for k∈=∈1, we show that the lower bound of two communication rounds is also sufficient for every read operation to complete and for k∈=∈t∈+∈1 we show that the lower bound of one round is also sufficient for every operation to complete. {\textcopyright} 2008 Springer Berlin Heidelberg.",
keywords = "Byzantine failures, Distributed storage, Wait-free algorithms, Control theory, Communication rounds, Lower bounds, Read operations, Write operations, Algorithms",
author = "D. Dobre and M. Majuntke and Neeraj Suri",
year = "2008",
doi = "10.1007/978-3-540-92221-6_14",
language = "English",
isbn = " 9783540922209",
volume = "5401 LNCS",
pages = "197--216",
booktitle = "Principles of Distributed Systems",
publisher = "Springer",

}

RIS

TY - CHAP

T1 - On the time-complexity of robust and amnesic storage

AU - Dobre, D.

AU - Majuntke, M.

AU - Suri, Neeraj

PY - 2008

Y1 - 2008

N2 - We consider wait-free implementations of a regular read/ write register for unauthenticated data using a collection of 3t∈+∈k base objects, t of which can be subject to Byzantine failures. We focus on amnesic algorithms that store only a limited number of values in the base objects. In contrast, non-amnesic algorithms store an unbounded number of values, which can eventually lead to problems of space exhaustion. Lower bounds on the time-complexity of read and write operations are currently met only by non-amnesic algorithms. In this paper, we show for the first time that amnesic algorithms can also meet these lower bounds. We do this by giving two amnesic constructions: for k∈=∈1, we show that the lower bound of two communication rounds is also sufficient for every read operation to complete and for k∈=∈t∈+∈1 we show that the lower bound of one round is also sufficient for every operation to complete. © 2008 Springer Berlin Heidelberg.

AB - We consider wait-free implementations of a regular read/ write register for unauthenticated data using a collection of 3t∈+∈k base objects, t of which can be subject to Byzantine failures. We focus on amnesic algorithms that store only a limited number of values in the base objects. In contrast, non-amnesic algorithms store an unbounded number of values, which can eventually lead to problems of space exhaustion. Lower bounds on the time-complexity of read and write operations are currently met only by non-amnesic algorithms. In this paper, we show for the first time that amnesic algorithms can also meet these lower bounds. We do this by giving two amnesic constructions: for k∈=∈1, we show that the lower bound of two communication rounds is also sufficient for every read operation to complete and for k∈=∈t∈+∈1 we show that the lower bound of one round is also sufficient for every operation to complete. © 2008 Springer Berlin Heidelberg.

KW - Byzantine failures

KW - Distributed storage

KW - Wait-free algorithms

KW - Control theory

KW - Communication rounds

KW - Lower bounds

KW - Read operations

KW - Write operations

KW - Algorithms

U2 - 10.1007/978-3-540-92221-6_14

DO - 10.1007/978-3-540-92221-6_14

M3 - Chapter

SN - 9783540922209

VL - 5401 LNCS

SP - 197

EP - 216

BT - Principles of Distributed Systems

PB - Springer

ER -