Optimal Resilient Dynamic Dictionaries⋆

DAIMI Report Series

View Publication Info
 
 
Field Value
 
Title Optimal Resilient Dynamic Dictionaries⋆
 
Creator Brodal, Gerth Stølting
Fagerberg, Rolf
Jørgensen, Allan Grønlund
Moruz, Gabriel
Mølhave, Thomas
 
Description Abstract. In the resilient memory model any memory cell can get cor- rupted at any time, and corrupted cells cannot be distinguished from uncorrupted cells. An upper bound, , on the number of corruptions and O(1) reliable memory cells are provided. In this model, a data structure is denoted resilient if it gives the correct output on the set of uncor- rupted elements. We propose two optimal resilient static dictionaries, a randomized one and a deterministic one. The randomized dictionary supports searches in O(log n + ) expected time using O(log ) random bits in the worst case, under the assumption that corruptions are not performed by an adaptive adversary. The deterministic static dictionary supports searches in O(log n + ) time in the worst case. We also in- troduce a deterministic dynamic resilient dictionary supporting searches in O(log n + ) time in the worst case, which is optimal, and updates in O(log n + ) amortized time. Our dynamic dictionary supports range queries in O(log n + + k) worst case time, where k is the size of the output.
 
Publisher Aarhus University
 
Contributor
 
Date 2007-01-01
 
Type info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
Peer-reviewed Article
 
Format application/pdf
 
Identifier http://ojs.statsbiblioteket.dk/index.php/daimipb/article/view/7222
10.7146/dpb.v36i585.7222
 
Source DAIMI Report Series; No 585 (2007): PB-585 Optimal Resilient Dynamic Dictionaries
DAIMI Report Series; No 585 (2007): PB-585 Optimal Resilient Dynamic Dictionaries
2245-9316
0105-8517
 
Language eng
 
Relation http://ojs.statsbiblioteket.dk/index.php/daimipb/article/view/7222/6162
 

Contact Us

The PKP Index is an initiative of the Public Knowledge Project.

For PKP Publishing Services please use the PKP|PS contact form.

For support with PKP software we encourage users to consult our wiki for documentation and search our support forums.

For any other correspondence feel free to contact us using the PKP contact form.

Find Us

Twitter

Copyright © 2015-2018 Simon Fraser University Library