We present an extensive experimental study of authenticated data structures for dictionaries and maps implemented with skip
lists. We consider realizations of these data structures that allow us to study the performance overhead of authentication
and persistence. We explore various design decisions and analyze the impact of garbage collection and virtual memory paging,
as well. Our empirical study confirms the efficiency of authenticated skip lists and offers guidelines for incorporating them
in various applications.
This work was supported in part by IAM Technology, Inc. and by the National Science Foundation under grants IIS–0324846 and
CCF–0311510. The work of the first author was done primarily as a consultant to Brown University.