L1: Intro to Computer Systems: Complexity Frans Kaashoek and Robert Morrishttp://web.mit.edu/6.033Example 6.033 ReadingsEmergent Property Example: EthernetPropagation of Effects Example (L. Cole 1969)Galileo in 1638Incommensurate scalingExample: more goals, more complexityExample: interacting features, more complexityClass planL1: Intro to Computer Systems:ComplexityFrans Kaashoek and Robert Morris6.033 Spring 2009http://web.mit.edu/6.033http://web.mit.edu/6.033•Schedule has all assignments•Every meeting has preparation/assignment•First deliverable is due Tuesday•Read the Therac paper for Friday•Return sign-up sheet at the end of lecture(if you didn’t do so yesterday)•We will post sections assignment tonightExample 6.033 ReadingsTherac-25UNIXEthernetEnd-to-End ArgumentsSystem REmergent Property Example: Ethernet•All computers share single cable•Goal is reliable delivery•Listen before send to avoid collisions•Will listen-while-send detect collisions?Maximum cable length!Minimum packet size!Propagation of Effects Example (L. Cole 1969)•WHO attempted to control malaria in North Borneo •Sprayed villages with DDT•Wiped out mosquitoes, but ….•Roaches collected DDT in tissue•Lizards ate roaches and became slower•Easy target for cats•Cats didn’t deal with DDT well and died•Forest rats moved into villages•Rats carried the bacillus for the plagueWHO replaced malaria with the plagueGalileo in 1638“To illustrate briefly, I have sketched a bone whose natural length has been increased three times and whose thickness has been multiplied until, for a correspondingly large animal, it would perform the same function which the small bone performs for its small animal. From the figures here shown you can see how out of proportion the enlarged bone appears. Clearly then if one wishes to maintain in a great giant the same proportion of limb as that found in an ordinary man he must either find a harder and stronger material for making the bones, or he must admit a diminution of strength in comparison with men of medium stature; for if his height be increased inordinately he will fall and be crushed under his own weight. Whereas, if the size of a body be diminished, the strength of that body is not diminished in the same proportion; indeed the smaller the body the greater its relative strength. Thus a small dog could probably carry on his back two or three dogs of his own size; but I believe that a horse could not carry even one of his own size.” [Dialog Concerning Two New Sciences, 2nd Day]Incommensurate scaling•Scaling a mouse into an elephant•Volume ~ O(x3) where x is a linear measure•Bone strength ~ cross section ~ O(x2)•[Haldane, “On being the right size”, 1928]•Scaling Ethernet’s bit-rate•10 mbit/s: min packet 64 bytes, max cable 2.5 km•100: 64 bytes, 0.25 km•1,000: 512 bytes, 0.25 km•10,000: no shared cable•Scaling the Internet•39 sites in 1973•Total size of tables (for shortest paths): O(n2)Example: more goals,more complexity •1975 Unix kernel: 10,500 lines of code•2008 Linux 2.6.24 line counts: 85,000 processes 430,000 sound drivers 490,000 network protocols 710,000 file systems1,000,000 different CPU architectures4,000,000 drivers7,800,000 TotalExample: interacting features, more complexity•Call Forwarding•Call Number Delivery Blocking•Automatic Call Back•Itemized BillingA C??ABCNDBACB + IB•A calls B, B is busy•Once B is done, B calls A•A’s number on appears on B’s billCF CFClass plan•Next lecture: computer systems are different•Naming: gluing modules together•Client/server: enforced modularity•Networks: hard boundaries between modules•Reliability and transactions: handing failures•Security: handling malicious
View Full Document
Unlocking...