容错堆栈
问题
基于指针的数据结构容易受到内存故障的影响,这会改变元素之间的链接。 此类故障可能导致数据结构的部分或全部内容丢失。 (想象一个单向链表:被内存故障损坏的单个指针会使列表中的所有以下元素都无法访问。)内存故障很容易观察到(尽管它们通常会导致系统崩溃),并且最近的各种工作都描述了现代 DRAM 对此类故障的敏感性,甚至可以由精心编写的旨在破坏数据的程序引起(例如,[1, 2, 3])。
潜在的解决方案
帮助减少内存故障对基于指针的数据结构的影响的一种方法是简单地复制数据结构的全部内容。 这需要大量的存储开销和额外的操作来保持副本之间的一致状态。 为了避免最多n 个错误,一个数据结构必须被复制n + 1 次。
为了帮助减少帮助容错所需的开销,Aumann 和 Bender [4] 设计了几种容错数据结构。 他们的主要思想是使用较低开销的方法,允许数据结构中最多n 个元素出现故障
2021-06-22 15:04:40
4KB
C
1