An accessible guide to our digital infrastructure, explaining the basics of operating systems, networks, security, and other topics for the general reader. Most of us feel at home in front of a computer; we own smartphones, tablets, and laptops; we look things up online and check social media to see what our friends are doing. But we may be a bit fuzzy about how any of this really works. In Bits to Bitcoin, Mark Stuart Day offers an accessible guide to our digital infrastructure, explaining the basics of operating systems, networks, security, and related topics for the general reader. He takes the reader from a single process to multiple processes that interact with each other; he explores processes that fail and processes that overcome failures; and he examines processes that attack each other or defend themselves against attacks. Day tells us that steps are digital but ramps are analog; that computation is about “doing something with stuff” and that both the “stuff” and the “doing” can be digital. He explains timesharing, deadlock, and thrashing; virtual memory and virtual machines; packets and networks; resources and servers; secret keys and public keys; Moore's law and Thompson's hack. He describes how building in redundancy guards against failure and how endpoints communicate across the Internet. He explains why programs crash or have other bugs, why they are attacked by viruses, and why those problems are hard to fix. Finally, after examining secrets, trust, and cheating, he explains the mechanisms that allow the Bitcoin system to record money transfers accurately while fending off attacks.
Author(s): Mark Stuart Day
Publisher: The MIT Press
Year: 2018
Language: English
Pages: 369
Tags: Computer Science: Popular Works, Digital Currencies
Contents......Page 8
Preface......Page 10
Acknowledgments......Page 14
1. Introduction......Page 16
I. Single Process......Page 18
2. Steps......Page 20
Bits......Page 23
Noise......Page 24
Is Computation Physical?......Page 25
Weighing Programs......Page 26
Analog/Digital Conversion......Page 27
Born Digital......Page 31
3. Processes......Page 32
Reading as a Process......Page 33
Turing Machines......Page 34
Infinite Processes......Page 37
Execution......Page 38
Effective Construction......Page 39
Hardware vs. Software......Page 40
Uniformity Gives Speed......Page 41
Moore’s Law and Uniformity......Page 42
4. Names......Page 46
What’s in a Name?......Page 47
Quoting......Page 49
Sentence Patterns......Page 52
Lambda......Page 53
5. Recursion......Page 56
Factorial......Page 57
The House That Jack Built......Page 58
Finite and Infinite......Page 61
All Software Is Flawed......Page 64
Discrete States......Page 65
Testing......Page 66
Massive Scale......Page 67
Doubling......Page 68
Branching......Page 69
Malleability......Page 70
Making Things Worse......Page 72
Requirements......Page 73
Specifications......Page 75
Implementation......Page 77
Environment......Page 80
Big Problems......Page 81
Computational Complexity......Page 82
Ignoring Constants......Page 83
Categories of Complexity......Page 84
Uncomputability......Page 86
Formal Logic......Page 87
No Solution to Hilbert’s Problem......Page 88
Russell’s Paradox......Page 89
Building a Paradox......Page 90
The Halting Problem......Page 91
II. Interacting Processes......Page 94
8. Coordination......Page 96
Multiple Books and Multiple Readers......Page 97
Deadlock......Page 98
Gridlock......Page 99
Detecting Deadlock......Page 100
Breaking Deadlock......Page 101
Livelock......Page 102
Thrashing......Page 103
9. State, Change, and Equality......Page 104
Stateless vs. Stateful......Page 105
Assignment......Page 106
Referential Transparency......Page 107
Is State Necessary?......Page 108
Same Object vs. Different Object......Page 110
Lost Update......Page 116
Two Processes, in Detail......Page 117
Interleaving......Page 118
Multiprocessing and Multiprogramming......Page 119
Some Example Interleavings......Page 120
Is This a Real Problem?......Page 122
Mutual Exclusion......Page 123
Using a Lock......Page 124
11. Interrupts......Page 126
The Unpredictable Environment......Page 127
Check, Check, Check …......Page 128
Interrupts and Handlers......Page 131
Shared Services......Page 132
Frequent Check, Rare Problem......Page 133
Protecting Memory......Page 135
System Calls......Page 136
12. Virtualization......Page 138
Managing Storage......Page 139
Virtual Memory......Page 141
Virtual Addresses and Real Addresses......Page 142
Virtual Machines......Page 144
Sharing Servers......Page 146
Building a Hypervisor......Page 148
13. Separation......Page 150
Autonomy......Page 151
Standards......Page 152
Distance Revisited......Page 153
Light Is Slow......Page 154
Is Anyone There?......Page 155
The Order of Events......Page 157
Reaching Agreement......Page 159
Heartbeats......Page 161
Are Earth-Size Distances Small?......Page 163
14. Packets......Page 166
Compression......Page 167
Incompressible Data......Page 168
15. Browsing......Page 170
Programs in Browsers......Page 172
Naming Resources......Page 173
Hierarchical Names......Page 174
Shorter Names......Page 176
Naming Servers......Page 177
Finding Servers......Page 178
Caching......Page 181
Talking to the Server......Page 184
Structure vs. Presentation......Page 185
Forms......Page 186
Escaping......Page 187
Searching Searches......Page 188
III. Unstoppable Processes......Page 190
Reliability vs. Availability......Page 192
Fail-Stop......Page 194
Spares......Page 195
Error Correction......Page 196
Error Detection......Page 197
Storage and Failure......Page 200
Flash......Page 202
Injury vs. Death......Page 203
Logging vs. Replication......Page 204
Stable Storage......Page 206
RAID......Page 207
Independent Failures?......Page 208
Common-Mode Failure......Page 209
Failure Rates......Page 210
Specifications Revisited......Page 214
Consistent Comparison......Page 215
Comparing Results......Page 217
Byzantine Failure......Page 219
Guaranteed Delivery?......Page 222
The End-to-End Principle......Page 223
Acknowledgment and Retransmission......Page 224
Multiple Acknowledgments and Negative Acknowledgments......Page 225
Congestion Collapse......Page 226
Congestion Control......Page 228
Cheating on Congestion Control......Page 229
19. Inside the Cloud......Page 232
Wires and Jacks......Page 233
Router......Page 234
Ethernet......Page 236
Interconnecting Networks......Page 237
Internet Protocol (IP)......Page 238
Routing as a Network Service......Page 239
DHCP......Page 242
Advertising......Page 243
Longer Routes......Page 244
Scaling Up......Page 245
IP Address Notation......Page 246
Distributed Management......Page 248
Network Address Translation (NAT)......Page 249
Routing Failure......Page 251
Interconnecting Different Routing......Page 252
Spraying Requests......Page 256
Tiers......Page 259
Geographic Distribution......Page 261
Cloud Computing and Big Data......Page 264
IV. Defending Processes......Page 266
Defending: An Overview......Page 268
Viruses......Page 269
Single-Purpose vs. Multipurpose......Page 270
Extensibility and Viruses......Page 272
Preventing Viruses......Page 273
Detecting Viruses......Page 275
22. Thompson’s Hack......Page 278
Translating High-Level Language......Page 279
Thompson’s Hack: Simple Version......Page 280
Thompson’s Hack: The Real Thing......Page 283
Assessing the Danger......Page 285
23. Secrets......Page 288
Secrets Are the Solution......Page 290
Steganography......Page 291
Cryptography......Page 292
Shared Secrets and One-Time Pads......Page 293
Key Exchange......Page 295
Public Key......Page 296
Multiplying and Factoring......Page 298
Messages via Multiplication......Page 299
Proving Identity Remotely......Page 300
24. Secure Channel, Key Distribution, and Certificates......Page 304
Why Is This Worthwhile?......Page 306
Secure Channel, Refined......Page 307
Key Distribution Center (KDC)......Page 309
Scaling up Key Distribution......Page 311
Certificates......Page 312
Cryptography for Integrity......Page 313
Revocation......Page 315
Root CAs and Hierarchies......Page 317
Trust Problems......Page 319
Ledgers......Page 322
Special Roles vs. Ordinary Participants......Page 324
Guarantor......Page 325
Bitcoin......Page 326
Distributed Ledger......Page 327
26. Bitcoin Mechanisms......Page 330
Unforgeable Transactions......Page 331
Unforgeable History......Page 333
Bitcoin Puzzles......Page 337
Hash Functions......Page 339
Hashing Data......Page 340
Moving Time Forward......Page 341
The Crowd Foils Cheating......Page 342
Rewards via Mining......Page 343
Pollution and Bitcoin......Page 344
Mining and Value......Page 345
Bootstrapping Value......Page 346
Bitcoin and Governance......Page 347
Significance of Bitcoin......Page 348
27. Looking Back......Page 350
Index of Metaphors and Examples......Page 352
Subject Index......Page 356
