Subject Index
Address See also Space, address; Memory, real; Memory, virtual
Ethernet, 221–223
internet protocol (IP), 223–235, 239 (see also Protocol, internet)
IPv6, 230
network, 167, 273–274, 289 (see also Address, internet protocol; Address, Ethernet)
private, 235
public, 235
wallet (Bitcoin), 317–318
Advertising (network address), 228–230, 233, 236, 238–239
AFR. See Failure rate, annual
Agreement
clock needed for, 144–146
Always-happens-before, 103–105
All-or-nothing, 17, 243. See also Model, digital; Transaction
Analog. See Model, analog
Appliance, 56, 242, 257–258, 261. See also System; Machine
Application, 118–122, 128–129, 132, 157, 244–248, 255–260
relocatable, 128
Arithmetic, 39, 76–77, 284–285
AS. See System, autonomous
Assignment
address, 228
port, 234
Asynchrony, 142–146
Attacker, 253–260, 267–271, 274–292, 295–301, 305, 313, 315–319, 322, 326–328, 332. See also Forgery; Cheating
Autonomy, 136–137, 214, 236, 239–240, 273–274. See also System, autonomous
Availability, 177–179, 197, 246, 297, 300, 310
early, 56
Backup (data), 197
Behavior, program, 17–24, 51–52, 54–55, 63, 68–71, 76, 90–95, 199–200, 257–260, 265–271. See also Execution; Process
coordination and, 86–88
interrupts and, 111–113, 120–122
BGP. See Protocol, border gateway
Bit, 8, 10–11, 137–138, 145, 151–154, 231–235
failed, 180
spare, 180–182
governance of, 332–333
mining of, 328–331
pollution and, 329–330
significance of, 333
value of, 330–331
Bitcoin puzzle, 322–326
Bit rot, 66
Blockchain, 326–333
Bookkeeper, 309–311
Boot loader, 256–257
Branching
execution, 53–55
hierarchy, 161
Browser, 155–159, 165, 168–173, 302. See also Client; Endpoint; Server
Bug. See Flaw, software
C (programming language), 265–270
CA. See Certificate authority
Cache, 166–169
cc (C compiler). See Compiler
CDN. See Network, content distribution
Certificate, 296–305, 316–317. See also Name; Cryptography, public-key
bogus, 304
revocation of, 300–301
self-signed, 302
users of, 305
Certificate authority (CA), 302–305
bogus, 304–305
customers of, 305
failure of, 303–305
hierarchy of, 302–305
root, 302–303
Certificate revocation list (CRL), 301
Chattiness, 140
Cheating, 214–215, 298, 315–316, 327–328, 330, 332. See also Forgery; Attacker
Chicken-and-egg problem, 279–280, 295, 331
Church, Alonzo, 73–74
Ciphertext, 275–276. See also Cryptography
Client, 136, 217, 227, 234–235. See also Endpoint; Browser; Server
Clock speed, 52–55
Cloud, 57. See also Cloud computing
network, 217–218, 239–240, 249
Code
bit-doubling, 181–185
error-correcting, 181–185, 192–193, 207–208, 210
error-detecting, 182–185
executable, 256–257, 264–271 (see also Execution; Behavior, program)
Combiner. See Value, combined
Comparison, consistent, 200–202
Completeness, 76–77
Complexity, computational, 66–71. See also Performance, program
Compression, 152–154
Computation, 2, 8, 183. See also Process; Execution; Complexity, computational; Construction, effective
centralized, 233
distributed, 136–149, 233, 236, 273–275
limits of, 49–77
nature of, 19–22, 25–29, 31, 36, 50–55 (see also Machine, Turing; Lambda calculus)
physicality of, 2, 10–11, 66, 199, 259
routing, 225–227, 233, 236–240
spare, 199–204
Computer science, 24–25, 32, 35–36, 46–47, 67, 73, 263–264
Concurrency, 101–109, 136, 140–144
Congestion, 212–214
Congestion collapse, 211–213
Congestion control, 213–215
Consistency
address assignment, 227
concurrent computation, 102
congestion control, 214
mathematical system, 76–77
replicated state, 148–149
transactions and, 243
Constant rate. See Traffic, constant-rate
Construction, effective, 24–25
Content
vs. form, 72–73 (see also Logic, formal)
vs. container, 89–90, 96–99, 101–107
Contradiction, 71–72, 74, 76, 91, 201
Controlled access, 82–83, 101, 108–109
Conversion
analog/digital (A/D), 12–16
data to code, 258–259
Coordination, 81–88
Coupling. See System, loosely coupled; System, tightly coupled
Crash, 180. See also Model, fail-stop
CRL. See Certificate revocation list
Cryptography, 277–283
public-key, 281–283, 285–288, 290–296, 298–300, 317
Data, 8–9
big, 249–250
deleted, 188–189
lumpy, 153–154 (see also Traffic, bursty)
obscure, 286, 290–291, 293–294, 299
Data center, 197, 241, 246–248
Deadlock, 83–87
Decision process. See also Agreement; Failure, Byzantine
architectural, 52
asynchronous, 145–146
miner’s, 330–331
multiversion, 202–203
Decryption, 286–287, 289–294. See also cryptography
communication by, 275–283
Delivery, guaranteed, 207–209
Detection, error. See Code, error-detecting
Detection, virus, 260
Device. See also Endpoint; Browser; Client; Server; Appliance
identical, 194–195
input/output, 112–118
multipurpose, 255–260
network, 217–221
storage, 130, 180, 185–197 (see also Disk, magnetic)
DHCP. See Protocol, dynamic host configuration
Diffie-Hellman-Merkle. See Key exchange, Diffie-Hellman-Merkle
Digital. See Model, digital
Disk, magnetic, 112, 130, 180, 185–189. See also Device, storage
spare, 191–195
Disks, redundant array of inexpensive (RAID), 192–194
Earth-size, 148–149
internetworking and, 222–223, 239–240
resilience and, 246–249
trust and, 273–274
Distributed operating system. See System, distributed operating
Distribution, geographic, 246–249
Divergence. See Halting problem
DNS. See System, domain name
Domain, 163–169
top-level, 166
DoubleHackedC (H2C), 269–270
Doubling, 38–39, 53–54, 235, 284. See also Code, bit-doubling; Storage, stable; Sampling
Drive, solid state (SSD), 187–188
Emulation, 66
Encryption, 154, 277–280, 285–288, 290–294. See also Cryptography
End-to-end principle, 208–210
Endpoint, 217–219, 227–240, 249. See also Client; Browser; Device; Server
Environment (natural world), 329–330
Environment (of program), 65–66, 112–113, 131, 259
Equal-now-and-forever, 95–97
Equal-now-but-might-change, 95–97
Error, 199–205. See also Code, error-correcting; Code, error-detecting
implementation, 49–52, 54–58, 62–63
trial and, 285, 326 (see also Randomness)
off-by-one, 63
Error rate, 57–58. See also Failure rate
Escaping (of data), 172–173
Ethernet, 221–224
Example. See metaphors and examples
Exclusion, mutual, 108–109
Execution, 23–27, 63, 93–95, 111–112, 256–257. See also Process; Behavior, program
Expiration, 301
Explosion
dynamite, 51–52
Expression
lambda calculus, 38–39
natural language, 46
Extensibility. See Programmability; Universality
Factoring, 283–285
Failover, 146–148. See also Spare; Model, failure
Fail-stop. See Model, fail-stop
Failure, 177–197, 199–205, 207–215, 253–254. See also Model, failure
agreement, 144–148
bookkeeper, 310
Byzantine, 204–205, 236 (see also Model, Byzantine)
certificate authority, 304–305
governance, 332–333
guarantor, 310–311
independent, 136, 189–192, 193–194, 199–200, 241, 270, 302–305
network, 144, 207–209, 213–215
protection, 121
routing, 236
software, 199–205
Failure rate, 195–197. See also Error rate
annual (AFR), 196
Federal Reserve, U.S., 310–311
Filtering (addresses), 233
Fisher-Lynch-Patterson (FLP) Impossibility. See Agreement, clock needed for
Flash storage, 187
Flaw, software, 49–50
Forgery, 273–275, 296, 316–322, 326–327. See also Cheating; Attacker
Form (on web page), 171–172
Fourier series, 12–15
FSM. See Machine, finite-state
Gateway, 237 See also Protocol, border gateway
Gibson, William, 335–336
Google, 107, 149, 155–159, 162–174, 177–178, 241–242
Governance, 332–333
GPS. See System, global positioning
Granularity, 18–19, 180, 201, 208–209. See also Sampling
Gridlock, 84–85, 212. See also Failure, multiprocess
Growth. See Complexity, computational
Guarantor (currency), 310–311
Hack, 264. See also Thompson’s hack
HackedC (HC), 267–269
Halting problem, 76–77, 87, 260
Handler, 116–120, 128–129. See also Interrupt
Hardware, 19, 22, 23, 25–29, 264. See also Machine; Device; System
checking, 120–122, 274–275 (see also Interrupt)
failure of, 146–148, 179–180, 185–197, 236 (see also Model, failure)
reliability of, 195–197
subverted, 271
virtualization of, 123–124, 131–133 (see also Machine, virtual; Memory, virtual)
Hash function, 324–326
H2C. See DoubleHackedC
HC. See HackedC
Heartbeat, 146–148
Hierarchy. See Name, hierarchical; Trust, hierarchy of
Hilbert, David, 72
Hilbert’s Problem, 72–73
History, unforgeable, 318–322
House That Jack Built, The, 43–46
HTTP. See Protocol, hypertext transfer
http: (URL scheme), 158–159, 169–170
https: (URL scheme), 158–159
Identity, 89, 98–99, 295–297. See also Name; Trust; State
proving, 285–294
Identity function, 39–40
Implementation, 22–24, 56–58, 62–63, 93–94, 199–203, 257–259. See also Error, implementation
I/O. See Input/output
Inflation, 311
Infrastructure, 1, 131, 157, 297
Instruction, 22, 107, 115, 120, 264–271. See also Code, executable; Language, machine-friendly
Integrity, 298–300
Interaction
browser/server, 156–157, 171–172, 242, 247, 304–305
key exchange, 280–281
network/network, 239
program/environment, 65–66, 112–117
real-world, 295 (see also Trust)
server/server, 244
user/program, 59, 62, 171–172, 335
user/user, 304–305
Interception (of message), 274
Interference, 212. See also Noise
Interleaving, 103–107
Internet, 136–137, 151, 213, 222–224, 234, 237–240
Internet routing. See Router
Interrupt, 111–113, 116–122, 123, 128–129, 133
IP. See Protocol, internet
IPv4. See Protocol, internet
IPv6. See Protocol, internet
Joke
Dogmatix, 31
outrun a bear, 254
rocks have bad I/O, 118
spherical cow, 25
the program is the holes, 11
TLA is a TLA, 41
XINU Is Not Unix, 41
KDC. See Key distribution center
Ken Thompson Hack. See Thompson’s hack
Key
cryptographic, 277–283, 285–288, 291–292, 294–297, 304, 316–317. See also Cryptography
on keyboard, 112–119, 133. See also Keystroke
Key distribution center (KDC), 294–297, 300–302
Key exchange, Diffie-Hellman-Merkle, 280–281
Keystroke, 115–119, 173–174. See also Key (on keyboard)
KTH. See Thompson’s hack
Language
functional, 96
high-level, 264–266
machine-friendly, 265 (see also Code (executable); Instruction)
markup, 170
Leasing, 228
Ledger, 307–309
distributed, 311–313, 322–330, 333
Light, speed of, 138–141
Livelock, 87–88
Logging, 189–190, 313, 316, 318–322, 327
Logic, formal, 72–73
Machine. See also Hardware; System; Device; Appliance
failure of, 179–180
finite-state (FSM), 21
performance of, 26–28
physical, 11, 25–26, 94, 124, 126–133, 194, 273–274
remote, 246–248, 273–274 (see also System, distributed)
step-taking, 19–25, 104–105, 111–120, 127–129, 131–133
Turing, 19–22, 73 (see also Programmability; Universality)
virtual, 124, 129–133, 249–250
Machine instruction. See Instruction
Maintenance, 57–58
Malleability, 55–58
Management, distributed, 233
Mathematics, 42–43, 67–70, 283–285, 323–324, 333
computation vs., 25, 91–92, 96, 145, 200–202
effective construction not required in, 25, 145
logic and, 72–77
Mean time before failure (MTBF), 195
Memory, 22, 120–121, 125–129, 273–274. See also Address
real, 124, 126–128 (see also Address, real)
virtual, 124–125, 126–129, 133. (see also Address, virtual)
Memory protection, 120–121, 128–129, 273. See also Interrupt
Message. See also Network; Ordering
asynchronous, 140–148
forging, 273–274 (see also Cheating; Attacker; Forgery)
performance of sending, 139–140, 211–215
redundant, 208–211
routing of, 217–231, 233, 237–240 (see also Router)
secret, 275–280, 284–288, 289–294 (see also Cryptography)
timestamped, 149
translating address of, 234–235
unpredictability of, 112–113, 207–208
Method (web), 156–157
Mining, 328–331
Mock-up, 62
Model. See also Representation
analog, 8–10, 12–16, 24, 50–51, 152–153, 200–201
Byzantine, 204–205, 236, 313 (see also Model, failure)
digital, 5–10, 12–22, 50–52, 58, 151–153, 179–180, 200–201
fail-stop, 179–180, 236 (see also Model, failure)
failure, 179–180, 204–205, 253–254, 313
Money, 307–312, 315–318, 331, 333
Moore, Gordon, 27
Mother Goose, 43–46
MTBF. See Mean time before failure
Multiplication, 283–285
Multiprocessing, 104–105
Multiprogramming, 104–105
Nakomoto, Satoshi, 332
Name, 32–40
hierarchical, 158–169
mutable value of, 92, 95–98, 248 (see also Name/value substitution)
recursive definition of, 41–42
signed binding of, 296–297, 300–303 (see also Certificate)
Name/value substitution, 31–45, 91–92, 95, 165–168. See also Name, mutable value of
Naming
delegation of, 164–166
resolution of, 159–169
NAT. See Translation, network address
National Security Agency, U.S. (NSA), 158, 332
Negation, 74–76
Netmask, 231–232
Network, 137–138, 140–142, 145, 217–240, 273–274. See also Message; Router; Packet
best effort, 208
guaranteed delivery, 207–208
content distribution (CDN), 248–249
peer-to-peer, 311–316, 327–333
reliable, 141, 169, 183, 207–215
round-trip time of, 138–140
virtual, 124
Nonlinearity. See Linearity
Notation, IP address, 231–232
NSA. See National Security Agency, U.S.
Obscurity, 277–278, 286–287, 290–291, 293–294, 299
Omnipotence, 71
One-time pad, 279–280. See also Cryptography, shared-secret
Ordering
causal, 142
fixed, 318–322
Overflow, 118–121
Packet, 151–153, 169, 207–208, 214, 235. See also Message; Router; Network
Participant, 310–313
Partition, 147–148
Path
network, 207–208. See also Router
Pattern, 10–11, 36–38, 44–46, 154
Payment, 307–311, 316–318, 333
Performance. See also Speed
network, 140, 209, 214–215, 247–249
program, 66–71, 132–133 (see also Complexity, computational)
Physicality. See Computation, physicality of
Plaintext, 275, 277, 284, 299–300
Pollution, 329–330
Port
IP address, 234–235
network device, 219. See also Jack
Porting, 66
P2P. See Network, peer-to-peer
Presentation (web page), 170
Prime, 283–284
Process, 2, 17–19, 24, 36, 127, 129–130. See also Concurrency; Program; Execution; Behavior, program
clairvoyant, 75–76
decision, 52, 73, 145, 202, 204, 330–331
infinite, 22–23, 41, 46–47, 51, 93–94
interacting, 81–109
lookup, 164–165
perfect, 65–77
Program, 2, 11, 22–25, 36, 264–271. See also Process; System, operating; Hypervisor; Handler
data layout for, 125–127
interrupting a, 111–113, 116–122
misbehaving, 254–261
perfect, 65–77
resource as, 156
script as, 157
spare, 199–205
using state in, 93–95
Programmability, 255–261. See also Universality
Protection. See Memory protection
Protocol
border gateway (BGP), 238–240
consensus, 145–146
dynamic host configuration (DHCP), 227–228
hypertext transfer (HTTP), 158–159, 169–170
internet (IP), 223–224, 225–235 (see also Router; Network)
internet (IPv4), 230–235
internet (IPv6), 230–231
routing, 236
transmission control (TCP), 169, 211, 213–214
Public key. See Cryptography, public-key
Puzzle, bitcoin, 322–326
Quad, 235
RAID. See Disks, redundant array of inexpensive
Randomness. See also Error, trial and
compression and, 154
Real world. See Interaction, real-world
Receiver (of message), 181–185, 207–212, 217, 235, 274–275, 284–285. See also Sender; Protocol
Reconstruction
data, 181, 188–189 (see also Code, error-correcting)
wave, 14–15
Recursion, 41–47, 164–165. See also Self-reference
mathematical, 42–43
data, 208
hardware, 189–195
software, 199–203
Regulation, 246–247
consensus, 144–146
network, 140–142, 146–148, 208–213
operating system, 121
software, 199–205
statistical measures of, 195–197
storage, 186–195
virus detection, 260
Relocatability. See Application, relocatable
Replication, 189–193. See also Redundancy
Representation. See also Model
blockchain, 316–327
digital, 5–6, 8–10, 14–16, 137–138
finite, 200–201
infinite, 201
IPv4 address, 231–232
ledger, 316–327
packet, 151–154
physical, 10–11
visual, 155–157
Request. See also Protocol; Response
disk, 186
identity proof, 286–288, 290–291, 293–294
network, 227
system call as, 121
web, 155–156, 163, 169–174, 241–248 (see also Browser)
Requirement (software development), 58–60
Resource (web), 156–159, 163, 169
Response. See also Protocol; Request
identity proof, 286–288, 290–291, 293–294
speed of, 138–140
web, 169–174 (see also Server)
Retransmission, 209–213
Reversal
mathematical, 283, 285, 324–325
transactional, 243
Revocation. See Certificate, revocation of
Root (of hierarchy), 161, 165–166, 168–169, 302–305
Root CA. See Certificate authority, root
Russell, Bertrand, 74
Russell’s paradox, 74–75
Safety factor, 51
Same-object-equal, 96–98
Same-value-equal, 96–98
Scale
economies of, 28
interplanetary, 138–139
key distribution, 296–297, 302–304
planetary, 149
problem, 66–71
program, 52–55
Scheme (of URL), 158–159, 163, 169–170
Secret, 158, 263, 273–294. See also Cryptography
Security, 253–254
encryption for, 273–283, 285–305
network, 158–159
operating system, 256, 268, 274
Security through obscurity, 278
Self-reference, 41, 74–76. See also Recursion
Sender (of message), 207–215, 274–275. See also Receiver; Protocol
asynchronous, 140–144
encoding, 181–185
Sequence. See also Interleaving
agreed, 313–322 (see also Ledger, distributed; Bitcoin)
certificate, 303
infinite, 94
message, 211
puzzle, 323–326
step, 18–19
Server, 136, 227. See also Endpoint; Client; Browser
named, 162–166
root (DNS), 165–166
shared, 131–133
virtual, 242–243
web, 155–159, 162–163, 169–174, 241–250
Service
computing, 249–250
directory, 163–166
routing, 224–231, 233, 236–240
search, 107, 158, 170–174, 177–178, 241–242
shared, 59, 65, 117–118, 126, 129–131, 133, 157 (see also system, operating)
web, 155–159, 163, 169–174, 241–250
Shannon limit, 14–15
Sharing. See also Cryptography, shared-secret
certificate, 296–305
GPS, 149
ledger, 307–309, 311–313, 315–333
routing information, 228–231, 233, 236–240
server, 131–133
uncontrolled, 102–107
Signing, 296–305, 316–324, 326
Signing, delegation of, 297, 302–305
Simultaneity, 137, 139–140, 141–144, 149, 192, 250
Software, 2, 17, 25–26, 49–63, 123–124, 131–132. See also Process; Program
multiversion, 199–205
vulnerability of, 253–261, 263–271
Space
address, 127–128, 235 (see also Address)
storage, 94–95, 120, 124–128, 207–208, 225
Spanner, 149
Spare, 180–182, 193–195, 199. See also Redundancy
Specification, 22–23, 60–63, 199–202
Speed. See also Performance
light, 139–140
mining, 329
program, 53–55, 66–71, 246–250
typing, 119
virtual machine, 133
Split-brain problem, 147–148
Spraying (requests), 241–243, 248, 257
SSD. See Drive, solid state
Standard, 137–138, 162, 332. See also Protocol
consistent, 101–109, 147–149, 243
discrete, 50–52, 58, 179–180, 271 (see also Model, digital)
durable, 177
mutable, 89–99
shared, 101–109
State machine. See Machine, finite state
Step. See Machine, step-taking; Model, digital
Steganography, 276–277
Storage, stable, 191–194, 199. See also Disks, redundant array of inexpensive
Structure (web page), 170
Subnet, 233
Substitution
device, 194
key, 296–297
message, 291–292
Summarizing (addresses), 233, 239
Switch (multiway), 81, 217, 219–220, 242
System
autonomous (AS), 238–240 (see also Autonomy)
asynchronous, 142–146
certificate, 297–305
compression, 152–154
concurrent, 81–88, 101–109, 111–122, 129–133, 136
cryptographic, 278–294
distributed, 136–149, 246, 249, 273
distributed operating, 149, 157 (see also System, operating)
domain name (DNS), 163–169, 227, 248, 303
fault-tolerant, 146–148, 177–195, 199–205, 312, 328, 330
file, 130
global positioning (GPS), 142, 149
input/output (I/O), 112–113, 118–120
key management, 277, 294–297, 300–305
loosely coupled, 135–136
long running, 320
mathematical, 73–77
naming, 32, 35, 159, 166 (see also System, domain name)
operating, 65, 118, 120–122, 126–133, 157, 256–259, 263–271, 273–274 (see also Hypervisor; System, distributed operating)
tightly coupled, 135–137
trust, 273–274, 275–305, 310–313, 315–328, 332–333
System call, 121–122. See also System, operating; Interrupt
TCP. See Protocol, transmission control
Thompson, Ken, 263–264
Thompson’s hack, 263–271
Threat. See Model, threat
Trade-off
audio/video system, 15
architectural, 52
completeness/consistency, 76
hardware/software, 26
performance/fault-tolerance, 193
quality/scale, 233
reliability/availability, 179
Traffic. See also Router; Message; Protocol; Packet
asynchronous, 141
bursty, 152–154, 208 (see also Data, lumpy)
car, 84–85
constant-rate, 152
controlled, 213–214
encrypted, 279
interfering, 212–215
request, 242–249
rewritten, 234–235
Transaction
signed, 316–318
unforgeable, 316–318
Translation
address (real/virtual), 128
literary, 31
high-level language (programming), 264–271
network address (NAT), 234–235
Transparency, referential, 92–93, 95–96
Trust. See also Interaction, real-world
Bitcoin does not require, 311–313, 315–316, 333
monetary roles and, 309–311
delegation of, 303–304
distributed systems and, 273–275, 277–278, 294–305 (see also Trust, Bitcoin does not require; Trust, software construction and)
hierarchy of, 303–304
software construction and, 260–261, 263–271
Turing Award, 263–265
Uncomputability, 71–76
Uniform resource locator (URL), 158–172, 249
opaque, 162
Uniformity, 26–28
Universality, 22, 73–76, 255–257. See also Programmability
Update
ledger, 308, 313, 315–316, 326, 330
lost, 101–109
value, 96–99, 189–192, 264–265 (see also Name/value substitution)
URL. See Uniform Resource Locator
Value. See also Update, value; Comparison, consistent; Same-value-equal; Name/value substitution
combined, 202–204
monetary, 331
address, 127–129
memory, 124–129
network, 124
server, 242–243
Virus, 254–261
cryptographic, 278
hardware, 271
network, 274
nontechnical sources of, 304–305
operating system, 258
software, 271
virus, 254–261
Waits-for graph, 85–87
Wave, sine, 12–15
Web, 155–174, 211, 235, 241–249
Weirdness, distributed-system, 148–149. See also Relativity, special