40
applicationsmanipulateeditinghistories,asinTimewarp(Edwards1997;EdwardsandMynat
1997),usuallyaddingneweditingoperationstoaparticularhistory(andthusupdatingthe
history),sometimesremovingchangesfromthathistory(andundoingpreviouslydoneop-
erations,orotherwiseadjustingorexaminingitsstructure(revealingtheactionsthathave
affectedit,andmergingdivergentstates).Althoughhistoriesmayhavedifferentforms,each
historydefinesastateofthedatastructure.Dataissharedbysharinghistories,and
concurrencyiscontrolledbymanagingthedifferencesbetweenhistories(asdeterminedby
thechangesthatbelongtothem).
Iwillconcentrateonthelogicalandformalproblemsinvolvedinimplementingsystems
thattreatchangesasfirst-classobjects.Inpresentingthiskindofcapability,Timewarpap-
pealstothenotionoftimetravelandquantumuncertaintyasaguidetotheconcurrency
modelanditsuserinterface.PalimpsestinsteadappealstotheCopenhagen,or“multiple
worlds”interpretationofquantummechanics.Historiesexistonlyastheyareexplicitlycon-
structedbyanapplication,andmanyalternatehistoriesarepossible,givenasetofopera-
tionsthatapplytothesamedata.Applicationsmaychoosetoconstructlinear,singlestate,
branchingorgeneralizedacyclichistories.Anysetofchangesdefinesahostofpossibleal-
ternativestatesoftheshareddata,dependingonexactlyhowthechangesarecombinedand
limitedonlybylogicalconstraintsastowhatcombinationsaremeaningful.Onlystatesthat
“cometoconsciousness”bybeinginstantiatedbyanapplicationareactuallyrealized,even
temporarily.Themanynever-instantiatedstatesareimportant,however.Likeahaloofvir-
tualparticles,theyrepresentauthorialoptionsforrevisionsnevermade.Thesizeofthisvir-
tualstatespaceessentiallydeterminestheflexibilityofachange-orientedconcurrencysys-
tem,sinceitisexactlythissetofpotentialstatesthatdetermineswhatoptionsforresolving
conflictsareavailable,eachlegalchoicerepresentsapossibilitythatmightbeusefulinsome
situation.

41
ThePalimpsestformalmodelpreciselydescribesaparticularsetoffundamentalsequence
operationsandmergestrategies.Thisformalmodelisonesolutiondrawnfromacomplex
designspace;itisbasedonbothpracticalconsiderationsandlogicalconstraints.Becauseof
themanyinteractionsofthebasicdatamodelwithuserinterface,systemsinfrastructure
anduserexpectations,theapplicationproblem(evenforoneapplication)almostcertainly
hasnosingleanalyticallydeterminedsolution;itratherallowsonlyvaryingcompromises
amongconflictingrequirements.WhilePalimpsestapplicationprogrammerscanbe(andare)
offeredsomechoiceintermsofstrategiesforoperationconflictresolution,adata-oriented,
declarativeapproachrequiresaclearlydefinedbaselevelsemantics(whichmaynotbeto-
tallyindependentofpolicy)andwhichformsthefoundationonwhichaparticularsystem
canbebuilt.
2.2 Datatypesandoperationtypes
Ifoperationsaretobethefundamentalentitiesincontrollingconcurrentaccessanded-
itingofadatastructure,twofactorsareofprimaryimportance.Theexactdatastructure
beingsharedisonecriticalfactor.Anotheristheinteractionofchangeswhentheyarecom-
binedintohistories.Finally,thestructureofhistoriesaffectsthedefinitionsofoperations
andtheirpreciseinteractions.Whilethesefactorsareconceptuallyindependent,specific
decisionsonanyofthesedimensionsinteractwiththepossibledecisionsonotherdimen-
sions.Furthermore,evenfortheextendablesequence,thedatatypeforwhichIwillconsider
arelativelyfullrangeofpossibilities,theappropriatenessofparticularhistorystructuresand
interactionsmayvarydependingonthespecificapplication,becauseofdiffering,equally
sensible,possiblemethodsofresolvingconflicts.Palimpsestmakesasfewpolicydecisionsas
possible,whileensuringthattextualauthoringisaccommodatedbytheresultingsystem.
Perhapstheprimaryfactorindeterminingthesetofoperationsforadatastructureisthe
datastructureitself.Iwillconsiderdatastructuresasalgebraicdatatypesinthestyleofa