what is the History of DATA STRUCTURE IN C++ ?

Characterizing History Independent

Data Structures

 
     In the early 1970s, Dennis Ritchie of Bell Laboratories was engaged in a project to develop a new operating system.  Ritchie discovered that in order to accomplish his task he needed the use of a programming language that was concise and that produced compact and speedy programs. This need led Ritchie to develop the programming language called C.

     In the early 1980's, also at Bell Laboratories, another programming language was created which was based upon the C language.  This new language was developed by Bjarne Stroustrupand was called C++.  Stroustrup states that the purpose of C++ is to make writing good programs easier and more pleasant for the individual programmer.  When he designed C++, he added OOP (Object Oriented Programming) features to C without significantly changing the C component.  Thus C++ is a "relative" (called a superset) of C, meaning that any valid C program is also a valid C++ program.

     There are several versions of the C++ language, of which Visual C++ is only one.  Other dialects include Borland C++, Turbo C++, and Code Warrior (Mac).  All of these software packages enable you to create computer programs with C++, but they all implement the C++ language in a slightly different manner.  In an attempt to maintain portability of both the C and C++ languages, the American National Standards Institute (ANSI) developed a standard of consistency for C and C++ programming.  While we will be working primarily with this ANSI standard, we will also be examining the idiosyncrasies of Microsoft Visual C++ 6.0.

Note:  Due to their power and ease of use, C and C++ were used in the programming of the special effects for Star Wars.

Jason D. Hartline1, Edwin S. Hong1, Alexander E. Mohr1,

William R. Pentney1, and Emily C. Rocke1

Department of Computer Science, University of Washington, Seattle, WA 98195.

{hartline,edhong,amohr,bill,ecrocke}@cs.washington.edu

Abstract. We consider history independent data structures as proposed

for study by Teague and Naor [2]. In a history independent data structure,

nothing can be learned from the representation of the data structure

except for what is available from the abstract data structure. We show

that for the most part, strong history independent data structures have

canonical representations. We also provide a natural less restrictive definition

of strong history independence and characterize how it restricts

allowable representations. We also give a general formula for creating dynamically

resizing history independent data structures and give a related

1 Introduction

On April 16, 2000, the New York Times published an article regarding the CIA’s

role in the overthrow of the Iranian government in 1953. In addition to the article,

the Times’ website posted a CIA file from 1954 which detailed the actions of

various revolutionaries involved in the plot. The Times opted to black out many

of the names mentioned in the document; some of the people referred to were

still alive and residing in Iran and could have been put at risk for retribution.

The file was published as an Adobe PDF file that contained the original document

in its entirety and an overlay covering up parts of the document. Shortly

after releasing the document, some Internet users reverse engineered the overlay

and made the original document available on the Web. In an environment

where information is valuable, private, incriminating, etc., data structures that

retain information about previous operations performed upon them can cause

considerable problems; the Times’ blunder represents a particularly grievous instance

of this. History independent data structures are designed not to reveal

any information beyond that necessarily provided by the contents of the data

structure.

The idea of maintaining a data structure so that no extraneous information is

available was first explicitly studied by Micciano [1]. This work studied “oblivious

trees” where no information about past operations could be deduced from the

pointer structure of the nodes in the search tree. In [3], Snyder studied bounds

on the performance of search, insert and delete functions on uniquely represented

data structures, which employ a canonical representation for each possible state

of the data structure. More stringent history independence requirements were

studied by Naor and Teague in [2]. In their model, the entire memory representation

of a history independent data structure, not just the pointer structure, must

not divulge information about previous states of the data structure. Following

[2] we consider two types of history independence: weak history independence, in

which we assume that a data structure will only be observed once; and strong

history independence, in which case the data structure may be observed multiple

times. A data structure is history independent if nothing can be learned from

the data structure’s memory representation during these observations except for

the current abstract state of the data structure.

In Section 3 we give a simple definition of strong history independence. In the

full version of this paper we show that this definition equivalent to that of [2].

Under this definition, any strong history independent implementation of a data

structure must satisfy a natural canonicality criterion (Section 4)

. For example,

a strongly history independent implementation of a hash table has the property

that up to randomness in the initialization of the hash table, e.g., the choice of

hash functions, the hash table’s representation in memory is deterministically

given by its contents. This answers an open question posed in [2] about the

necessity of canonical representations.

In Section 5 we consider a natural relaxation of strong history independence,

where non-canonical representations and randomness can be used. However, we

show that even under this less restrictive definition, there are still very stringent

limitations on using non-canonical representations.

Finally, in Section 6 we discuss the issue of creating dynamically resizing

history independent data structures. We give a general technique for dynamically

resizing weak history independent data structures in amortized constant

time against a non-oblivious adversary. We prove that no such technique exists

for strongly history independent dynamically resizing data structures. This

result provides insight into the open problem of whether there is a complexity

separation between weak and strong history independence [2].