Repository navigation
Expand file tree
/
Copy patharchitecture_of_continuity.tex
More file actions
3680 lines (2615 loc) · 444 KB
/
Copy patharchitecture_of_continuity.tex
File metadata and controls
3680 lines (2615 loc) · 444 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
% The Architecture of Continuity
% Compile with lualatex or pdflatex, two passes.
\documentclass[11pt,twoside,openright]{book}
\usepackage[a4paper,inner=30mm,outer=25mm,top=30mm,bottom=32mm]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{iftex}
\ifPDFTeX
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{mathpazo}
\usepackage{courier}
\else
\usepackage{mathpazo}
\usepackage{fontspec}
\setmainfont{TeX Gyre Pagella}
\setmonofont[Scale=MatchLowercase]{DejaVu Sans Mono}
\fi
\usepackage{microtype}
\usepackage{booktabs}
\usepackage{longtable}
\usepackage{array}
\usepackage{enumitem}
\usepackage{fancyhdr}
\usepackage{titlesec}
\usepackage{listings}
\usepackage[dvipsnames]{xcolor}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,positioning,calc,shapes.geometric,fit,decorations.pathreplacing}
\usepackage[hidelinks,bookmarksnumbered]{hyperref}
\usepackage[nameinlink]{cleveref}
\usepackage{setspace}
\setstretch{1.06}
\setlength{\parindent}{1.4em}
\setlength{\parskip}{0pt}
\raggedbottom
\lstset{basicstyle=\ttfamily\small,columns=fullflexible,keepspaces=true,
frame=single,framerule=0.3pt,rulecolor=\color{black!40},
breaklines=true,xleftmargin=0.5em,xrightmargin=0.5em,
aboveskip=0.8em,belowskip=0.8em,showstringspaces=false}
\pagestyle{fancy}
\fancyhf{}
\fancyhead[LE]{\small\nouppercase{\leftmark}}
\fancyhead[RO]{\small\nouppercase{\rightmark}}
\fancyfoot[C]{\small\thepage}
\renewcommand{\headrulewidth}{0.3pt}
\fancypagestyle{plain}{\fancyhf{}\fancyfoot[C]{\small\thepage}\renewcommand{\headrulewidth}{0pt}}
\titleformat{\part}[display]{\centering\normalfont\Huge\bfseries}{\partname\ \thepart}{12pt}{\Huge}
\titleformat{\chapter}[display]{\normalfont\huge\bfseries}{\chaptertitlename\ \thechapter}{10pt}{\Huge}
\titlespacing*{\chapter}{0pt}{0pt}{26pt}
\setcounter{tocdepth}{1}
\setcounter{secnumdepth}{2}
% Theorem environments, numbered within chapters
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[chapter]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{countermodel}[theorem]{Countermodel}
\newtheorem{principle}[theorem]{Principle}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\crefname{theorem}{Theorem}{Theorems}
\crefname{proposition}{Proposition}{Propositions}
\crefname{lemma}{Lemma}{Lemmas}
\crefname{definition}{Definition}{Definitions}
\crefname{conjecture}{Conjecture}{Conjectures}
\crefname{countermodel}{Countermodel}{Countermodels}
\crefname{principle}{Principle}{Principles}
\crefname{example}{Example}{Examples}
\crefname{remark}{Remark}{Remarks}
% Epistemic status labels. Every major claim carries exactly one.
\newcommand{\Proved}{\textup{\textsc{[proved under stated assumptions]}}}
\newcommand{\Tested}{\textup{\textsc{[experimentally investigated]}}}
\newcommand{\Conj}{\textup{\textsc{[conjectural]}}}
\newcommand{\Design}{\textup{\textsc{[design argument]}}}
% Notation
\newcommand{\R}{\mathcal{R}}
\newcommand{\Ag}{\mathsf{A}}
\newcommand{\Ob}{\mathsf{O}}
\newcommand{\Hist}{\mathcal{H}}
\newcommand{\Rec}{\operatorname{Rec}}
\newcommand{\Cont}{\operatorname{Cont}}
\newcommand{\Phys}{\operatorname{Phys}}
\newcommand{\Refp}{\operatorname{Ref}}
\newcommand{\Oper}{\operatorname{Op}}
\newcommand{\Suff}{\operatorname{Suff}}
\newcommand{\Pow}{\mathcal{P}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Prob}{\mathbb{P}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\img}{\operatorname{im}}
\newcommand{\anc}{\preceq}
\DeclareMathOperator{\Anc}{Anc}
\DeclareMathOperator{\Cl}{cl}
\DeclareMathOperator{\Rd}{Reads}
\title{\textbf{The Architecture of Continuity}\\[0.6em]
\Large Naming, Memory, Versioning, and the Mathematical Foundations\\ of Scientific Institutions}
\author{Flyxion\\[0.3em]\normalsize Independent Researcher}
\date{November 2026}
\begin{document}
\frontmatter
\maketitle
\chapter*{Abstract}
\markboth{Abstract}{Abstract}
\noindent This monograph develops a general account of how artifacts, and the people and institutions that produce them, remain usable by future agents. The starting point is elementary: an author who saves a file, names a directory, or writes a comment above a function is making a prediction about a later encounter in which the author's present knowledge will be partly unavailable. The book argues that this prediction problem is the common root of operating-system namespaces, filesystem hierarchies, naming conventions, documentation, package management, version control, repository hosting, computational reproducibility, and the public argumentation systems through which scientific claims are corrected. A sequence of formal definitions separates three kinds of persistence (physical, referential, and operational), introduces a hierarchy of continuation classes with minimal sufficient contexts, and treats naming as a retrieval problem under uncertainty. The same vocabulary is then carried through the history of software distribution, the formation of the individual developer, a mathematical theory of repository institutions (typed graphs, lineage, authority, admissibility, federation, and portability), the repository as a scientific instrument, and semantic and epistemic infrastructure for knowledge versioning. The final part examines the architectural requirements for independent scientific infrastructure and the limits of repository-based science. Every major claim carries one of four epistemic labels: proved under stated assumptions, experimentally investigated, a design argument, or conjectural. No architectural aspiration is presented as a mathematical result.
\tableofcontents
\chapter*{Preface}
\addcontentsline{toc}{chapter}{Preface}
\markboth{Preface}{Preface}
A repository begins as a convenience and ends as an institution only if certain things happen along the way. Files must acquire names that can be searched for. Names must acquire contexts that disambiguate them. Contexts must be recorded in forms that survive the departure of whoever understood them. Changes must be recorded in a manner that allows later readers to tell what was altered and why. Disagreements about which continuation of a body of work is authoritative must have procedures, however informal. Claims drawn from the work must be connected to the evidence and the reasoning that support them, so that a later reader can evaluate them without trusting the author. This book is an attempt to say precisely what these requirements are, in what order they arise, which of them can be mechanized, and which of them cannot.
The subject is deliberately broader than any hosting service. Repository hosting is a late and contingent development in a long history of attempts to keep work usable across time, and a theory that took one provider as its object would inherit the provider's accidents. The book therefore begins with externalized memory, proceeds through accounts, namespaces, permissions, paths, and naming, and arrives at hosted collaboration only after the problems that collaboration solves have been stated in neutral terms. Hosting services appear as historical examples and as sources of counterexamples, never as the definition of the object of study.
Three conventions govern the exposition. First, formal definitions are given for the notions that carry weight in later arguments, and informal discussion is separated from them. Second, results are classified. A statement marked \Proved{} is a theorem or proposition proved from assumptions that are stated beside it. A statement marked \Tested{} has been investigated through small computational experiments described in the appendices, with the understanding that experiment does not establish a universal claim. A statement marked \Design{} is an argument about what a system ought to provide, not a claim about what any system does provide. A statement marked \Conj{} is a conjecture, offered because it is precise enough to be refuted. Second-order claims of this kind are kept apart from the historical narrative, which relies on documented sources listed in the bibliography and is otherwise described cautiously where records are incomplete.
Third, and with a stated limitation, the treatment of the semantic and argumentative systems discussed in Part~\ref{part:semantic} is interface-first. Those systems exist as independent specifications with their own established definitions, and this book does not replace their vocabulary. Where a chapter requires a notion from them, the notion is stated as an abstract interface, and the correspondence with the specification is recorded in the appendix on cross-reference mapping. Results about them proved here hold for the abstract interface and transfer to a specification exactly when the specification satisfies the stated assumptions.
The nine parts are arranged so that each depends on the earlier ones but can be read for its own sake. Part~\ref{part:recall} states the problem of future recall and the three notions of persistence. Part~\ref{part:identity} treats identities, namespaces, permissions, and naming. Part~\ref{part:reuse} treats the disciplines through which artifacts are made reusable: scripts, templates, documentation, dependencies, and conventions. Part~\ref{part:history} gives the history of software continuity up to Git and hosted repositories. Part~\ref{part:developer} describes the progressive acquisition of capability by a developer, distinguishing what a person can do from what the person knows can be done. Part~\ref{part:math} is the mathematical core, concerned with typed repository graphs, lineage, authority, admissibility, divergence, and portability. Part~\ref{part:science} applies the framework to computational science, reproducibility, and priority. Part~\ref{part:semantic} treats knowledge versioning beyond files. Part~\ref{part:institution} turns to architectural requirements, independence from particular providers, and the limits of the whole enterprise.
\section*{Relation to Previous Work}
This book is a synthesis of research lines developed earlier by the author, and the new contribution is the explicit derivation that runs from individual memory and filesystem organization to repository institutions and the preservation of scientific knowledge. Three lines converge here. The first is the semantic infrastructure line, which begins with the RSVP-Polyxan unified field theory of semantic hyperstructures \cite{flyxion2025rsvp} and its category and sheaf formalization of selective semantics \cite{flyxion2025membrane}, and continues through a coherence-first account of identity and provenance \cite{flyxion2026coherence} and a study of manifold-aligned semantic dynamics \cite{flyxion2026manifold}, together with the Polyxan specifications and PlenumHub that are treated in Part~\ref{part:semantic}. The second is the historical and operational continuity line, represented by the work on persistence, event histories, replay, procedural ontology, and repair, including the deterministic event-sourced operating system Spherepop. The third is the epistemic accountability line, represented by the study of correction and answerability \cite{flyxion2026geometry}, by the Adversaria specification of a public claim graph \cite{flyxion2026adversaria}, and by a series of shorter essays on evidence, provenance, and verification. Earlier essays on memory, retention, and digital decay supply the motivation for Part~\ref{part:recall}. The titles and dates of these works have been recovered from the author's repositories and have not all been checked against canonical versions; several are specifications or project names and not independently published papers, and some exist in more than one version. They are cited for orientation and not as evidence for any result in this book, and each theorem here is proved or investigated from the definitions given in these pages.
\section*{Information Retrieval, Personal Information Management, and the Governance of Shared Repositories}
The problem of preserving an artifact for a future interpreter has antecedents in several established research traditions. Information retrieval examines the representation, indexing, ranking, and recovery of documents; personal information management examines how individuals keep, organize, and rediscover information over time; and research on open-source governance examines the rules through which distributed communities coordinate contributions and maintain collective projects. These literatures address different scales of a common difficulty: information does not remain useful merely because it remains stored. Its continued use depends on relations among artifacts, agents, descriptions, practices, and institutions.
\subsection*{Information retrieval and the problem of recoverability}
Classical information retrieval distinguishes a collection of documents from the mechanisms by which documents become accessible in response to queries. Manning, Raghavan, and Sch\"utze \cite{manning2008} develop the foundations of document indexing, query processing, ranking, and retrieval evaluation. Their treatment makes clear that the existence of relevant information in a collection does not entail that a retrieval system will return it, or that a returned document will satisfy the user's information need. This anticipates the separation developed in this monograph between physical and referential persistence. A file may be preserved without remaining discoverable to an agent whose vocabulary, knowledge, or retrieval tools have changed, and an improved index may restore accessibility to an artifact whose physical representation has not changed at all.
The present framework extends the retrieval problem by asking what happens after the artifact is found. A retrieved program may lack its dependencies, a recovered dataset may lack its measurement protocol, and a discovered scientific claim may lack the evidentiary record necessary for evaluation. Referential persistence is therefore necessary for many forms of continuation but is not sufficient for operational persistence. There is also a difference between the usual evaluation of retrieval systems and the problem considered here. Retrieval effectiveness is commonly assessed relative to a specified collection, query set, and relevance judgments. Continuation introduces a temporal dimension: the future agent may not know which query to formulate, which collection to search, or which interpretation of the recovered artifact is correct. Naming and metadata must therefore be understood partly as predictions about the information available to an unknown future searcher.
\subsection*{Personal information management and the future self}
The personal information management literature approaches this difficulty from the standpoint of an individual who must preserve information for later use. Jones \cite{jones2007} treats personal information management as a collection of activities involving finding, keeping, organizing, maintaining, and making sense of information, and Jones and Teevan \cite{jonesteevan2007} situate these activities within the practical limitations of attention, time, and the changing circumstances in which information is needed. An especially relevant empirical contribution is the study by Barreau and Nardi \cite{barreau1995}, which synthesizes investigations of how people organize and recover computer files. Their findings emphasize the importance of location-based retrieval as a means of reminding, alongside users' reluctance to construct elaborate filing systems. The location of an artifact can therefore serve not merely as an address but as a cue to the activity, project, or purpose with which the artifact was associated.
This observation has consequences for the interpretation of directory hierarchies. A directory path is simultaneously a retrieval mechanism and a partial representation of the context in which a file was produced. Reorganization may improve one mode of retrieval while damaging another, and replacing a familiar hierarchy with a search index can reduce lookup costs without necessarily preserving the contextual cues supplied by the original arrangement. The present monograph differs from personal information management research in treating the future self as one instance of a more general class of successor agents. The later interpreter may be another developer, a scientific reviewer, an automated build system, or an institution that inherits responsibility for an abandoned project. The formal notion of continuation developed here is intended to express that transfer without assuming that the successor possesses the producer's memories. It also distinguishes the preservation of sufficient information from the practical problem of selecting and interpreting that information under bounded effort, a distinction that remains an important limitation of the monotone sufficiency model.
\subsection*{Open-source development as collective institutional organization}
The open-source literature examines the corresponding problem at the level of distributed communities. Raymond's account of the cathedral and bazaar models \cite{raymond1998} offers an influential comparison of development practices, particularly the role of distributed participation and iterative correction. It is best read as a historically influential architectural argument and not as a universal empirical law of software production. O'Mahony and Ferraro \cite{omahony2007} provide a more directly institutional analysis. Their study of an open-source community describes the emergence of formal authority together with mechanisms that limit and legitimate its exercise. Governance in this account is not reducible to the technical ability to modify shared code. It concerns the procedures through which participants acquire authority, contest decisions, and coordinate their contributions.
Schweik and English \cite{schweik2012} extend the institutional perspective by examining open-source software projects as commons, including the conditions associated with project success and abandonment. Their analysis makes the persistence of a collaborative project a question of social organization as well as technical maintenance. A repository can remain publicly accessible after its community has ceased to maintain it; equally, a community can preserve the practical continuity of a project while migrating its infrastructure. The development of hosted repositories adds another dimension. Dabbish and colleagues \cite{dabbish2012} investigate how visible activity on GitHub supports social inference, coordination, learning, and reputation. The repository is consequently more than a store of source-code revisions, since its public activity records provide information about participants and their relationships that cannot be reconstructed from the source tree alone. This motivates the separation, developed later in this book, between the Git object graph and the institutional graph maintained around it. Commit ancestry records one kind of continuity, while issues, reviews, permissions, organizational membership, and public recognition record others, and the latter participate in the determination of which contributions are accepted, which histories are treated as authoritative, and which agents can legitimately continue a project.
\subsection*{The contribution of a unified continuation framework}
These research traditions establish much of the phenomenology from which the present argument begins. Information retrieval already recognizes the gap between storage and discovery, personal information management the difficulty of preserving useful context for later encounters, and open-source governance research the need of distributed production for institutions of authority, coordination, and legitimation. The proposed contribution of this monograph is not the discovery of these difficulties individually. It is an attempt to place them within a common formal vocabulary and to examine their dependencies across scales. The resulting questions are more demanding than whether a document can be found, a program can be executed, or a project can attract contributors. They concern whether a future agent can recover the conditions under which an artifact may be used correctly, modified safely, evaluated independently, and incorporated into an authorized continuation of a shared history.
No claim is made that the three literatures can be reduced to one another. Retrieval effectiveness does not determine institutional legitimacy, and a valid governance procedure does not guarantee scientific correctness. The value of the continuation framework depends instead on its ability to identify the information and relations that each kind of activity requires, to distinguish those requirements from one another, and to specify the transformations under which they are preserved or lost. In this sense the architecture of continuity is neither a theory of search alone nor a theory of version control alone. It is a proposed theory of the conditions under which recorded work remains available for responsible action after the circumstances of its production have changed.
\mainmatter
\part{The Problem of Future Recall}\label{part:recall}
\chapter{Externalized Memory Under Limited Recall}\label{ch:memory}
\section{The prediction made at the moment of saving}
Every act of saving is addressed to a reader who does not yet exist. The reader may be the same biological individual, but the individual who returns to a file after a year is in a different informational state from the one who wrote it. The writer knew why the file was created, what problem it addressed, which assumptions it embodied, where related files could be found, and what had been tried and abandoned. The returning reader knows some of this, imperfectly, and is typically unaware of how much has been lost. The asymmetry has a precise consequence: the cost of making an artifact usable is borne at the moment when its necessity is least apparent, because the writer's present understanding makes the artifact seem self-explanatory.
This asymmetry is the basic fact from which the rest of the book proceeds. It is not a claim about unusual forgetfulness. It follows from any model in which an agent's accessible knowledge decays or is displaced faster than the artifacts the agent produces. Human memory has this property; so do organizations, in which personnel turn over; so do research communities, in which the practices that make a result reproducible are seldom written down. The problem is general, and so the vocabulary used to treat it should not presuppose any particular medium.
\begin{definition}[Agents, artifacts, and encounters]\label{def:encounter}
An \emph{agent} is a system with an internal state that can change over time, a repertoire of operations, and a capacity to search. Write $\sigma_a(t)$ for the state of agent $a$ at time $t$. An \emph{artifact} is a finitely describable object $x$ that persists, if it persists, independently of the state of any particular agent. An \emph{encounter} is a triple $(a,x,t')$ in which agent $a$ attempts at time $t'$ to find, interpret, or use artifact $x$ that was produced at some earlier time $t<t'$ by an agent $a_0$. The \emph{delay} of the encounter is $\Delta=t'-t$. The agents $a_0$ and $a$ may be identical as individuals while differing as states, so that $\sigma_{a_0}(t)\neq\sigma_a(t')$ in general.
\end{definition}
The definition makes no assumption that the later agent is a person. A build system, a search index, a language model that is asked to continue a project, and a reviewer reconstructing a published analysis are all agents in the relevant sense. What distinguishes them is the repertoire of operations they can perform and the background knowledge they bring, both of which enter the analysis through the notion of context introduced below.
\section{Recall, retrieval, and interpretation}
The word remembering conflates at least three distinct capacities. An agent may remember that an artifact exists, may remember where it is, and may remember what it is for. The first is awareness, the second is location, and the third is understanding. Ordinary usage treats them as a single capacity because in everyday objects they usually fail together or not at all. In stored digital artifacts they come apart. A person may recall writing a script that computes a graph statistic, have no idea which directory contains it, and be unable, on finding it, to say why it uses a particular normalization. Each of these failures is independent of the others, and each calls for a different remedy. Awareness is supported by indexes and catalogs, location by naming and structure, and understanding by documentation and tests.
\begin{principle}[Remembering is not retrieving]\label{pr:notretrieving}
For an artifact $x$ and an encounter $(a,x,t')$, the following three conditions are logically independent: that $x$ continues to exist in some physical form; that $a$ can identify and obtain $x$ within a bounded effort; and that $a$ can use $x$ correctly for the purposes of the encounter. Practices intended to support future encounters must be evaluated against each condition separately.
\end{principle}
This principle is stated here without proof because it is a design principle; the formal version, with independence established by countermodels, is given as \Cref{prop:independence} in the next chapter. Its practical force is that an investment aimed at one condition does not purchase the others. A reliable backup system secures existence and nothing more. A disciplined naming scheme improves location, whether or not the files it names remain intelligible. A comprehensive manual improves understanding but is useless if nobody can find it.
\section{Externalization and the economy of attention}
A person who writes something down is externalizing a computation. The note holds the result so that the person does not have to hold it. The benefit is the release of attention for present work; the cost is a dependence on the note being found and understood later. Externalization is thus a loan against the future, and like any loan it is cheap when contracted and costly when called in. The relevant economy has two sides. Writers underinvest in future-oriented metadata because the benefit is deferred and uncertain. Readers overinvest in reconstruction because the alternative is to abandon the artifact. The equilibrium is a body of work in which the most important artifacts are the ones that are hardest to use, since the artifacts that matter most are the ones that depend on the most accumulated context.
Institutions can be understood as arrangements that correct this misallocation by making the externalization of context a shared obligation. A laboratory notebook convention, a code review that requires a description, a journal's data availability policy, and a distribution's packaging guidelines are all mechanisms for obliging writers to leave information for readers. They differ in what they require, whom they bind, and how they are enforced. They are comparable because each responds to the same asymmetry.
\section{Scope of the claims}
Some caution about what follows is needed from the outset. The book does not claim that all information should be preserved, that more documentation is always better, or that every artifact deserves long-term care. Preservation has costs, and the formal development in later chapters treats those costs explicitly. Most artifacts should be allowed to lapse, and the interesting question is how to decide which. The claims are conditional: if an artifact is to support a given class of future operations by a given class of agents, then a certain minimum of context must accompany it, and the minimum has a structure that can be studied.
\chapter{Three Kinds of Persistence}\label{ch:persistence}
\section{Physical, referential, and operational persistence}
The distinctions drawn informally in the previous chapter can be sharpened by relating each to an effort bound. An agent never has unlimited effort available, and an artifact that can be found only by an exhaustive search of every storage medium accessible to the agent is, for practical purposes, not findable. The definitions below therefore carry an explicit budget.
\begin{definition}[Physical persistence]\label{def:phys}
Let $W_t$ denote the set of storage states of the world at time $t$. An artifact $x$ is \emph{physically persistent} at $t$, written $\Phys(x,t)$, if there is some state $w\in W_t$ and some decoding procedure $d$ such that $d(w)=x$. The definition ignores whether any agent knows of $w$ or $d$.
\end{definition}
\begin{definition}[Referential persistence]\label{def:ref}
Let $\beta$ be a positive effort budget, measured in whatever units are appropriate (time, queries, cost). An artifact $x$ is \emph{referentially persistent for agent $a$ at time $t'$ within budget $\beta$}, written $\Refp(x,a,t',\beta)$, if there is a retrieval procedure $\rho$ available to $a$ with cost at most $\beta$ such that $\rho$ returns an object $\hat{x}$ and $a$ can verify that $\hat{x}=x$ by a check available to $a$ at cost at most $\beta$. Verification may rely on a stored identifier such as a content hash, on comparison with a remembered feature, or on any other criterion that, given the agent's knowledge, distinguishes $x$ from alternatives.
\end{definition}
\begin{definition}[Operational persistence]\label{def:oper}
Let $K$ be a class of operations. An artifact $x$ is \emph{operationally persistent for agent $a$ at $t'$ with respect to $K$ within budget $\beta$}, written $\Oper(x,a,t',K,\beta)$, if $\Refp(x,a,t',\beta)$ holds and $a$ can perform every operation in $K$ on $x$ correctly, where correctness is judged against the specification of the operation, within budget $\beta$.
\end{definition}
The verification clause in \Cref{def:ref} excludes the case in which the agent retrieves something and takes it for the artifact. Retrieval without verification is a weaker property which is worth naming but does not support continuation, since the agent acting on a wrongly identified object proceeds with false confidence. The operation class $K$ in \Cref{def:oper} is left abstract here and given a structure in the next chapter.
\begin{figure}[t]
\centering
\begin{tikzpicture}[
box/.style={draw,rounded corners=2pt,minimum width=3.3cm,minimum height=0.9cm,align=center,font=\small},
imp/.style={-{Stealth[length=2.2mm]},thick},
fail/.style={draw,dashed,rounded corners=2pt,minimum width=4.6cm,minimum height=0.9cm,align=center,font=\footnotesize}]
\node[box] (o) at (0,3.2) {$\Oper(x,a,t',K,\beta)$\\operational};
\node[box] (r) at (0,1.6) {$\Refp(x,a,t',\beta)$\\referential};
\node[box] (p) at (0,0) {$\Phys(x,t')$\\physical};
\draw[imp] (o.south) -- node[right,font=\footnotesize]{implies} (r.north);
\draw[imp] (r.south) -- node[right,font=\footnotesize]{implies} (p.north);
\node[fail] (f1) at (5.6,0.8) {holds, but the next level fails:\\stored and not findable};
\node[fail] (f2) at (5.6,2.4) {holds, but the next level fails:\\found and not usable};
\draw[dashed] (p.east) -- (f1.west);
\draw[dashed] (r.east) -- (f2.west);
\end{tikzpicture}
\caption{The three kinds of persistence of \Cref{prop:independence}. Solid arrows are implications that hold under the stated assumption. The dashed boxes mark the converses, which fail: an artifact can satisfy a lower level without satisfying the one above it. The figure shows logical dependence and says nothing about the probability of any failure.}
\label{fig:persistence}
\end{figure}
\section{Dependencies among the three}
From the definitions, two implications hold under a natural assumption, and their converses fail.
\begin{proposition}[Ordering of the persistence notions]\label{prop:independence}
Assume that retrieval procedures return only objects obtained from existing storage states. Then:
(i) $\Refp(x,a,t',\beta)$ implies $\Phys(x,t')$; (ii) $\Oper(x,a,t',K,\beta)$ implies $\Refp(x,a,t',\beta)$; (iii) Neither converse holds in general. There exist models in which $\Phys$ holds and $\Refp$ fails for every agent and budget, and models in which $\Refp$ holds and $\Oper$ fails for a nonempty $K$.
\Proved{}
\end{proposition}
\begin{proof}
Part (i): if $a$ retrieves and verifies $x$, then the procedure returned $x$, and by the assumption $x$ was decoded from an existing state, so $\Phys(x,t')$. Part (ii) is immediate from \Cref{def:oper}, which includes $\Refp$ as a conjunct. For part (iii), the countermodels below are given.
\end{proof}
\begin{countermodel}[Present but not locatable]\label{cm:lost}
Let $x$ be a data file on a disk image stored in a box, and let the only record of the box's existence be the memory of an agent who has since died. Then $\Phys(x,t')$ holds, since a decoding of the disk exists, but no agent has any retrieval procedure of bounded cost that reaches it. This is the case that archivists describe as a collection without a finding aid.
\end{countermodel}
\begin{countermodel}[Locatable but not usable]\label{cm:opaque}
Let $x$ be a compiled program with a recorded hash, stored in a known location, written for a hardware platform and a library version that no longer exist and with no source or documentation retained. Then $x$ can be found and verified, so $\Refp$ holds, but an agent who wishes to modify the behavior of $x$ lacks the information needed to do so within any feasible budget. The class $K$ containing modification is not satisfied, so $\Oper$ fails for that $K$ even though it may hold for the class consisting only of copying.
\end{countermodel}
The third persistence notion is relative to $K$, and this is not a defect but a feature. The same artifact may be operationally persistent for one class of operations and not another. A compiled binary that cannot be modified may still be executed on an emulator, a spreadsheet whose macros are broken may still be read as data, and a text file in a forgotten encoding may still be opened and examined as bytes. The relevant questions are always of the form: persistent for whom, within what budget, for what operations.
\section{Failure modes as a classification}
The three notions yield a classification of failures that is more useful than the undifferentiated complaint that something has been lost. A \emph{loss} is a failure of physical persistence: the bits are gone. A \emph{disappearance} is a failure of referential persistence in the presence of physical persistence: the bits exist but cannot be found or cannot be recognized as the sought object. A \emph{decay of intelligibility} is a failure of operational persistence in the presence of referential persistence: the artifact is in hand and unusable. Each has different causes and different remedies, and a program of preservation that addresses only one will produce the others as byproducts. A common instance is the migration of a collection to a new format, which secures physical persistence and often destroys referential persistence by changing identifiers, and sometimes operational persistence by dropping features of the original that were not represented in the new format.
\begin{example}[A migrated mailbox]\label{ex:mailbox}
A mailbox archive is converted from a proprietary format to plain text files in a directory per month. Physical persistence is improved, because plain text has no dependence on a vendor application. Referential persistence is damaged for any agent who formerly located messages by folder hierarchy and flag state, because those are not carried by the new format. Operational persistence with respect to the class of operations \emph{reconstruct a conversation thread} is damaged if message identifiers are not preserved. The migration is a net benefit or a net loss only relative to a stated agent and a stated class of operations.
\end{example}
\section{The role of verification}
The verification clause deserves a closer look, because it marks the place where content addressing enters the story. An agent who holds a hash of an artifact can verify any candidate by recomputing the hash and comparing, so that referential persistence for that agent reduces to the problem of finding any copy of the artifact, wherever it may be. This gives hashes a distinctive role: they separate the identity of an artifact from its location, and so make referential persistence robust against changes of location. They do not provide any of the context needed for operational persistence, and a hash is useless to an agent who has lost the hash. These observations are developed formally in \Cref{part:math}, where content-addressed object graphs are treated in full.
\chapter{Recovery as a Probabilistic Problem}\label{ch:recovery}
The following model abstracts from established information-retrieval models, which evaluate the recovery of documents relative to a collection, a query set, and relevance judgments \cite{manning2008}. It concerns a single artifact and a single delay, and its two channels stand in for the whole apparatus of indexing and query formulation.
\section{A simple model of delayed recovery}
The independence results of the previous chapter are qualitative. Practical decisions about how much effort to spend on naming, documentation, and indexing require a quantitative picture, and a model need not be accurate to be useful for the purpose of exposing the structure of the tradeoff. The following model isolates the principal dependencies.
Let an artifact be produced at time $t$ and an encounter occur at $t'=t+\Delta$. Let $m$ denote the metadata recorded with the artifact (names, comments, indexes, documentation) and $c$ the retrieval context in which the later agent operates (available search tools, search vocabulary, the agent's knowledge of the project). The quantity of interest is
\[
R(x,\Delta\mid m,c)=\Prob\bigl[\text{the agent recovers and correctly interprets }x\text{ after delay }\Delta\bigr].
\]
\begin{definition}[Two-channel recovery model]\label{def:twochannel}
Recovery can occur through two channels that are assumed to succeed independently. The \emph{memory channel} succeeds with probability $p(\Delta)=e^{-\lambda\Delta}$, where $\lambda>0$ is a forgetting rate; it represents the agent's unaided recollection of location and purpose. The \emph{record channel} succeeds with probability $s=s(m,c)\in[0,1]$, which depends on the recorded metadata and the retrieval context but not on $\Delta$ directly. Then
\[
R(\Delta)=1-\bigl(1-e^{-\lambda\Delta}\bigr)\bigl(1-s\bigr).
\]
\end{definition}
The independence assumption is strong, and in practice the channels interact: a person's memory of an artifact's existence prompts a search that uses the metadata. The formula should be read as a benchmark and not as a bound. If the channels are positively dependent, so that success of one makes success of the other more likely, the probability that at least one succeeds is lower than the independent value; if they are negatively dependent, it is higher. The direction of the error therefore depends on the dependence, which is an empirical matter. The value of the model is that it makes certain qualitative consequences explicit, and the consequences of \Cref{prop:twochannel} should be checked for robustness against dependence before being relied on.
\begin{proposition}[Behavior of the two-channel model]\label{prop:twochannel}
Under \Cref{def:twochannel} with $s$ constant in $\Delta$:
(i) $R$ is nonincreasing in $\Delta$, with $R(0)=1$ and $\lim_{\Delta\to\infty}R(\Delta)=s$; (ii) The marginal value of the record channel, $\partial R/\partial s=1-e^{-\lambda\Delta}$, is increasing in $\Delta$ and vanishes at $\Delta=0$; (iii) If an investment of cost $\kappa$ raises $s$ by $\delta s$, then the investment increases the recovery probability by $\delta s\,(1-e^{-\lambda\Delta})$, so it is worthwhile at horizon $\Delta$ with benefit-per-recovery $V$ only when $V\,\delta s\,(1-e^{-\lambda\Delta})>\kappa$.
\Proved{}
\end{proposition}
\begin{proof}
Write $p=e^{-\lambda\Delta}$, so $R=1-(1-p)(1-s)=p+s-ps=s+p(1-s)$. Then $dR/d\Delta=(1-s)\,dp/d\Delta=-\lambda(1-s)e^{-\lambda\Delta}\le 0$, with equality only when $s=1$, which gives monotonicity. At $\Delta=0$, $p=1$ and $R=1$; as $\Delta\to\infty$, $p\to0$ and $R\to s$. For (ii), $\partial R/\partial s=1-p$. For (iii), a small change $\delta s$ yields $\delta R=(1-p)\,\delta s$ to first order, and this is exact because $R$ is linear in $s$. Multiplying by $V$ and comparing with $\kappa$ gives the condition.
\end{proof}
The proposition reproduces a familiar experience in formal terms. Over short horizons, the record channel is nearly worthless, because memory suffices; over long horizons it is nearly everything. A writer who judges the value of documentation from the standpoint of the present, when memory is intact, will rationally underinvest, and this underinvestment is a feature of the decision problem and does not need to be attributed to carelessness.
\section{Non-monotonicity in realistic settings}
The monotone decline in \Cref{prop:twochannel} depended on $s$ being constant. In realistic settings $s$ depends on the retrieval context $c$, which changes. Search tools improve, so that an artifact that was hard to find in one decade is trivially found in the next. Indexes are rebuilt, new naming conventions are adopted, and new contexts supply interpretive keys. It is therefore wrong to suppose that recoverability is a decreasing function of time. A correct statement is that recoverability is the outcome of two processes, the decay of what the agent knows and the evolution of the tools and records the agent can use, and either can dominate.
\begin{proposition}[Recoverability can increase with delay]\label{prop:increase}
There exist time-varying record-channel functions $s(\Delta)$ for which $R(\Delta)$ is strictly increasing on some interval.
\Proved{}
\end{proposition}
\begin{proof}
With $R(\Delta)=s(\Delta)+e^{-\lambda\Delta}(1-s(\Delta))$ we have $R'(\Delta)=s'(\Delta)(1-e^{-\lambda\Delta})-\lambda(1-s(\Delta))e^{-\lambda\Delta}$. Choose $s(\Delta)=\tfrac12$ for $\Delta\le\Delta_0$ and then increase it linearly with slope $\mu$ on $[\Delta_0,\Delta_0+\epsilon]$. At $\Delta_0+$ we have $R'=\mu(1-e^{-\lambda\Delta_0})-\tfrac{\lambda}{2}e^{-\lambda\Delta_0}$, which is positive whenever $\mu>\tfrac{\lambda e^{-\lambda\Delta_0}}{2(1-e^{-\lambda\Delta_0})}$. Such a $\mu$ exists for every $\Delta_0>0$.
\end{proof}
The example is not exotic. A scanned lab notebook that was unreadable in 1990 becomes searchable after optical character recognition improves; a text file in an obscure format becomes readable when a converter is written. The lesson for preservation is that the retrieval context is not a constant of nature and that preserving the raw artifact in its original form keeps open the possibility that a later context will recover what an earlier one could not. Premature normalization, in which an artifact is converted into a convenient form and the original discarded, closes this possibility.
\section{What the record channel consists of}
The function $s(m,c)$ was left abstract. It is useful to decompose it according to the structure of the retrieval task. To recover an artifact, an agent must formulate a query, apply it to some index, select the correct item from the results, and interpret the item. The probability of the whole is a product of the probabilities of the steps conditional on their predecessors. Names and directory structure contribute chiefly to the second and third steps. Documentation contributes chiefly to the fourth. Indexes and search tools contribute to the second. Tests contribute to the fourth, by providing a mechanical check that the agent's interpretation matches the author's. Writing $s=s_1s_2s_3s_4$ for the four conditional success probabilities, any practice that increases one factor increases $s$ by an amount proportional to the product of the others. This multiplicative structure has a notable implication: the factor with the lowest value limits the benefit of improvements to the others. A project with excellent documentation and an unsearchable file structure gains little from further documentation.
\begin{remark}[Calibration]
No numerical values are assumed for $\lambda$ or for the components of $s$. These would have to be estimated for specific populations of agents and artifacts, and the appendix on experimental protocols outlines how such estimates could be obtained from retrospective studies of real projects. The resulting relationships are structural: the shape of the dependence on delay, the multiplicative form of the record channel, and the increasing value of metadata with horizon.
\end{remark}
\chapter{The Continuation Problem}\label{ch:continuation}
\section{From persistence to capability}
The persistence notions of \Cref{ch:persistence} are relative to a class $K$ of operations that the later agent wishes to perform. It is now time to give this class a structure. The structure should capture the intuition that opening a file requires less preserved context than running a script, running a script less than modifying it safely, and modifying it safely less than reproducing a scientific result that depends on it.
\begin{definition}[Operation classes]\label{def:opclasses}
Fix a universe $\mathsf{Op}$ of operations that an agent might perform on an artifact. An \emph{operation class} is a subset $K\subseteq\mathsf{Op}$. Let the following classes be distinguished for artifacts that are programs or program-like, with the understanding that analogues exist for other kinds of artifact:
(a) \emph{Inspection}, $K_{\mathrm{ins}}$: obtaining the artifact's representation and reading it as a sequence of symbols; (b) \emph{Execution}, $K_{\mathrm{exe}}$: running the artifact on some input and obtaining its output; (c) \emph{Correct use}, $K_{\mathrm{use}}$: running the artifact on inputs within its intended domain and interpreting the output as intended; (d) \emph{Safe modification}, $K_{\mathrm{mod}}$: changing the artifact while preserving specified properties; (e) \emph{Reproduction}, $K_{\mathrm{rep}}$: reconstructing a reported result produced by the artifact; (f) \emph{Evaluation}, $K_{\mathrm{evl}}$: judging whether the artifact or the result it supports is correct for the purpose claimed.
\end{definition}
The classes are not nested as sets of operations, but they are ordered by the demands they make on context in typical cases. Evaluation of a result presupposes the ability to reproduce it, since one cannot judge a result one cannot regenerate; reproduction presupposes correct use; and correct use presupposes execution, which presupposes inspection. The ordering is a hierarchy of \emph{requirements}, and the next definition makes this precise.
\begin{definition}[Context and sufficiency]\label{def:context}
Fix a finite universe $I$ of \emph{information items}, each representing a unit of context that might be preserved with an artifact: a build instruction, a dependency version, a statement of the intended input domain, a rationale for a design choice, a statement of the statistical model, and so on. A \emph{context} is a subset $m\subseteq I$. For an artifact $x$, agent $a$, and operation class $K$, the predicate $P_{x,a,K}(m)$ asserts that $a$, given $x$, $m$, and its own background knowledge, can perform $K$ on $x$ correctly. The predicate is assumed \emph{monotone}: if $P_{x,a,K}(m)$ and $m\subseteq m'$ then $P_{x,a,K}(m')$. The set of \emph{sufficient contexts} is
\[
\Suff(x,a,K)=\{m\subseteq I:P_{x,a,K}(m)\}.
\]
\end{definition}
Monotonicity says that additional preserved information never makes an operation impossible. This is an idealization, because in practice irrelevant or misleading information can degrade performance, and a comprehensive archive without a finding aid can be less usable than a short one. The idealization is made so that the structure of sufficiency can be studied separately from the problem of presentation; the effect of noise is treated in \Cref{ch:conventions}.
\section{Structure of sufficient contexts}
\begin{proposition}[Basic structure of sufficiency]\label{prop:suffstructure}
Let $I$ be finite and let $P=P_{x,a,K}$ be monotone with $\Suff(x,a,K)\neq\varnothing$. Then:
(i) $\Suff(x,a,K)$ is an up-set in $(\Pow(I),\subseteq)$, and every sufficient context contains a minimal sufficient context; (ii) If $P_{x,a,K'}(m)$ implies $P_{x,a,K}(m)$ for all $m$ (so that $K'$ is at least as demanding as $K$), then $\Suff(x,a,K')\subseteq\Suff(x,a,K)$; (iii) Minimal sufficient contexts need not be unique, and need not have equal size.
\Proved{}
\end{proposition}
\begin{figure}[t]
\centering
\begin{tikzpicture}[
n/.style={draw,rounded corners=2pt,minimum width=1.6cm,minimum height=0.7cm,font=\small},
suff/.style={fill=gray!25},
mn/.style={very thick},
e/.style={thin}]
\node[n] (0) at (0,0) {$\varnothing$};
\node[n,suff,mn] (a) at (-3,1.6) {$\{a\}$};
\node[n] (b) at (0,1.6) {$\{b\}$};
\node[n] (c) at (3,1.6) {$\{c\}$};
\node[n,suff] (ab) at (-3,3.2) {$\{a,b\}$};
\node[n,suff] (ac) at (0,3.2) {$\{a,c\}$};
\node[n,suff,mn] (bc) at (3,3.2) {$\{b,c\}$};
\node[n,suff] (abc) at (0,4.8) {$\{a,b,c\}$};
\foreach \u/\v in {0/a,0/b,0/c,a/ab,a/ac,b/ab,b/bc,c/ac,c/bc,ab/abc,ac/abc,bc/abc}
\draw[e] (\u) -- (\v);
\end{tikzpicture}
\caption{An up-set of sufficient contexts in $(\Pow(I),\subseteq)$ for $I=\{a,b,c\}$, as in \Cref{prop:suffstructure}. Shaded vertices are sufficient. The two heavy outlines are the minimal sufficient contexts $\{a\}$ and $\{b,c\}$: they are incomparable and of different sizes, so a minimal sufficient context is neither unique nor of fixed cardinality. The example is constructed for illustration and does not describe a particular artifact.}
\label{fig:suffcontexts}
\end{figure}
\begin{proof}
(i) That $\Suff$ is an up-set is the monotonicity assumption. Given a sufficient $m$, if $m$ is not minimal there is a sufficient proper subset; repeating the step yields a descending chain of proper subsets, which terminates by finiteness at a minimal sufficient context contained in $m$. (ii) is immediate from the hypothesis. (iii) is shown by example: let $I=\{r,t,s\}$ and let $P(m)$ hold iff $m\supseteq\{r\}$ or $m\supseteq\{t,s\}$, where $r$ is a README stating the interface, $t$ is a test suite, and $s$ is a sample invocation. Both $\{r\}$ and $\{t,s\}$ are minimal sufficient, with sizes $1$ and $2$.
\end{proof}
Part (iii) corresponds to a familiar fact: there are typically several independent routes by which a later reader can come to understand an artifact. A reader can learn how to use a function from its documentation, from its tests, from its callers, or from reading its body. The preservation problem is not to preserve one route but to choose which routes are worth the cost of preserving.
\begin{definition}[Cost of preservation]\label{def:preservecost}
A \emph{cost function} is a map $\kappa:I\to\mathbb{R}_{\ge0}$ extended additively to contexts by $\kappa(m)=\sum_{i\in m}\kappa(i)$. The \emph{minimum preservation cost} for the family $\{K_1,\dots,K_n\}$ of operation classes is
\[
\min\Bigl\{\kappa(m):m\in\bigcap_{j=1}^{n}\Suff(x,a,K_j)\Bigr\}.
\]
\end{definition}
For a single operation class, the problem is easy when the sufficient contexts are given explicitly as a list of alternatives: take the cheapest. But the interesting problems involve several classes at once, since an author typically wishes to support inspection, use, modification, and reproduction together, and different classes have overlapping routes. Overlap is what makes the combined problem hard.
\begin{proposition}[Hardness of multi-class preservation]\label{prop:nphard}
The decision problem \emph{given a finite family of operation classes, each specified by a list of alternative minimal contexts, a cost function, and a budget, does a context of cost at most the budget lie in all the sufficiency sets?} is NP-complete, even when every alternative minimal context is a singleton and every item has unit cost. The reduction is from Set Cover \cite{karp1972}.
\Proved{}
\end{proposition}
\begin{proof}
Membership in NP is clear, since a proposed context can be checked against each list in polynomial time. For hardness, reduce from Set Cover. Given a universe $U=\{e_1,\dots,e_n\}$, a family of sets $S_1,\dots,S_k\subseteq U$, and an integer $B$, let the information items be $I=\{1,\dots,k\}$ with unit costs. For each $e_i$ define an operation class $K_i$ whose alternative minimal contexts are the singletons $\{j\}$ for every $j$ with $e_i\in S_j$. A context $m\subseteq I$ is sufficient for all $K_i$ simultaneously exactly when for each $i$ it contains some $j$ with $e_i\in S_j$, that is, exactly when $\{S_j:j\in m\}$ covers $U$. A context of size at most $B$ exists iff a cover of size at most $B$ exists.
\end{proof}
The result is a precise sense in which perfect documentation policy is computationally intractable in general. It does not imply that practical policies are intractable, since real structures have regularity that arbitrary instances lack. What it does imply is that no universal procedure for choosing what to preserve can be expected, and that conventions, which fix the family of routes in advance, are valuable partly because they replace an intractable optimization with a lookup.
\section{The ladder and its limits}
The hierarchy of \Cref{def:opclasses} suggests a ladder. At the bottom, inspection requires only that the artifact be retrievable and its encoding known. Execution adds the requirement that the environment can run it: interpreter or processor, libraries, system calls. Correct use adds the intended input domain and the meaning of the outputs. Safe modification adds the invariants the author intended to preserve and the rationale for the design, because a modification is safe only relative to properties, and the properties are not always visible in the code. Reproduction adds the data, the parameters, the randomness, and the measurement procedure for the scientific result. Evaluation adds the criteria by which the result is to be judged, which are partly empirical and partly conventional.
\begin{remark}[The ladder is not universal]
Climbing the ladder is not a developmental inevitability. An artifact may support evaluation in the absence of safe modification, as when a mathematical result is checked by a reader who has no ability to extend the method. An artifact may support execution but not inspection, as when a binary is run on an emulator and nobody can read its source. The ordering describes typical growth in contextual demand and not a strict partial order on capabilities. In particular, evaluation of a scientific result does not presuppose its reproduction: a reader can check a derivation, identify a confounding variable, or detect an invalid inference without executing anything. The requirements of the operation classes are better described as a partial order with several routes to evaluation, of which the ladder is one chain. Later chapters will repeatedly meet the same caution in the setting of developers (\Cref{ch:organizer}), where growth in awareness of available operations does not entail growth in actual ability, and neither entails competence.
\end{remark}
\section{The unifying claim}
All the practices considered in this book can be read as attempts to preserve enough structure that a future agent can recover meaning, evaluate validity, and continue development. A comment above a function and a warrant attached to a scientific claim are different objects, but each preserves information that a later interpreter needs in order to judge whether an operation or a conclusion is legitimate. The remaining parts take this common function and follow it through increasingly institutional settings: from the account on a personal computer to the namespace of a public repository, from a note to oneself to a review process, from a file to a claim.
\begin{definition}[Continuation]\label{def:continuation}
Let $x$ be an artifact produced at time $t$ with preserved context $m\subseteq I$, let $a'$ be an agent at time $t'>t$, and let $K$ be an operation class. Let $A_{t'}$ denote the information that $a'$ can acquire at time $t'$ without access to the circumstances of the production of $x$: public sources, documentation of tools and standards, subsequent research, and the agent's own further investigation. The relation $\Cont(a',x,m,t',K)$ holds when $a'$ can perform every operation in $K$ on $x$ correctly using $x$, $m$, the agent's own knowledge, and information from $A_{t'}$, and without requiring any information from the circumstances of the production of $x$ that is neither contained in $m$ nor recoverable from $A_{t'}$.
\end{definition}
The definition does not require the future agent to be epistemically isolated. What it excludes is dependence on inaccessible historical context, such as the unrecorded intention of a producer, as distinct from the legitimate acquisition of new information. Enlarging $A_{t'}$ weakens the demand on $m$, so that a context $m$ may suffice for an agent in a well-documented field and fail for the same artifact in a field with no accessible literature; sufficiency is accordingly relative to the information environment as well as to the operation class. The final clause is what makes continuation distinct from mere use. A former collaborator who can be asked can often use an artifact whose preserved context is empty, but the dependence on the collaborator is precisely what continuation is meant to remove. Continuation is the property that a work can outlive the availability of its producers.
\part{Identity, Filesystems, and Rights}\label{part:identity}
\chapter{Accounts, Principals, and Namespaces}\label{ch:accounts}
\section{The first institutional distinction}
A person who first sits at a multi-user operating system meets an elementary institutional fact before meeting any program: the machine is not merely a collection of programs but an environment populated by identities, resources, and rules governing what the former may do with the latter. The session begins with a name and a credential. The name selects a principal; the credential supports a claim that the person is entitled to act as that principal. Everything that follows, including the files created, the processes started, and the permissions exercised, is attributed to the principal and not to the person. This separation between the human being and the identity under which the human acts is a long-standing feature of multi-user computing, and it predates Unix: time-sharing systems of the 1960s, among them CTSS and Multics, already attached accounts, credentials, and access rules to users, and Multics in particular developed access control lists and protection rings. Unix simplified and popularized this inheritance. Every later construction in this book, from repository accounts to claim authorship, inherits the separation.
In Unix-like systems a principal is represented internally by a numeric user identifier, and a user may belong to several groups, each represented by a numeric group identifier. The textual user name that appears at the login prompt is a label for the number; the kernel authorizes operations by comparing numbers. In the traditional account database, each user entry carries a name, a numeric identifier, a primary group identifier, a descriptive field, a home directory path, and a login shell. In Windows systems the corresponding construct is the security principal, identified by a security identifier, with a token constructed at logon that lists the principal's identifier, group memberships, and privileges. The two designs differ in many respects, but they agree on the structural point: authorization is decided by identifiers, and labels are for humans.
\section{Identity as a relation}
It is tempting to identify an account with its name. The tempting identification fails for the same reason that identifying a document with its title fails: names can be changed, reused, and shared, while the thing named must remain recognizable across such changes if records about it are to remain meaningful.
\begin{definition}[Namespace and principal]\label{def:namespace}
A \emph{namespace} is a pair $(L,\nu)$ in which $L$ is a set of labels and $\nu:L\rightharpoonup \mathsf{Id}$ is a partial resolution function to a set of identifiers. A \emph{principal} is an element $p\in\mathsf{Id}$ for which authorization predicates are defined. A namespace is \emph{injective} if distinct labels never resolve to the same identifier, and \emph{stable} under an operation if the operation does not change $\nu(\ell)$ for any label $\ell$ outside the operation's declared scope.
\end{definition}
\begin{definition}[Identity as a relation]\label{def:identity}
The \emph{identity} of an agent in an institution is not a single identifier but a relation $\mathrm{Id}\subseteq L\times\mathsf{Id}\times\mathcal{H}\times\mathcal{R}$ among labels, identifiers, histories of recorded actions, and recognitions by other agents. The label tells others what to call the agent, the identifier tells the system whom to authorize, the history records what has been done under the identifier, and the recognition records who treats the agent as the author of that history.
\end{definition}
The four components can vary independently. An agent may change its label while keeping the identifier and history, as when an account is renamed. An agent may lose its identifier while retaining its history in records that mention the label, as when an account is deleted. An agent may acquire a history without recognition, as when contributions are made pseudonymously and no one links them to a person. And a recognition may attach to a label that, over time, has been controlled by several different agents. A theory of identity that collapses these components cannot describe, for instance, the difference between a renamed account and a transferred one.
\begin{proposition}[Rename invariance and reuse hazard]\label{prop:reuse}
Let a filesystem record ownership as a numeric identifier. Then (i) renaming the label of a user does not change the ownership relation on existing files; (ii) deleting a user and later assigning the same numeric identifier to a different user transfers ownership of all files formerly owned by the deleted user to the new user; (iii) consequently, ownership by identifier is a faithful record of authorship only under an additional assumption that identifiers are never reused.
\Proved{}
\end{proposition}
\begin{proof}
Ownership is stored as the pair of numeric identifiers in the file's metadata, and authorization compares numbers. (i) The label resolves to the number through the account database; changing the label changes the database entry and not the numbers stored with files. (ii) After deletion, files retain the old number. When a new account is created with that number, resolution of the stored number now yields the new account. (iii) follows: the ownership relation records an identifier, and the claim that the identifier names the same agent over time is an additional assumption.
\end{proof}
The hazard is no mere curiosity. Hosted repository services face the same structure when an account name is released and claimed by another party: any link, citation, or attribution that depended on the label now points to a different agent, though the numeric identifier used internally by the service differs. Whether the service treats the identifier or the label as the public handle determines which of the persistence notions of \Cref{ch:persistence} the public record enjoys. The matter returns in \Cref{ch:accountsrepo} and, with formal consequences for portability, in \Cref{ch:portability}.
\section{The home directory and the persistent address}
The home directory is the first place at which a principal acquires a persistent association with resources. It is a location in the namespace of files that is, by convention, the default working area of the principal and the repository of that principal's configuration. The association is established by the account database and protected by the permission system, and it persists across sessions. This persistence is what allows a person to accumulate scripts, notes, and configuration over years, and it is also what makes the later problem of recall acute: the home directory is a private institution whose only member may forget its contents.
The conventional division of the home directory into visible working material and hidden configuration, the latter marked by a leading period in file names, is an instance of classification by convention. Hidden files do not receive special protection; they are simply omitted from default listings. The convention is nevertheless significant, because it separates artifacts that the person produces from artifacts that the person's tools produce about the person's preferences, a distinction that becomes the topic of \Cref{ch:scripts}.
\chapter{Permissions as an Authorization Relation}\label{ch:permissions}
\section{The permission check}
Authorization in the traditional Unix model is determined by a short algorithm applied to a file's metadata. Each file has an owner, a group, and a mode word of which the lowest nine bits are three triples of read, write, and execute bits for the owner class, the group class, and all other users. When a process requests an operation on a file, the system selects exactly one class: the owner class if the process's effective user identifier equals the file's owner, otherwise the group class if the process belongs to the file's group, otherwise the other class. It then checks whether the selected class's bit for the requested operation is set. A privileged user, conventionally identified by the zero identifier, is exempt from most of these checks.
The selection of exactly one class is the feature of the algorithm that most often surprises newcomers. It means that permissions are not cumulative across classes: the owner is not granted whatever the group and others are granted. The following consequence illustrates this.
\begin{example}[An owner denied what others may do]\label{ex:ownerdenied}
Let a file have mode $007$ in octal notation, so that the owner and group classes have no permissions and the other class has read, write, and execute. A process whose effective user identifier equals the file's owner is assigned to the owner class and is denied every operation, while any unrelated user is permitted all of them. The owner may restore access by changing the mode, since the right to change the mode belongs to the owner independently of the mode bits.
\end{example}
The example exhibits a structural feature that is the seed of governance: the right to change the rules is distinct from the rights the rules confer. A model of authorization must therefore have two levels.
\begin{definition}[Authorization system with meta-permissions]\label{def:authsystem}
An \emph{authorization system} consists of a set $P$ of principals, a set $O$ of objects, a set $\mathsf{Op}$ of operations, a set $\Pi$ of policies, an authorization relation $\Gamma\subseteq P\times O\times\mathsf{Op}\times\Pi$ read as \emph{principal $p$ may perform $\mathit{op}$ on $o$ under policy $\pi$}, and a \emph{policy-update operation} $\mathsf{chpol}\in\mathsf{Op}$ whose effect on an object $o$ is to replace the policy governing $o$ by another. The system has \emph{meta-permissions} when the authorization of $\mathsf{chpol}$ is itself determined by $\Gamma$.
\end{definition}
In the traditional model, the authorization of $\mathsf{chpol}$ on a file is hard-wired to the owner (and to the privileged user), which means the system does not allow the policy-update right to be delegated except by transferring ownership. Access control lists in Windows and in POSIX extensions generalize this by making the right to change permissions an entry like any other, so that it may be granted to several principals or withheld from the owner. The distinction has a long reach: the history of repository systems is largely a history of increasingly fine meta-permissions, from the owner of a repository to organization roles, protected branches, and required reviews.
\section{Expressivity limits of mode bits}
\begin{proposition}[Class limitation]\label{prop:classlimit}
Under the traditional mode-bit model, for a fixed file and a fixed operation, the principals are partitioned into three classes determined by the file's owner and group (owner, other members of the group, everyone else), and the authorized set is a union of some of these classes, apart from the privileged user. Hence at most eight authorized sets are expressible for the operation on the file. In particular, a policy under which two principals in the same class are treated differently, or under which the authorized set is not a union of the three classes, cannot be expressed by mode bits alone, and a policy family that requires more than eight distinct authorized sets for one operation on one file cannot be expressed by mode bits on that file.
\Proved{}
\end{proposition}
\begin{proof}
The principals are partitioned by the algorithm into the owner class, the group class (principals other than the owner who belong to the file's group), and the remainder. The permitted set for each operation is the union of those classes whose bit for the operation is set. Every expressible authorized set is therefore determined by a choice of a subset of three classes, giving at most $2^3=8$ possibilities. Two principals in the same class satisfy exactly the same permission checks, so no policy that separates them is expressible, and a requirement for more than eight distinct authorized sets cannot be met. The statement concerns a fixed file and operation; the count of three classes is a property of the model and does not bound the number of principals.
\end{proof}
The practical remedy, creation of groups, moves complexity from the file to the group database. This remedy has costs that foreshadow later organizational problems: group membership must be maintained, the semantics of group names must be remembered, and a group created for one purpose is liable to be reused for another. Access control lists remove the bound at the cost of greater opacity: a file's effective policy is no longer visible in a single short string.
\section{Directories, traversal, and the semantics of write}
The permission bits take on distinctive meanings for directories. Read permission on a directory allows its entries to be listed; write permission allows entries to be added, removed, or renamed, provided search permission is also held; execute permission, called search permission, allows entries to be resolved by name when the name is already known. These meanings produce asymmetries that bear on discoverability. A directory with search permission but no read permission allows a person who already knows a file name to open the file but does not allow the person to find out what names exist. In effect, such a directory withholds referential persistence for agents who lack prior knowledge while preserving it for those who possess the name. The mechanism is a rudimentary form of capability: possession of the name is the authority.
A further device is the restricted deletion flag, commonly called the sticky bit, which on a shared directory restricts removal and renaming of an entry to the entry's owner, the directory's owner, and the privileged user. It exists because the write permission on a directory, ordinarily sufficient to delete any entry within it, would otherwise allow any participant in a shared scratch space to delete the files of every other. The sticky bit is thus a small governance rule: it distinguishes the right to contribute to a shared space from the right to alter the contributions of others, a distinction that reappears in every collaboration system.
\begin{principle}[Contribution is not control]\label{pr:contribcontrol}
A system that allows many principals to add to a shared space must distinguish, in its authorization relation, the right to add from the right to remove or alter what others have added. Systems that do not make this distinction either forbid shared spaces or expose them to destruction by any participant.
\Design{}
\end{principle}
\chapter{Paths, Files, and Classification}\label{ch:paths}
\section{Files, names, and the identity of content}
Early students of filesystems sometimes suppose that a file is its name. In Unix-like systems the file is an index node, a record carrying metadata and pointers to content, and the name is an entry in a directory that associates a string with an index node number. A single index node can have several names, which are called hard links, and removing a name does not remove the node until the last name is gone and no process holds it open. Renaming within a filesystem changes the directory entry and leaves the index node untouched. Symbolic links add another kind of association: a symbolic link is a small file whose content is a path, resolved each time it is followed, and which may therefore dangle if the target is moved or removed.
\begin{definition}[Filesystem as a labelled directed graph]\label{def:fs}
A \emph{filesystem} is a tuple $(N,D,\lambda,c)$ in which $N$ is a set of nodes, $D\subseteq N$ is the set of directory nodes, $\lambda:D\to(\Sigma^*\rightharpoonup N)$ assigns to each directory a partial map from names to nodes, and $c:N\setminus D\to\mathsf{Content}$ assigns content to non-directory nodes. A \emph{path} is a finite sequence of names, and the \emph{resolution} of a path $s_1/\dots/s_k$ from a root $r\in D$ is $\lambda(\cdots\lambda(\lambda(r)(s_1))(s_2)\cdots)(s_k)$ when every step is defined, and undefined otherwise.
\end{definition}
The definition models a filesystem without symbolic links: in it every non-directory node is content-bearing, and resolution is a recursive descent through directory maps. Symbolic links make resolution depend on the content of intermediate nodes, which are interpreted as paths to be resolved in turn, so that resolution may fail to terminate and a path may be valid at one moment and dangling at the next. The results below are stated for the restricted model unless a symbolic link is mentioned.
The definition makes plain that resolution is a partial function whose value depends on the whole chain of directory maps, so that a path is meaningful only relative to the state of every directory it traverses. A path is therefore a fragile reference. Moving any ancestor directory invalidates every path through it, though not the identity of the files beneath. This is the formal content of the old advice not to rely on locations, and it explains why content-addressed systems, in which the reference is derived from the content itself, behave differently under reorganization (\Cref{ch:git}).
\begin{figure}[t]
\centering
\begin{tikzpicture}[
d/.style={draw,rounded corners=2pt,minimum width=2.4cm,minimum height=0.8cm,font=\small},
f/.style={draw,minimum width=2.6cm,minimum height=0.9cm,align=center,font=\small},
ar/.style={-{Stealth[length=2.2mm]},thick}]
\node[d] (root) at (0,3) {root directory};
\node[d] (res) at (-3.3,1.5) {\texttt{results/}};
\node[d] (arc) at (3.3,1.5) {\texttt{archive/}};
\node[f] (n) at (0,-0.3) {node $n$\\content $c(n)$};
\draw[ar] (root) -- node[left,font=\footnotesize]{\texttt{results}} (res);
\draw[ar] (root) -- node[right,font=\footnotesize]{\texttt{archive}} (arc);
\draw[ar] (res) -- node[left,font=\footnotesize,pos=0.4]{\texttt{run1.csv}} (n);
\draw[ar] (arc) -- node[right,font=\footnotesize,pos=0.4]{\texttt{old.csv}} (n);
\end{tikzpicture}
\caption{A filesystem in the model of \Cref{def:fs} with one node reachable under two names, which is the situation created by a hard link. The paths \texttt{results/run1.csv} and \texttt{archive/old.csv} resolve to the same node $n$. Renaming either entry changes the resolution of paths through it (\Cref{prop:reorg}) and leaves $n$ and its content unchanged. The model contains no symbolic links.}
\label{fig:fsidentity}
\end{figure}
\begin{proposition}[Reorganization and references]\label{prop:reorg}
Let $\phi$ be a rename of a directory entry. (i) Resolution of every path that does not traverse the renamed entry is unchanged. (ii) Resolution of every path that traverses the renamed entry through the old name becomes undefined, unless a new entry with the old name is introduced. (iii) The node, its content, and the resolution of paths through any hard link not involving the renamed entry are unchanged.
\Proved{}
\end{proposition}
\begin{proof}
Each claim follows directly from \Cref{def:fs}: resolution depends only on the maps $\lambda(d)$ for directories $d$ along the path, and the rename changes exactly one of these maps at exactly one name.
\end{proof}
\section{Classification by hierarchy}
A directory hierarchy is a classification scheme with the restriction that each artifact receives one primary class. The restriction matters. Real artifacts have several attributes, and a hierarchy forces a choice of which attribute to use first. A scientific project may wish to organize its files by experiment, by data type, by date, or by the stage of analysis, and a tree can honor only one of these as the top-level partition. The remaining attributes are relegated to lower levels or to the file names, where they are accessible only by scanning.
\begin{example}[Two attributes, one tree]\label{ex:twoattr}
Let artifacts be indexed by pairs $(u,v)$ with $u\in\{1,\dots,A\}$ and $v\in\{1,\dots,B\}$, one artifact per pair. A tree whose top level partitions on $u$ and whose second level partitions on $v$ has $A$ directories each containing $B$ files. A searcher who knows $u$ opens one directory. A searcher who knows only $v$ must open directories until finding one with the sought entry, which takes on average $(A+1)/2$ directory openings. The tree ordered by $v$ first reverses the costs.
\end{example}
\begin{proposition}[Axis ordering]\label{prop:axis}
Suppose the searcher knows $u$ but not $v$ with probability $q$, and knows $v$ but not $u$ with probability $1-q$, and never both. The expected number of directory openings for the $u$-first tree is $q+(1-q)\tfrac{A+1}{2}$, and for the $v$-first tree is $q\tfrac{B+1}{2}+(1-q)$. The $u$-first tree is strictly better exactly when $(1-q)(A-1)<q(B-1)$.
\Proved{}
\end{proposition}
\begin{proof}
For the $u$-first tree, a searcher who knows $u$ opens exactly one directory. A searcher who knows only $v$ opens directories in some order until success; with the location uniformly distributed, the expected number of openings is $(A+1)/2$. The $v$-first case is symmetric with $A$ and $B$ exchanged and the roles of the probabilities swapped. Subtracting, the difference of costs ($u$-first minus $v$-first) is
\[
q\Bigl(1-\tfrac{B+1}{2}\Bigr)+(1-q)\Bigl(\tfrac{A+1}{2}-1\Bigr)=-\tfrac{q(B-1)}{2}+\tfrac{(1-q)(A-1)}{2},
\]
which is negative exactly when the stated inequality holds.
\end{proof}
The condition says that the first axis should be the one the searcher is more likely to know, weighted by the fan-out of the other axis, which accords with intuition: organize first by what future searchers will be able to say. The result also shows why the problem has no universal solution. The probabilities $q$ are properties of future searchers, which the person creating the hierarchy can estimate but not know. Systems that supplement hierarchies by tagging or by search indexes dissolve the choice of axis at the cost of building and maintaining a second structure, and that second structure is itself an artifact subject to the three kinds of persistence.
\section{Context contributed by the path}
The path contributes a substantial portion of the meaning of a file, and empirical studies of how people organize and recover files report that location serves as a reminder of the activity with which a file was associated \cite{barreau1995}. The name \texttt{results.csv} says almost nothing, but \texttt{percolation-screening/\allowbreak experiments/\allowbreak chokepoint/\allowbreak results.csv} says a good deal, and this meaning is not stored in the file. It is stored in the directory structure, and if the file is copied elsewhere the meaning is lost. This is an important example of information that is held in the \emph{relations} among artifacts and not in the artifacts themselves, and it recurs at every scale of the book. A commit's meaning depends on its position in a history; a claim's standing depends on its position in an argument; a repository's authority depends on the recognition it receives. In each case, a copy of the item without its relations is a different and poorer object.
\begin{principle}[Context may live outside the artifact]\label{pr:outside}
When context relevant to a class of operations is held in relations to other artifacts (directory position, links, history, citation), operations that move or copy the artifact without those relations do not preserve operational persistence for that class, even if the artifact's bytes are preserved exactly.
\Design{}
\end{principle}
Archival practice has long recognized this under the heading of original order, the doctrine that a collection's arrangement as received carries information that should not be altered casually. The mathematical content is that any reorganization is a map on the relational structure and that preservation questions must be asked of the map, not only of the objects.
\chapter{Naming as Prediction}\label{ch:naming}
\section{The retrieval loss of a naming policy}
A name is a message to a future searcher who cannot be consulted. The message must be composed under uncertainty about the searcher's vocabulary, knowledge, and intent. The problem has a natural formalization as the minimization of expected retrieval loss.
\begin{definition}[Naming policy and retrieval loss]\label{def:namingpolicy}
Let $X$ be a finite set of artifacts, $\Lambda$ a set of labels, and $Q$ a set of queries. A \emph{naming policy} is a map $N:X\to\Lambda$. A \emph{retrieval procedure} for $N$ is a map $\operatorname{Retrieve}(\cdot,N):Q\to\Pow(X)$ returning a set of candidates. Given a joint distribution on pairs $(X,Q)$ of target artifact and query, and a loss function $\ell(x,S)$ that penalizes failure to include $x$ in the returned candidate set $S$ and the size of $S$, the \emph{expected retrieval loss} is
\[
\mathcal{L}(N)=\E_{(X,Q)}\bigl[\ell\bigl(X,\operatorname{Retrieve}(Q,N)\bigr)\bigr].
\]
\end{definition}
The loss penalizes two kinds of error. Retrieving the wrong artifact, or failing to retrieve any, is the obvious kind. Retrieving a large set of candidates among which the right one must be identified at cost is the other, and in practice it is often the dominant cost, since the searcher's time is consumed by sifting. A good name does not merely allow the artifact to be found; it allows it to be recognized as the artifact being sought, among its neighbors.
\section{Bounds on label-only retrieval}
The most basic limit on naming concerns the size of the label space. A name carries information, and a naming policy that uses few distinct labels cannot distinguish many artifacts.
\begin{proposition}[Label capacity]\label{prop:labelcap}
Let $X$ have $n$ elements, let the target be drawn uniformly, and let $N:X\to\Lambda$ be a naming policy that uses exactly $L$ distinct labels. A searcher who knows the label of the target and returns a single guess succeeds with probability exactly $L/n$, whatever the sizes of the classes sharing a label. In particular no policy with at most $L$ labels in use supports label-only retrieval with success probability above $L/n$.
\Proved{}
\end{proposition}
\begin{proof}
Given the label, the searcher's best single guess is any element of the class carrying that label; it is correct with probability $1/|C_\ell|$ conditional on the label $\ell$, which occurs with probability $|C_\ell|/n$. The unconditional success probability is $\sum_\ell \frac{|C_\ell|}{n}\cdot\frac{1}{|C_\ell|}=L/n$, where the sum is over the $L$ labels in use. This holds for any partition into classes, equal or not, so the success probability is the number of distinct labels over $n$, and it cannot exceed $L/n$ for a policy with at most $L$ labels in use.
\end{proof}
The relevant quantity is the number of labels actually in use and not the size of the label alphabet. A policy that gives every artifact a unique label, so that $L=n$, supports perfect label-only retrieval, but only for searchers who know the unique label. Unique labels are cheap to generate (a hash will do) and useless to a searcher who cannot reconstruct them. The value of a name lies in its reconstructibility from what the searcher is likely to know, which is why descriptive names are used in preference to arbitrary identifiers, and why arbitrary identifiers are used in addition to descriptive names when exactness is needed.
\begin{proposition}[Names must be reconstructible]\label{cor:reconstruct}
For a searcher with knowledge state $\kappa$ and a naming policy $N$, let $E$ be the event that the searcher derives $N(x)$ from $\kappa$, and let $\rho=\Pr[E]$. Assume (a) the sequential model: retrieval succeeds only if the label is first derived, so that the success event $S$ satisfies $S\subseteq E$; and (b) given $E$, the searcher's success is that of a searcher who knows the label, so that $\Pr[S\mid E]\le L/n$ by \Cref{prop:labelcap}. Then $\Pr[S]\le\rho\,L/n$.
\Proved{}
\end{proposition}
\begin{proof}
By (a), $\Pr[S]=\Pr[S\cap E]=\Pr[E]\Pr[S\mid E]$, and by (b) the second factor is at most $L/n$.
\end{proof}
Both assumptions matter. Without (a), a searcher who fails to derive the label may still succeed by browsing or by search on content, and the bound fails. Without (b), derivation of the label may be correlated with the target in a way that favors the searcher, as when the searcher derives the label because the target is a typical member of its class. The proposition says that, within the sequential model, a naming policy cannot do better than balance label capacity against reconstructibility; whether real searchers follow the sequential model is an empirical question.
\section{Conventions as constraints on the search space}
If the future searcher cannot know the writer's naming habits, shared conventions can substitute for knowledge. A convention is a commitment, observed by many writers, to derive labels from attributes by a stated rule. A searcher who knows the rule and the attributes can reconstruct the label without remembering it.
\begin{proposition}[Value of a convention]\label{prop:convention}
Let attributes $\alpha(x)\in\mathcal{A}$ be injective on $X$ and let a convention fix a deterministic map $g:\mathcal{A}\to\Lambda$ that is injective, with $N(x)=g(\alpha(x))$. A searcher who knows $\alpha(x)$ and $g$ retrieves $x$ with probability one. A searcher who knows only a proper subset of the attributes succeeds with probability equal to the reciprocal of the number of artifacts consistent with the known attributes.
\Proved{}
\end{proposition}
\begin{proof}
With full knowledge, the label $g(\alpha(x))$ is computable and, by injectivity, identifies $x$. With partial knowledge, the consistent artifacts form a set $S$; if the target is uniform within $S$ and the searcher guesses one element, the success probability is $1/|S|$.
\end{proof}
The proposition shows what a convention does and what it does not do. It converts memory of a label into computation of a label, which is a gain whenever the attributes are more memorable than the label. It does nothing for a searcher who knows too few of the attributes. For this reason the design of conventions is a matter of choosing which attributes to encode, and the choice has the same structure as the choice of tree axes in \Cref{prop:axis}.
\section{Names in code, in commits, and in headings}
The same analysis applies, with changes of detail, to function names, variable names, commit messages, section headings, and file names. A function name is a retrieval key for a reader who is scanning a codebase for the procedure that does a thing; a good name encodes the operation and its domain. A commit message is a retrieval key for a reader who is searching history for the change that introduced a behavior. A heading is a retrieval key for a reader skimming a document for the part that answers a question.
Names also embody a theory of how the artifact will be described later. A name chosen from the writer's present vocabulary encodes the writer's present concerns; a name chosen from the vocabulary of the problem domain encodes concerns that outlive any particular author. Naming from the domain is accordingly more durable, but also more demanding, since it requires the writer to know the domain's vocabulary. Naming from the implementation is less durable, because implementations change while the problem endures. The familiar advice to name things for what they are and not for how they are done is a heuristic for increasing the reconstruction probability of \Cref{cor:reconstruct} over long horizons.
\begin{remark}[Names and the stability of reference]
A name that must remain stable to support external references, such as a published function name in a library, is an interface, and changing it is an act with consequences for every dependent. Part~\ref{part:history} shows how package ecosystems formalized this through version numbering conventions, and Part~\ref{part:math} treats name stability as a component of institutional continuity.
\end{remark}
\part{The Discipline of Reuse}\label{part:reuse}
\chapter{Scripts, Templates, and Portable Configuration}\label{ch:scripts}
\section{The script as externalized procedure}
A script is a procedure that has been written down so that it need not be performed from memory. Its first function is labor saving: a sequence of commands that would be typed repeatedly is typed once. Its second function, which is more important for the argument of this book, is that it records a procedure in a form that can be inspected. A script that renames a thousand files according to a rule documents the rule more exactly than any prose description could, and it does so in a notation whose meaning is fixed by an interpreter. The record is executable, and so it is checkable by running it. This dual character, being both a tool and a statement of method, is why scripts occupy a central place in the passage from personal practice to reproducible science.
A script nevertheless inherits all the persistence problems of \Cref{ch:persistence}. It may exist (physical persistence) while its location is forgotten (referential persistence); it may be found while the assumptions about the environment in which it ran have been lost (operational persistence). A script that reads from a hard-coded path, depends on an environment variable set in a long-closed shell session, or invokes a tool that has changed its option syntax may be inspectable and not executable. The common cause is that the script's text records the \emph{operations} while the \emph{conditions} under which the operations were valid are held elsewhere.
\begin{definition}[Implicit and explicit preconditions]\label{def:precond}
For a script $s$ and an environment $e$, let $\mathrm{Pre}(s)$ be the set of conditions on $e$ under which $s$ executes as intended. The \emph{explicit preconditions} $\mathrm{Pre}_{\mathrm{exp}}(s)\subseteq\mathrm{Pre}(s)$ are those recorded in the script or in artifacts bundled with it, and the \emph{implicit preconditions} are the remainder. The script is \emph{self-describing} when $\mathrm{Pre}_{\mathrm{exp}}(s)=\mathrm{Pre}(s)$.
\end{definition}
Self-description is an ideal, seldom attained, but it is the measure against which practices can be compared. Checks at the head of a script that verify the presence of required tools and exit with an informative message convert implicit preconditions into explicit ones; declarations of required versions do the same; and strict modes in which undefined variables cause errors turn some implicit preconditions into detectable failures.
\section{Idempotence and the safe rerun}
A procedure intended for repeated use should behave well when run more than once, since a person who is unsure whether it has been run is likely to run it again. The mathematical notion is idempotence.
\begin{definition}[Idempotent operation]\label{def:idempotent}
An operation $f$ on states of an environment is \emph{idempotent} if $f\circ f=f$. A family of operations $\{f_i\}$ is \emph{commuting} if $f_i\circ f_j=f_j\circ f_i$ for all $i,j$.
\end{definition}
\begin{proposition}[Composition of idempotent operations]\label{prop:idemp}
(i) If $f$ and $g$ are idempotent and commute, then $f\circ g$ is idempotent. (ii) Without commutation, the composition of two idempotent operations need not be idempotent. (iii) If $f$ is idempotent, then for every state $e$ the state $f(e)$ is a fixed point of $f$, and iterating $f$ never changes the outcome after the first application.
\Proved{}
\end{proposition}
\begin{proof}
(i) $(fg)(fg)=f(gf)g=f(fg)g=(ff)(gg)=fg$ using commutation and idempotence. (iii) is the identity $f(f(e))=f(e)$. For (ii), take states $\{0,1,2\}$ with $f$ defined by $f(0)=1$, $f(1)=1$, $f(2)=2$, and $g$ by $g(0)=0$, $g(1)=2$, $g(2)=2$. Both are idempotent. Then $fg(0)=f(0)=1$, $fg(1)=f(2)=2$, so $(fg)(fg)(0)=fg(1)=2\ne fg(0)=1$.
\end{proof}
The failure of idempotence under non-commuting composition explains why setup scripts that are composed of individually safe steps can still be unsafe to rerun: the order of steps matters, and the second run starts from a state that the first run altered. The practical discipline is to make each step a check followed by an action, so that a step that has already taken effect becomes a no-op, and to order steps so that later steps do not invalidate the checks of earlier ones.
\section{Dotfiles and the portable environment}
Configuration of a working environment accumulates in files that tools read at startup: shell initialization, editor settings, version control preferences, terminal behavior. In Unix-like systems these are conventionally hidden files in the home directory, and collectively they are called dotfiles. They constitute the personal institution of a user in an unusually literal sense: they record that user's standing decisions about how work is to be done.
Dotfiles are among the first artifacts a user places under version control, because loss of them is felt immediately and because their small size and textual form make them well suited to version control. The practice of keeping dotfiles in a repository and installing them on new machines by a bootstrap script is, in the vocabulary of this book, an environment-reconstruction procedure. Its quality is judged by how fully it restores the environment from the repository alone.
\begin{definition}[Reconstruction map]\label{def:reconstruct}
Let $\mathsf{Rep}$ be the set of states of a configuration repository and $\mathsf{Env}$ the set of environment states. A \emph{reconstruction map} is a function $\beta:\mathsf{Rep}\times\mathsf{Env}_0\to\mathsf{Env}$ that applies the repository's bootstrap procedure to a base environment $e_0\in\mathsf{Env}_0$. The repository is \emph{sufficient} for a target environment $e^*$ relative to a class $\mathsf{Env}_0$ of base environments if $\beta(r,e_0)\simeq_K e^*$ for all $e_0\in\mathsf{Env}_0$, where $\simeq_K$ is observational equivalence for an operation class $K$: for a family of observations $\mathrm{Obs}_K(e)$ (the outputs and visible effects of each operation of $K$ on each input in a stated test family), $e\simeq_K e'$ holds when $\mathrm{Obs}_K(e)=\mathrm{Obs}_K(e')$. Exact equality $e=e^*$ implies $e\simeq_K e^*$ for every $K$ and is strictly stronger; two environments with different installed but unused packages may be equivalent for $K$ and unequal.
\end{definition}
The base class $\mathsf{Env}_0$ is the quantity that matters. A bootstrap script that works from a freshly installed system of a particular distribution, with network access, is sufficient for a narrow class; a script that also works when a package index has changed, a tool has been removed, or a different operating system is in use is sufficient for a wide one. Preference for default configurations, with as little customization as the work allows, is a strategy that widens the class: the less the environment departs from defaults, the more machines already satisfy the target, and the fewer steps the bootstrap needs to carry. This is a kind of conservatism with a precise justification, namely that every deviation from defaults is an item of context that must be preserved and that a future environment may lack.
\section{Templates and the reuse of structure}
A template is a script's cousin for documents and projects: a pre-built structure with places to fill in. Templates carry conventions, so that a new project begins with a README, a license file, a layout, and a place for tests. They are the practical means by which conventions propagate. A template does for the structure of an artifact what a naming convention does for its label (\Cref{prop:convention}): it replaces a decision to be remembered with a decision to be recognized.
The risk of templates is cargo-cult adoption, in which the structure is retained while its function is forgotten. A project may carry a contributing guide that nobody maintains and a test directory that tests nothing. The distinction between structure and function is again the distinction between physical or referential persistence and operational persistence: the file exists and can be found, but the practice it was meant to support has lapsed. The discipline of reuse thus consists not in the accumulation of templates but in the continual checking that the practices they encode are still operative.
\chapter{Documentation as Communication with an Absent Agent}\label{ch:documentation}
\section{The manual page tradition}
The manual page is one of the most successful documentation genres in computing. Its fixed sections, which in the conventional layout include a name line, a synopsis, a description, a list of options, examples, related commands, and notes on known defects, give the reader a predictable route to the information needed: what the command is called and does, how it is invoked, what each option means, and where to look next. The predictability is the point. A reader encountering an unfamiliar command can navigate its manual page without having to read it, because the structure of every page is the same.
The structure of the genre embodies a theory of what a user of a tool needs to know. The synopsis answers \emph{how do I call this}; the description answers \emph{what does it do}; the options answer \emph{what can I vary}; the examples answer \emph{what does typical use look like}; the related-commands section answers \emph{what else is relevant}. These are different kinds of information, and an undifferentiated essay that mixes them forces the reader to extract each from a narrative. In the vocabulary of \Cref{def:context}, the manual page is a partitioning of context items by type, so that a reader seeking a particular type can find it without reading the rest.
\section{Contracts and what the code does not say}
Function-level documentation conventions, including documentation comments with sections for arguments, return values, and exceptions, serve a similar role at smaller scale. The strongest form is the specification of a procedure as a contract: a statement of what the caller must ensure (the precondition), what the procedure guarantees on return (the postcondition), and what remains unchanged (the frame). In Hoare's notation \cite{hoare1969}, a correctness statement has the form $\{P\}\,C\,\{Q\}$, meaning that if the precondition $P$ holds before the command $C$ is executed and $C$ terminates, then the postcondition $Q$ holds afterward.
The importance of contracts for the present argument lies in what they leave out. A contract describes an interface and says nothing about how the interface is realized. This is valuable for use, since a caller needs only the interface, and troublesome for modification, since a maintainer needs to know why the implementation takes the form it does. Two different implementations may satisfy the same contract while differing in running time, memory use, numerical stability, ordering of side effects, and behavior outside the specified domain, and a modification that preserves the contract may destroy properties the contract never mentioned.
\begin{proposition}[Contracts underdetermine safe modification]\label{prop:contract}
Let $C_1$ and $C_2$ be two programs satisfying the same contract $\{P\}\,\cdot\,\{Q\}$ and differing in some property $\Phi$ not implied by the contract (that is, $C_1$ has $\Phi$ and $C_2$ does not, and neither $P$ nor $Q$ entails $\Phi$). Then replacing $C_1$ by $C_2$ preserves all properties entailed by the contract and may fail to preserve $\Phi$. Consequently, the contract alone is not a sufficient context for the operation class \emph{modify while preserving $\Phi$}.
\Proved{}
\end{proposition}
\begin{proof}
Every property entailed by the contract holds for any program satisfying it, hence holds for $C_2$ if it held for $C_1$. By hypothesis $\Phi$ holds for $C_1$ and not $C_2$, so the replacement does not preserve $\Phi$. A context that does not mention $\Phi$ cannot distinguish the safe replacement from the unsafe one, so it is not sufficient for a class of operations whose correctness criterion includes $\Phi$.
\end{proof}
This is the formal form of the observation that documentation must record the \emph{why} as well as the \emph{what}. The reasons an implementation was chosen are the properties $\Phi$ that the contract omits: that an algorithm was selected for numerical stability, that a loop order was chosen for cache locality, that a data structure was kept because an external consumer depends on its ordering. These are rationale items in the information universe $I$, and they are the items most easily lost, since they are not needed to make the code run.
\section{History as documentation}
Version control adds a second documentary channel: the record of changes. A commit consists of a snapshot or difference together with a message, and the message is the place for explaining why the change was made. But the difference itself does not determine the explanation.
\begin{proposition}[Intent is not a function of the change]\label{prop:intent}
Let $\mathrm{Intent}$ denote the set of intentions with which a change may be made, and let $\delta$ be a textual difference between two versions. There exist differences $\delta$ and distinct intentions $\iota_1\neq\iota_2$ such that both are consistent with $\delta$. Hence no function from differences to intentions is correct in general.
\Proved{}
\end{proposition}
\begin{proof}
Consider the difference that replaces the constant $0.05$ by $0.01$ in a threshold. One author may intend to tighten the statistical significance level, another to correct a transcription error from a source that gives $0.01$, a third to tune a parameter against a validation set. All three produce the identical difference. A function from differences to intentions would assign a single value to this difference, hence be wrong for at least two of the three authors.
\end{proof}
A commit message that says \emph{change threshold} restates the difference. A commit message that says \emph{use the significance level stated in the protocol; the previous value was a transcription error} records the intention, and the intention is exactly what the difference cannot supply. This is the reason that disciplined projects ask for descriptive messages and that tools which generate messages automatically from differences are of limited documentary value: they add no information beyond what the difference contained.
\section{Documentation decay}
Documentation can be wrong. A comment that describes code as it was before a change is worse than no comment, because it misleads a reader who trusts it. The risk is greatest for documentation that is physically separate from the thing described, since there is no mechanical connection forcing the two to change together. Remedies fall on a spectrum. At one end, documentation embedded in code, as comments or documentation strings, is edited when the code is edited, with some probability. Further along, documentation that is executable, in the form of examples that are run as tests, fails loudly when it diverges from the behavior it describes. At the far end, the specification and the implementation are derived from a single source, so that divergence is impossible by construction.
\begin{definition}[Documentary coupling]\label{def:coupling}
The \emph{coupling} of a documentation item $d$ to an artifact $x$ is the probability that a change to $x$ affecting the content of $d$ is accompanied by a corresponding change to $d$. Documentation is \emph{mechanically coupled} when coupling is one by construction (for example, generated from the artifact), \emph{checked} when divergence triggers a failure signal (for example, a doctest), and \emph{free} otherwise.
\end{definition}
The three levels have increasing reliability and increasing cost in flexibility. Mechanically coupled documentation can only say what the artifact determines, which excludes rationale; checked documentation can say more, but only things that tests can verify; free documentation can say anything and is trusted only as far as its maintainers are diligent. A project that wishes its documentation to survive long horizons will use all three, assigning each kind of information to the level that suits it: signatures and types to the mechanical level, usage examples to the checked level, and rationale to the free level, with the understanding that the free level is the most fragile and the most valuable.
\chapter{Dependencies and Environments}\label{ch:dependencies}
\section{The hidden context of imported code}
An artifact that imports another artifact has acquired a dependency, and the dependency is part of the context needed for any operation on the first. A script that uses a numerical library cannot run without the library, and the behavior of the script depends on the library's version, on the versions of the libraries the library itself uses, and on the system on which they are all installed. The dependency graph of a nontrivial program is large, deep, and mostly unexamined by its author. The result is a distinctive failure mode: a program that worked for years stops working, not because it changed, but because something it depends on, directly or transitively, changed beneath it.
\begin{definition}[Dependency graph and closure]\label{def:depgraph}
A \emph{dependency graph} is a directed graph $G=(V,E)$ whose vertices are artifacts together with version identifiers and whose edges $u\to v$ record that $u$ requires $v$. For a set $S\subseteq V$ of artifacts, the \emph{closure} $\Cl(S)$ is the set of vertices reachable from $S$. A deployment is \emph{closed} if every artifact that it uses at run time belongs to $\Cl(S)$ for the declared set $S$ of direct requirements. The \emph{undeclared dependencies} of a run are the artifacts it reads that lie outside $\Cl(S)$.
\end{definition}
The distinction between declared and actual dependencies is critical. A script may import a module that happens to be installed on the author's machine through an unrelated project; the dependency is real, since the script fails without it, and undeclared. Undeclared dependencies are among the most common reasons why work that functions on its author's machine fails elsewhere.
\section{Version constraints and resolution}
Dependencies are rarely stated as exact versions. Most package managers allow ranges, such as any version at least a given number but below the next major release. The practice trades precision for flexibility: a range allows the ecosystem to supply bug fixes without requiring each consumer to update its declarations. The cost is that the meaning of a declaration depends on the state of the registry at the time of resolution.
\begin{definition}[Resolution function]\label{def:resolution}
Let $\mathsf{Reg}_\tau$ be the state of a package registry at time $\tau$, and let $\mathsf{Req}$ be a set of requirements with version constraints. A \emph{resolution procedure} is a function $\varrho$ that maps $(\mathsf{Reg}_\tau,\mathsf{Req})$ to a set of pinned artifacts satisfying the constraints, or to failure.
\end{definition}
\begin{proposition}[Resolution depends on time]\label{prop:restime}
In general, $\varrho(\mathsf{Reg}_\tau,\mathsf{Req})\neq\varrho(\mathsf{Reg}_{\tau'},\mathsf{Req})$ for $\tau\neq\tau'$. A pinned specification that names each artifact by content hash is invariant: it resolves to the same artifacts at every time at which those artifacts remain obtainable.
\Proved{}
\end{proposition}
\begin{proof}
For the first claim, let $\mathsf{Req}$ require a library at least version $1.0$. If at time $\tau$ the registry's latest release is $1.0$ and at $\tau'$ it is $1.1$, a procedure that selects the latest satisfying version returns different results. For the second, a content hash determines the artifact (under collision resistance), so the specification does not depend on registry state, only on the availability of an artifact with that hash.
\end{proof}
The proposition is the formal content of the practice of lock files, which record the resolved versions, and, in stronger form, of hash-pinned requirements. A lock file converts a resolution that depends on time into one that does not, at the price of freezing the ecosystem's improvements until the lock is deliberately refreshed.
\section{The computational difficulty of resolution}
The difficulty of dependency resolution is not merely organizational. When versions can conflict, so that two packages cannot both be installed, the problem of finding a consistent installable set is computationally hard. The hardness is a classical result in the literature on package-management systems.
\begin{theorem}[Hardness of installability]\label{thm:installability}
Deciding whether a given package can be installed from a repository in which packages declare dependencies as conjunctions of disjunctions of versioned packages, together with pairwise conflicts, is NP-complete.
\Proved{}
\end{theorem}
\begin{proof}
Membership in NP holds because a proposed installation set can be checked for dependency satisfaction and absence of conflicts in polynomial time. For hardness, reduce from 3-SAT. Given a formula with variables $x_1,\dots,x_k$ and clauses $C_1,\dots,C_n$, introduce for each variable a package pair $x_i^{\top}$ and $x_i^{\bot}$ declared in conflict, so that at most one of them is installed. For each clause introduce a package $c_j$ whose dependency is the disjunction of the packages corresponding to its literals. Introduce a root package that depends on all variable choices (a disjunction $x_i^{\top}\lor x_i^{\bot}$ for each $i$) and on all clause packages. The root is installable iff there is an assignment (choice of one package per variable) satisfying every clause.
\end{proof}
The result is attributed, in various forms, to work on package-based distributions and on dependency solving as a separate concern (see \cite{mancinelli2006, abate2012}). It explains why modern package managers incorporate satisfiability solvers, and why the existence of a compatible set of versions is a different matter from its discoverability by naive procedures. It does not imply that practical instances are hard, since real dependency graphs have structure that SAT solvers exploit, but it does set the baseline: a theory of reproducible environments cannot assume that a consistent dependency assignment can be found cheaply by inspection, or that, once found, it is unique.
\section{Environments as artifacts}
Because the behavior of a program depends on its environment, the environment itself must be treated as an artifact if the program's behavior is to be reproduced. Environment descriptions can be of several kinds: a list of installed packages with versions; a container image that bundles the user-space filesystem; a declarative description from which an environment is built; or a complete system image. They differ in how much of the environment they capture, in how much they depend on external registries at rebuild time, and in how readable they are. The container image is the most complete and the least inspectable; the declarative description is the most readable and the most dependent on external state.
\begin{proposition}[Completeness-inspectability tradeoff]\label{prop:envtradeoff}
Among environment representations, one that stores the complete binary content of the environment is independent of external registries but supports inspection only through additional tooling, while one that stores only requirements is directly inspectable but is subject to the time dependence of \Cref{prop:restime}. Hybrid representations that store a declarative description together with content hashes of the resolved artifacts recover time independence for those artifacts that remain obtainable while preserving inspectability.
\Design{}
\end{proposition}
The design argument is simple and its force is practical. A representation that records both the intended requirements and the resolved artifacts supports two classes of operations: reproduction of the original environment where possible, and informed reconstruction where it is not. The second class is the one that matters when an artifact has been withdrawn from a registry, since the declarative layer says what was needed even when the binary layer cannot be satisfied.
\chapter{Conventions, Noise, and the Economy of Reading}\label{ch:conventions}
\section{More context can mean less usability}
\Cref{def:context} assumed that sufficiency is monotone: adding information to a context never harms. That assumption is false in practice, because readers have finite budgets. A repository with ten thousand undifferentiated files and a one-line description is not better documented than one with a short README, even though the first contains strictly more information. The additional information is noise, in the sense that its presence raises the cost of finding what is needed.
\begin{definition}[Budgeted reading]\label{def:budgetreading}
Let a preserved context be a finite sequence $m=(i_1,\dots,i_k)$ of items, each with reading cost $\gamma(i_j)>0$, and let a reader have budget $\beta$. The reader processes the items in order until the budget is exhausted. A class of operations $K$ requires a set $\mathrm{Need}(K)\subseteq I$ of items; the reader \emph{succeeds} if every item of $\mathrm{Need}(K)$ is processed within the budget.
\end{definition}
\begin{proposition}[Noise can destroy sufficiency]\label{prop:noise}
Under budgeted reading, adding items to a context can cause a reader who previously succeeded to fail. In particular, if irrelevant items are placed before a needed item, then for a sufficiently large total cost of irrelevant items, a budget that sufficed before the addition no longer suffices.
\Proved{}
\end{proposition}
\begin{proof}
Let $m=(r)$ with $r$ needed and $\gamma(r)=1$, and let $\beta=1$. The reader succeeds. Let $m'=(n_1,\dots,n_k,r)$ with irrelevant items of unit cost. The reader exhausts the budget after processing $n_1$ and fails for any $k\ge1$.
\end{proof}
The monotone idealization is thus recovered only when the reader has an effective way of skipping irrelevant items, which is to say, when the context is structured so that relevant items can be located without processing the rest. Indexes, tables of contents, section headings, and naming conventions are mechanisms for providing this.
\section{Ordering by expected relevance}
If the order of items matters, the question arises of which order is best. In the simplest case, in which a reader needs exactly one item, drawn from a known distribution, and processes items in sequence, the optimal ordering has a classical form.
\begin{proposition}[Optimal ordering for single-item need]\label{prop:ordering}
Let the needed item be item $i$ with probability $w_i$, with unit reading costs and budget $B$ (an integer). A reader processing items in the order $\pi$ succeeds with probability $\sum_{j\le B}w_{\pi(j)}$, and this is maximized by ordering items by nonincreasing $w_i$. The maximum equals the sum of the $B$ largest weights.
\Proved{}
\end{proposition}
\begin{proof}
Success occurs iff the needed item is among the first $B$ in the order, which has probability equal to the sum of the weights of those items. The sum of any $B$ distinct weights is at most the sum of the $B$ largest, and ordering by nonincreasing weight places the $B$ largest first.
\end{proof}
The result justifies the near-universal practice of putting a summary first. A README is a convention that places the most frequently needed items at a standard position. Its authority comes from its being the first thing a reader opens, and its usefulness from the high weight of orienting information in the distribution of needs. Conventions of this sort effectively fix the prior $w$ across a community, so that writers need not estimate it separately for each artifact.
\section{Standard files as institutional organs}
Repositories of software have developed a small set of conventional files whose names and places are recognized by readers and by tools: a README that orients the reader, a license that states the terms of reuse, a changelog that records notable changes between releases, a contributing guide that states how outsiders may propose changes, and a code of conduct that states expectations of participants. Each answers a question that a prospective user or contributor will ask, and each does so at a predictable place. Taken together they are the organs by which a repository communicates with newcomers.
From the standpoint of the formalism, each such file is a context item of a distinct type, placed at a conventional position to reduce search cost. The license file deserves particular note: it is a context item without which a large class of operations, including copying, modification, and redistribution, is not legally permitted, regardless of whether it is technically possible. Technical possibility and legal permission are independent, and the license is the artifact that carries the latter. An archive of code without licenses is physically and referentially persistent and, for many classes of operations, not operationally persistent in the legal sense.
\section{Closing the first three parts}
The preceding chapters have established a vocabulary: three kinds of persistence, the recovery model, the hierarchy of continuation classes with minimal sufficient contexts, the structure of namespaces and permissions, the economics of naming, the layering of documentation, and the dependence of artifacts on environments. The claims made so far are modest, and several are elementary, but they have the useful property of being stated sharply enough to be applied to institutions. The next part turns from the formal vocabulary to its historical development, tracing how the problems identified here were met, imperfectly, by successive generations of tools, until they became the problems of repository infrastructure.
\part{The History of Software Continuity}\label{part:history}
\chapter{Software Before Persistent Distribution}\label{ch:before}
\section{Programs as physical objects}
The earliest programs were configurations of hardware. Plugboards, switches, and punched media held them, and a program could be transferred only by moving or reproducing the medium. Stored-program machines changed the representation but not at first the economics: programs were written for a specific machine, held on cards, paper tape, or magnetic tape, and distributed within user communities by physical exchange. Cooperative user groups for early commercial machines circulated program libraries on media, and the practice of sharing source was ordinary because the programs were written for particular installations by the people who operated them. Source and executable were not separated in the way that later commercial practice would separate them: the thing that was shared was typically what could be read.
Successive media improved density, cost, and ease of copying. Magnetic tape allowed large collections to be moved; floppy disks, introduced in the early 1970s and refined through several formats, put a duplicable medium within reach of individuals; cassette tape served early hobbyist machines. The consequence for continuity was ambivalent. Cheaper, more durable media increased the number of copies in circulation and the probability that some copy survived, and at the same time they multiplied versions, since each copying event was an opportunity for modification, corruption, and loss of the information about origin.
\section{Networks of exchange}
The next layer was electronic. Bulletin board systems, of which the best known early example was the computerized bulletin board begun in Chicago in 1978, allowed users to dial a machine and download programs. File transfer protocols, whose early specifications date to the first years of the ARPANET and whose long-lived standard was published in 1985, supported archives of software on networked hosts. Distributed discussion systems carried source code posted to special groups, some moderated so that postings were collected as complete, buildable packages. Compilation archives, shareware collections, and later commercial and noncommercial software repositories on optical discs extended the pattern. The network made a program discoverable, in the sense that a person who knew where to look could obtain it, but it did little for provenance. A file named for a program on an archive host might be the latest version, an old version, a modified version, or an unrelated file.
The commercial counterpart was the separation of the executable from the source. Software sold as a product was typically sold as an executable, with source retained by the vendor. The user possessed a thing that could be run and could not be read in the sense that matters for maintenance. This distinction is crucial for the theory of continuity, because the map from source to executable is many-to-one.
\begin{proposition}[Executables underdetermine sources]\label{prop:compile}
Let $c:\mathsf{Src}\to\mathsf{Exe}$ be a compilation map. If $c$ is not injective, there is no function $d:\mathsf{Exe}\to\mathsf{Src}$ with $d\circ c=\mathrm{id}$. Compilation maps of practical compilers are not injective: they discard comments, identifier names (in stripped binaries), formatting, and distinctions erased by optimization.
\Proved{}
\end{proposition}
\begin{proof}
Suppose $c(s_1)=c(s_2)$ with $s_1\ne s_2$. A left inverse $d$ would give $s_1=d(c(s_1))=d(c(s_2))=s_2$, a contradiction. Two sources differing only in a comment compile to the same executable under any compiler that discards comments, so $c$ is not injective.
\end{proof}
The proposition has a historical corollary. A collection of executables is a collection of artifacts for which the highest operation class available to an ordinary user is execution (\Cref{def:opclasses}), and perhaps inspection of a representation that is not meant for human reading. Safe modification and reproduction require the source and the build context, which were not distributed. Decompilation can recover a program of equivalent behavior in some cases, but it recovers neither the author's identifiers nor the comments nor the rationale, which is to say, nearly the entire contextual layer that matters for continuation.
\section{The problem of identification}
When software circulates through informal channels, the question of what a given file is becomes nontrivial. Identification under incomplete provenance is the problem of deciding, for a given artifact and a given claim about its identity, whether the claim is true.
\begin{definition}[Provenance record]\label{def:provrecord}
A \emph{provenance record} for an artifact $x$ is a tuple $\pi(x)=(\mathrm{prod},\tau,\mathrm{src},\mathrm{der})$ recording the producing agent, the time of production, the artifacts from which $x$ was derived, and the derivation procedure. A record is \emph{incomplete} if one or more components are unknown or unverifiable.
\end{definition}
An identification policy decides whether two artifacts or an artifact and a description are the same. The simplest policy identifies by name. Name-based identification fails in two opposite ways: the same artifact may be known under several names, and different artifacts may share a name.
\begin{proposition}[Names are neither sound nor complete]\label{prop:namesidentify}
Let $\mathsf{Univ}$ be a universe of artifacts that allows (a) renaming, in which one artifact acquires an additional name, and (b) name reuse, in which one name is applied to different artifacts at different times or places. Then no identification policy based on name alone is both sound (never identifying distinct artifacts) and complete (always identifying copies of the same artifact).
\Proved{}
\end{proposition}
\begin{proof}
By (b) there are distinct artifacts $x\neq y$ bearing the same name $n$; a policy that is complete with respect to names identifies $x$ and $y$, which violates soundness. By (a) there is an artifact $z$ with names $n_1\neq n_2$; a policy that is sound for names, identifying only artifacts with the same name, fails to identify the copy under $n_1$ with the copy under $n_2$, which violates completeness. Both properties cannot hold.
\end{proof}
The way out, which becomes decisive later, is to identify by content. A checksum or cryptographic hash identifies an artifact by a function of its bytes, so that identical content gives identical identifiers regardless of name, and differing content gives different identifiers up to the collision resistance of the function. Content identification solves the identity problem for byte-level equality at the cost of making any change, however trivial, a change of identity. It says nothing about authorship, purpose, or derivation, which are the rest of provenance.
\chapter{The Dependency and Version Problem}\label{ch:depversion}
\section{Shared libraries and the single-slot namespace}
As software grew in size, programs came to be assembled from components, and economy of storage and update suggested that common components be shared. A shared library is installed once and used by many programs; fixing a defect in it fixes all programs that use it. The arrangement has a cost, which became widely known in the era of dynamic link libraries on desktop systems: a program is written against a version of a library, and installing a program may replace the shared copy with another version that other programs cannot tolerate. The colloquial name for the resulting class of failures was DLL hell, and the phenomenon was not specific to one vendor's platform.
The structure of the problem is a namespace in which the library is addressed by name alone. A single slot exists for each name, and installers compete for it.
\begin{proposition}[Single-slot conflict and its resolution]\label{prop:slot}
Let programs $P_1,\dots,P_k$ each require a library of name $\ell$ at a version in a set $V_i$ of acceptable versions. (i) If the system admits one installed version per name and $\bigcap_i V_i=\varnothing$, then the programs cannot all function. (ii) If the system keys installed libraries by the pair (name, version), then each program can be supplied with a version in $V_i$, subject only to the availability of that version.
\Proved{}
\end{proposition}
\begin{proof}
(i) A single installed version $v$ must belong to every $V_i$ for all programs to function, which requires $v\in\bigcap_i V_i$, impossible when the intersection is empty. (ii) With composite keys, each program is directed to the entry for a version in its own $V_i$, and entries for different versions do not collide.
\end{proof}
The remedies that emerged corresponded to the two halves of the proposition. Side-by-side installation, in which the version becomes part of the key, resolves conflicts at the price of storage and of multiplying the number of copies that require security updates. Isolation, in which each program bundles its own copies of libraries, achieves the same effect by a different route and is the basis of modern container images. Both abandon the single-slot sharing that created the problem. A third approach, the package manager, keeps shared installation but computes a consistent selection, which is where the complexity result of \Cref{thm:installability} applies.
\section{Registries and package managers}
Two components of the modern ecosystem are often conflated. A \emph{registry} is a service that stores published packages and metadata, and answers queries about available versions. A \emph{package manager} is a client tool that reads a project's declared requirements, queries one or more registries, resolves a consistent set of versions, retrieves them, and installs them. The Python Package Index and the tool commonly used with it, the Node ecosystem's public registry and its client, and the Rust crates registry and its build tool all illustrate the division. System-level package managers of Unix-like distributions combine both roles within the distribution's own infrastructure, with curated repositories maintained by the distribution.
The separation matters because the registry carries a risk that the client cannot eliminate: it determines what exists. A package that is withdrawn from a registry disappears from the world of all projects that did not retain a copy. The best-known illustration is an incident of 2016 in which the author of a very small and very widely used package removed it from the public Node registry and builds across the ecosystem failed. The package consisted of a few lines. Its removal demonstrated that a dependency graph is only as stable as its least-controlled node, and that the transitive closure of a project may contain components that the project's authors have never heard of. Registry policy was subsequently changed to restrict the removal of packages that others depend on, an example of institutional response to an infrastructural failure.
\begin{definition}[Registry dependence]\label{def:regdep}
A project has \emph{registry dependence} on a registry $\mathcal{G}$ if some artifact in the closure of its requirements is obtainable only from $\mathcal{G}$. The project has \emph{unmirrored registry dependence} if, in addition, no copy of that artifact is retained in the project's own storage.
\end{definition}
Registry dependence is not in itself a defect, since it is the point of a registry. Unmirrored registry dependence is a vulnerability in the sense of \Cref{ch:persistence}: it leaves referential persistence in the hands of a third party. Vendoring dependencies, mirroring registries, and hash-pinning with local caches are the corresponding mitigations.
\section{Semantic versioning as a convention}
Version numbers began as labels and became a communication channel. A widely adopted convention, proposed in the early 2010s, gives numbers three components, a major, a minor, and a patch number, and prescribes that the major number is incremented for incompatible changes to the public interface, the minor for backward-compatible additions, and the patch for backward-compatible corrections. The convention allows a consumer to state a requirement like \emph{any version with major number two}, relying on the promise that no such version will break the consumer.
The promise is a claim about behavior, and claims about behavior of programs are subject to Rice's theorem \cite{rice1953}. The convention is therefore a social contract and not a verified guarantee.
\begin{proposition}[Compatibility cannot be decided mechanically]\label{prop:semver}
For programs in a Turing-complete language, there is no algorithm that decides, given two versions $p$ and $p'$ of a library, whether $p'$ is backward compatible with $p$, in the sense that every client program that terminates correctly with $p$ also terminates correctly and with the same observable result with $p'$.
\Proved{}
\end{proposition}
\begin{proof}
Reduce the halting problem. Given a Turing machine $M$ and input $w$, let $p$ be a library exposing a function $f$ that returns the constant $0$. Let $p'$ be identical except that $f$ first simulates $M$ on $w$ and then returns $0$. A client that calls $f$ and prints the result behaves identically under $p$ and $p'$ exactly when $M$ halts on $w$ (when $M$ does not halt, the client under $p'$ does not terminate while under $p$ it does). A decision procedure for compatibility would decide the halting problem.
\end{proof}
The proposition does not make the convention worthless; it places the responsibility for compatibility on the humans who publish and on the test suites that approximate the semantics. Type systems and interface checkers verify a decidable subset, namely syntactic compatibility of signatures, which is necessary and far from sufficient. A mature ecosystem combines the convention, the checkers, and the experience of maintainers, with the understanding that none of them replaces the others.
\chapter{Version Control Before Git}\label{ch:vcsbefore}
\section{The first systems}
The earliest widely used systems for tracking changes to source files appeared in the 1970s and early 1980s. One system developed at a large telephone-company research laboratory \cite{rochkind1975} stored successive versions of a file as a compact record from which any version could be reconstructed, together with who made each change and when. Another, developed in the early 1980s \cite{tichy1982}, reversed the direction of storage: the newest version of a file was stored in full and older versions as differences, on the grounds that the newest version is the one most often requested. These systems operated on individual files, with locking to prevent simultaneous editing: a user who wished to change a file checked it out under a lock, edited it, and checked it in, at which point the lock was released.
The per-file model and the locking discipline reflect the working conditions of their period: small teams on shared machines, expensive storage, and the expectation that two people would not edit the same file at the same time. As teams grew and machines were networked, the locking discipline became a bottleneck, and the per-file model hid something important, namely that the unit of meaningful change is often a set of coordinated modifications across several files.
\section{Concurrent versioning and the repository state}
A system that became the dominant open-source tool of the late 1980s and 1990s replaced exclusive locking with concurrent editing and merging \cite{berliner1990}. Each developer worked on a private copy, updated it from a central server, and resolved conflicts when changes overlapped. The model scaled better. Its limitation was that the server still tracked revisions per file, and a commit that touched several files was executed as a sequence of separate operations. Between the first and last, the repository was in a state that no author had intended.
\begin{proposition}[Intermediate states under non-atomic commit]\label{prop:atomic}
Suppose a commit consists of $k$ independent file updates applied one at a time to a shared repository. (i) If the order of application is fixed, an observer can see $k+1$ distinct repository states associated with the commit, of which exactly two correspond to states intended by the author. (ii) If the order is unconstrained, an observer can see any of $2^k$ subsets of the updates applied, of which exactly two correspond to intended states. (iii) If the commit is atomic, exactly two states are visible, before and after.
\Proved{}
\end{proposition}
\begin{proof}
In (i), after applying the first $j$ updates for $j=0,1,\dots,k$ the repository is in state $S_j$, giving $k+1$ states; only $S_0$ and $S_k$ were intended. In (ii), any subset of the updates may have been applied when the observation is made, giving $2^k$ states, again with only the empty subset and the full set intended. In (iii), by definition, no intermediate state is observable.
\end{proof}
The consequences are practical and historical. Builds from a repository in an intermediate state fail or, worse, succeed with a mixed program. Revision numbers attached to files, which differed from file to file, made it impossible to name the state of the project as a whole except by a symbolic tag applied to every file. A successor designed in the 1990s and 2000s to address these shortcomings introduced atomic commits and global revision numbers, so that a single integer identified a complete repository state. This was a real advance in referential persistence: a person could say \emph{revision 1432} and have a determinate meaning, provided that the repository itself remained available and unrewritten.
\section{Centralized coordination and centralized storage}
All the systems of this era shared a design feature: a central server held the authoritative repository. Developers held working copies, but the history lived in one place. This coupled two functions that are logically distinct. The first is \emph{coordination}: deciding what the official history is and who can append to it. The second is \emph{storage}: holding the bytes of the history and serving them. In a centralized system both reside in the server. A server failure threatens storage, a server administrator controls coordination, and a person without commit rights cannot keep a history of local work that is integrated with the official one.
\begin{definition}[Coordination and storage]\label{def:coordstorage}
For a version control system, \emph{storage centralization} is the property that a single host holds the only complete copy of the history. \emph{Coordination centralization} is the property that a single party decides which histories are authoritative. The two properties are independent: a system may have centralized storage and distributed coordination, or distributed storage and centralized coordination.
\end{definition}
The distinction is easy to lose and is crucial for what follows. The distributed systems that appeared in the 2000s, among them systems named Monotone, Darcs, BitKeeper, Mercurial, and Git, eliminated storage centralization by giving every working copy the full history. They did not eliminate coordination centralization, and in practice most projects using them continued to designate a single repository as authoritative. The designation became a matter of convention and social recognition and not of technical necessity. The next two chapters examine how this convention arose and what supports it.