[av_dropcap1]T[/av_dropcap1]he discipline of Computer Science affects us all, but for many people it is shrouded in mystery. Forged from a union of mathematics and electrical engineering, it beautifully blends the abstract and practical, although knowing this does little to clarify what that means to the non-initiate. The term “Informatik”, or “information science”, was coined in German universities in the late 1950’s to describe the discipline, by the late founding father of German Computer Science, Karl Steinbuch.1
This really gets at the heart of the matter – Computer Science is about the acquisition, storage, and transmission of data. One of the founding legends of the field is about the Internet itself (originally a system named ArpaNet): that it was designed as a communication tool for military use that could withstand a nuclear attack. While the original aims were actually more modest2, fundamental design principles for internet technologies do emphasize robustness, by providing many routes for information to travel between two individual points. This allows for the network to survive failures in particular regions of the network by routing information around the problem area.
Early academic papers on internet technology focus on building communication systems that transfer information using discrete packets of data. This stands in opposition to communication systems that transfer information in a single circuit. This can be easily understood by imagining mailing someone one book a page at a time, as compared to reading it to her over the phone. Mailing books by the page could send a book more quickly by transferring pages in parallel, but requires sorting the mail as it arrives.
The robustness of packet based systems justifies dealing with some fairly abstract problems. For instance, pages may arrive out of order and need to be re-assembled. If a page takes too long to arrive one might ask for it again, knowing that requesting it to be re-sent could actually lead to receiving it twice.
The original ARPA (now DARPA) organization was instrumental in supporting research that eventually formed the backbone of the internet. It was founded by the Eisenhower administration as a research unit within the U.S. Defense Department. Spurred on by fear of the Soviet launch of Sputnik, this organization has supported many high risk/high reward projects3. In 2004, DARPA started a competition to encourage teams to build self-driving vehicles, which became a popular extracurricular project in schools with Computer Science programs4.
Before DARPA and the internet there were many ingenious low-tech ways to transmit military communication. Lower tech communication methods worked at a slower speed and a smaller scale than today’s internet, but the underlying problems help us to understand equivalent issues we experience today.
[av_slideshow size=’large’ animation=’slide’ autoplay=’false’ interval=’5′ control_layout=”]
[av_slide slide_type=’image’ id=’2872′ video=’http://’ mobile_image=” video_ratio=’16:9′ title=” link_apply=” link=’lightbox’ link_target=”][/av_slide]
[av_slide id=’2876′][/av_slide]
[av_slide id=’2877′][/av_slide]
[/av_slideshow]Slideshow: “La Ville d’Orleans”567
[av_dropcap1]O[/av_dropcap1]n one November evening in Paris, a balloon named “La Ville d’Orleans” took off near midnight, carrying two men, pigeons, and most importantly mail.8 This wasn’t just any commercial mail. In 1870 France was at war with Prussia, and Paris was under siege9. The balloon trip aimed to deliver a message from the Parisian governor to the French resistance, but after nearly twelve hours in flight in the wrong direction, it overshot its mark, landing in Norway.
Earlier in the war, the French started a balloon-based air mail service. This is thought to have processed 2-3 million letters over the course of a single year – demonstrating the enormous demand for the transmission of data, whether it be love letters or commercial contracts.
The pigeons carried on La Ville d’Orleans bear special note: pigeons were used to send a large amount of mail into Paris. Pigeons cannot carry as many letters as a hot air balloon, so the French cleverly encoded the mail onto collodion film slides, then re-transcribed the letters on arrival. The internet today, like the postal system, relies on a variety of routing techniques and vehicles for information delivery. Many homes today have at least three networks, each with their own internal design: wireless internet access, wired access (via ethernet), and a phone or cable line to the outside, although all three are typically bridged by a single device.
[av_image_hotspot src=’http://www.garysieling.com/blog/wp-content/uploads/2016/01/2077004-1-1030×325.jpg’ attachment=’2885′ attachment_size=’large’ animation=’no-animation’ hotspot_layout=’numbered’ hotspot_tooltip_display=” hotspot_mobile=’aviaTBhotspot_mobile’]
[av_image_spot tooltip_pos=” tooltip_width=” tooltip_style=” link=” link_target=” hotspot_color=” custom_bg=” custom_font=” custom_pulse=” hotspot_pos=’46.9,33′][/av_image_spot]
[av_image_spot tooltip_pos=” tooltip_width=” tooltip_style=” link=” link_target=” hotspot_color=” custom_bg=” custom_font=” custom_pulse=” hotspot_pos=’79.2,24.3′][/av_image_spot]
[/av_image_hotspot]Image from David Rumsey Maps10
[av_dropcap1]N[/av_dropcap1]early a hundred years prior to the balloon incident, the U.S. Post Office was established by Congress, and when the seat of government moved from Philadelphia to Washington, DC, the Post Office moved its supplies with two horse-drawn wagons.11 As the nation and technology grew, mail began to be moved across the country by rail and early airplanes.
In 1919, the first transatlantic flights started, and almost immediately carried mail. Daytime mail flights from New York to Chicago soon began. As air flights expanded across the nation, new innovations– such as parachutes, lighted runways, and equipment optimized for lower altitude flights– were developed to alleviate the dangers of air mail (for a fascinating reference, see Air Mail, an Illustrated History).8
Even before transcontinental air mail, the time savings of flying mail from New York to Chicago was enough to meet an earlier train, saving a full day on the trip across the country. This was funded by special stamps, allowing the consumer of the service to choose how their mail was prioritized and routed to its destination.
In modern times, the Post Office has many pricing options that control how mail is routed and delivered. For instance, this includes a service that allows external companies to separately route their own mail across, but use the Postal Service for delivery. Depending on where the mail goes, it may be scanned on a belt machine, automatically dropped into a truck, or sorted manually by mail carriers.12 The key here is that customers have some influence (the type of stamp they buy), but the mechanics of how to route a specific piece of mail from it’s current point to the next can be determined without all parties to the operation having to discuss it.
[av_hr class=’short’ height=’50’ shadow=’no-shadow’ position=’center’ custom_border=’av-border-thin’ custom_width=’50px’ custom_border_color=” custom_margin_top=’30px’ custom_margin_bottom=’30px’ icon_select=’yes’ custom_icon_color=” icon=’ue808′ font=’entypo-fontello’]
[av_dropcap1]T[/av_dropcap1]he same military and commercial drivers that influenced the development of postal mail also controlled the development of early mainframes, although as a consumer of computing, it is difficult sometimes to imagine the scale. According to one of the pioneers of Computer Science, Edgar Dijkstra, the IBM/360 cost more to develop than the Manhattan project (not adjusted for inflation)13.
Dijkstra was known for being a tough instructor. Originally from the Netherlands, he began his career as an academic in Cambridge, England, studying theoretical physics. While completing his studies he took a part-time position as a programmer at the Mathematical Centre in Amsterdam. At the time, they were trying to build their first computers. Since the computers were in development, programming was done on paper.
As a professor, he required students to submit their programming homework handwritten, noting that you could tell if someone’s thoughts were unclear if their work had many erasures.14 He observed that the labor of writing forces you to carefully consider whether the design of an algorithm is overly complex, providing an incentive to simplify, and being too poor to buy better equipment forces you to make better use of what you have.12
When he encountered peers in the United States, he complained of a lack of rigor among software developers. Of particular concern was a tendency to work in an experimental fashion: trying things to see what works, rather than thinking problems through in advance. He was particularly critical of IBM’s work, and suggested that the greatest American victory in the Cold War was that the Soviets decided to clone the IBM/36012 (a mainframe model that started shipping in 196615 ).
[av_image src=’http://www.garysieling.com/blog/wp-content/uploads/2016/01/360-91-panel-1030×697.jpg’ attachment=’2896′ attachment_size=’large’ align=’center’ styling=” hover=” link=” target=” caption=” font_size=” appearance=’on-hover’ overlay_opacity=’0.4′ overlay_color=’#000000′ overlay_text_color=’#ffffff’ animation=’no-animation’][/av_image]An IBM/360 installed at NASA16
While completing his studies in theoretical physics, Dijkstra decided to become a programmer because he found the intellectual challenge of programming greater than that of theoretical physics. He discovered that programming was not appreciated in the university – to the physicists he was a deserter. Mathematicians looked down on programming because it requires the practitioner to operate in the world of the finite.
At the time of his graduation, the computer he’d been working on was unveiled – the awesomely named Automatische Rekenmachine MAthematische Centrum (ARMAC). In order to do a public demonstration of this new computing machine, the team needed a piece of software that could demonstrate the use of the equipment to the public. Earlier demonstrations showed random number generation. While random numbers may seem like an abstract use for a computing machine, consider that this is necessary to operate a lottery. Prior to computerization lotteries used public information to determine winners, such as the last digits of stock prices, or baseball scores17.
For the release of the ARMAC, Dijkstra built an algorithm for finding routes on maps – a good problem for a machine that was now reliable. The software he built could find the shortest distance between two selected cities in the Netherlands, out of a list of 64.
In an interview, he described the development:
“What’s the shortest way to travel from Rotterdam to Groningen, in general: from given city to given city. It is the algorithm for the shortest path, which I designed in about twenty minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in ’59, three years late. The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. … Eventually that algorithm became, to my great amazement, one of the cornerstones of my fame. I found it in the early ’60’s in a German book on management science – – “Das Dijkstra’sche Verfahren.” Suddenly, there was a method named after me.”
Dijkstra’s Algorithm
The algorithm, now termed “Dijkstra’s Algorithm”18 wasn’t published until three years later, in 1959. Dijkstra was asked by a friend if he had anything he could contribute to a German mathematical journal called Numerische Mathematik, so he submitted a write-up of the algorithm and another he’d designed. At the time this was not considered mathematics, but he felt that the additional material made it more compelling. This type of material is now treated as fundamental to Computer Science programs, under the heading of “Discrete Mathematics”. The shift in importance of non-infinite mathematics stems from being the foundation of a host of well-known technologies, including GPS.
Dijkstra’s algorithm assumes that you can identify a series of locations, paths between them, and a “cost” of each – cost can be based on the distance, the time it takes to travel, or how many pieces of mail your balloon can carry. Locations could be cities, but they can also be air strips or rail stations. Variants of this algorithm handle special cases, like pigeons that can only travel one way.
[av_dropcap1]M[/av_dropcap1]ore sophisticated algorithms power the routing of information on the internet. GPS-style routing has omniscience about the structure of the network, whereas internet routing devices maintain tables that route data based on attributes of the address, and each entity that effectively forwards mail makes the best decision they can without knowing the final route. Following the postal analogy, a router in California might have a rule that zip codes from 10000-15000 are forwarded to a single peer in New York State, which would then fan this out to regional routers, who handle the final connection.
In the case of mail, you can also tie a “cost” function based on time or price to the type of stamp on your mail, you can route mail to the next stop by train or by plane, as appropriate, without knowing any information about the intent of the sender – a simple routing algorithm .
Much technology exists to improve the deliverability of information on the internet, like compressing technology that functions similarly to storing letters on micro-film. In fact, the routing of information on the internet actually solves a problem the French didn’t fully solve- it can re-send your mail when the pigeon is shot down by a sniper.
[av_mailchimp list=’0cd6c29281′ double_opt_in=’aviaTBdouble_opt_in’ on_send=” sent=’Thank you for subscribing!’ link=’manually,http://’ color=’av-custom-form-color’]
[av_mailchimp_field id=’0′ label=’Email Address’ type=’text’ value=” disabled=” check=’is_email’][/av_mailchimp_field]
[av_mailchimp_field id=’av-button’ label=’Subscribe’ type=’button’ value=” check=”][/av_mailchimp_field]
[/av_mailchimp]
- http://helios.informatik.uni-kl.de/euology.pdf [↩]
- http://www.internetsociety.org/internet/what-internet/history-internet/brief-history-internet [↩]
- http://www.computermuseum.li/Testpage/99HISTORYCD-ARPA-History.HTM [↩]
- https://en.wikipedia.org/wiki/DARPA_Grand_Challenge#2004_Grand_Challenge [↩]
- http://loc.gov/pictures/resource/cph.3a30765/ [↩]
- http://www.loc.gov/item/2003653010/ [↩]
- http://www.loc.gov/resource/cph.3b17810/ [↩]
- http://amzn.to/1JV2MLA [↩] [↩]
- https://en.wikipedia.org/wiki/Franco-Prussian_War [↩]
- http://www.davidrumsey.com/luna/servlet/detail/RUMSEY~8~1~24735~940068:Orograph–Europa-?sort=Pub_List_No_InitialSort%2CPub_Date&qvq=q:Pub_List_No%3D%272077.000%27%22%2B;sort:Pub_List_No_InitialSort%2CPub_Date;lc:RUMSEY~8~1&mi=6&trs=73 [↩]
- https://about.usps.com/publications/pub100/pub100_005.htm [↩]
- http://www.wsj.com/articles/u-s-mail-does-the-trick-for-fedex-ups-1407182247 [↩] [↩] [↩]
- http://dl.acm.org/citation.cfm?id=1787249 [↩]
- http://www-history.mcs.st-and.ac.uk/Biographies/Dijkstra.html [↩]
- http://www-03.ibm.com/ibm/history/exhibits/mainframe/mainframe_FS360.html [↩]
- https://commons.wikimedia.org/wiki/File:360-91-panel.jpg# [↩]
- http://historyatlanta.com/eddie-guyol-the-numbers-king-of-atlanta/ [↩]
- https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm [↩]
- https://commons.wikimedia.org/wiki/File:1938_CPA_625-633.jpg# [↩]