Today's lecture is our second and final lecture on time travel, or more precisely, temporal data structures. Here we will study retroactive data structures, which mimic the "plastic timeline" model of time travel. For example, in Back to the Future, Marty goes back in time, makes changes, and returns to the present that resulted from those changes and all the intervening years. In a partially retroactive data structures, the user can go back in time, perform an additional operation, return to the present that results, and query the resulting data structure. In this way, we maintain a single (changing) timeline, consisting of the sequence of update operations. Retroactive data structures can add, or remove, an update at any time, not just the end (present). A fully retroactive data structure can furthermore query the data structure at any time in the past. Finally, a third type of retroactivity, called "nonobvious", puts queries on the timeline as well, and reports the first query whose answer changed. As you might expect, retroactivity is hard to obtain in general, but good bounds are known for several data structures of interest.
The Massachusetts Institute of Technology (MIT), founded in 1861, is located in Cambridge, Massachusetts, and is one of the foremost U.S. institutions in science and technology. It is comprised of five schools and one college, including the renowned School of Engineering and Sloan School of Management, offering Bachelor's, Master's, and Doctorate degrees. Notable alumni include Ben Bernanke, Chairman of the Federal Reserve, Benjamin Netanyahu, prime minister of Israel, and American astronaut "Buzz" Aldrin.