October 5th, 2008

My 10/05/08 Missoulian column: The logic of digital decisions

We say we think logically when we figure out problems step-by-step and by trial and error. If our truck won’t crank over in the morning, before we call the tow truck we might turn the headlights on to see if the battery has a charge. We know that the starter runs off the battery, and if the lights don’t come on we know the battery might be dead and so maybe we can get a jump start from the neighbor.

But if the lights are bright, we know that there’s juice in the battery and we can deduce that the problem might be with the starter. Time for a tow truck. But we might try something like jiggling some loose wires under the dash, and if we find that the truck will crank over, we know that there’s a loose connection in those wires and maybe we can get to work and back a few more times by jiggling the wires.

The digital logic in computers also makes decisions in logical steps, but very simple decisions using only the “ones” and “zeros,” the building blocks of digital information. The “decisions” a computer makes are the result of built-in logic in the form of “gates,” the building blocks of logic. Software tells the gates what to do with ones and zeros - which numbers to add, what to put into memory, what to record on a hard drive - and the logic gates make simple decisions depending on the ones and zeros they are given to work with. All those decisions happen in millionths of a second and result in the Web browser running correctly and giving us the Web page we want to see.

Basic computer logic works with three different kinds of gates, and we can draw a metaphor for how differently they work with light switches and light bulbs. The first type of logic gate needs two different switches thrown at the same time in order to light the room; not one or the other, but both at the same time. The second type of gate needs just one or the other switch thrown to light the room, but is also quirky in that it will also light the room if both switches are on. And the third type of gate has just one switch, but it works in a particular way: the light is on when the switch is off, and the light is off when the switch is on.

These three types are called AND, OR and NOT gates, and from those names it might already be obvious which is which. Now, thinking of the way digital computers work - with ones (the light is on) and zeros (the light is off) - an AND gate looks for ones at both of the inputs; an OR gate looks for a one at either of two inputs; and a NOT gate reverses whatever is at the input. And so each of these gates makes a very simple logical decision based on binary states: one or zero, or, like the lights and switches, on and off.

But with lots of these gates put together in complicated patterns, much more complex decisions can be made, and with those three basic types of gates - and special “hybrids” based on those three - all of the functions of a computer can be made to work. Those hybrids can be NAND or NOR gates, which work like AND or OR gates, but opposite; or they can be “counters” that count in binary, or they can be very simple memory banks called registers. But they all begin with the simple AND, OR and NOT gates. Put hundreds of thousand or millions of gates together and you have a modern microprocessor. Logic gates - Wikipedia.

All of the different kinds of gates come to life in the circuitry of a computer by way of tiny components like transistors and other electronic goodies. Transistors serve as electronic switches like the flipping of light switches on or off. Transistors sense either a one or a zero at the handle of the gate and respond - or not - depending on which kind of gate.

Like anything high-tech, logic gates have shrunk in size over the years. The first logic gates were made from vacuum tubes and took up buildings and used whole power plants of electricity. Then the transistor came in during the 1950s, and gates became smaller and used much less electricity. Then the first integrated circuit - with lots of transistors on one chip - was invented in the late 1950s, and a bunch of gates could fit in half a square inch and run from a battery. Now, the average microprocessor in your PC has hundreds of thousands - or more - gates on one chip. Moore’s Law says that the number of transistors that can be put on an integrated circuit doubles approximately every 18 months, and that is expected to remain true for possibly another decade.

With all those millions of switches making up logical gates, does computer logic make “mistakes”? Yes, if the logic is not correct to begin with. Millions of dollars go into testing microprocessors before they go out into the real world in a PC. But in 1994, Intel shipped a brand-new Pentium processor that had a subtle flaw in the logic of the the chip. Mathematicians soon discovered that in very rare cases, the chip gave wrong results in complex calculations. The flaw was traced to just a few gates on the chip, and while very few people would notice, competition was very real in the growing microprocessor business, so the Pentium chip was recalled and free replacements offered.

And, rarely, cosmic rays and other forms of background radiation can cause logic glitches. Modern logic gates are made of transistors and components so small that a particle of naturally occurring background radiation can “flip” the value of a gate - from one to zero or from zero to one - and result in wrong data or a “freeze up.” But built into many forms of computer logic and memory circuits are other types of logic that perform error correcting, and so when a “check sum” doesn’t add up, the logic “knows” something is wrong and recalculates, or tells you with an error message.

So between the logical complexities and error correcting, sometimes you won’t even know the once-in-a-billion-time that a tiny bit of logic in your PC happens to make a wrong logical decision. But if you deduce wrongly the logical reason why your truck will or won’t start, you’ll know it right away.

Email   Front Page   Printable Post   Share/Bookmark

September 30th, 2008

This week in the Missoulian: the basics of computer logic - AND, OR and NOT gates. Millions of such gates make up the average microprocessor.

And: is cloud computing a bad idea? Are web services for word processing, search - and everything else under the sun it seems - are bad because we might get “locked in” to these free services that we don’t fully control? Richard Stallman thinks so.

Richard Stallman is (from his Wikipedia entry ) Richard Matthew Stallman (born March 16, 1953), often abbreviated “rms”, is an American software freedom activist, hacker (programmer), and software developer. In September 1983, he launched the GNU Project to create a free Unix-like operating system, and has been the project’s lead architect and organizer. With the launch of the GNU Project, he started the free software movement and, in October 1985, set up the Free Software Foundation.

From the 9/30/08 The UK Guardian: Cloud computing is a trap, warns GNU founder Richard Stallman. Web-based programs like Google’s Gmail will force people to buy into locked, proprietary systems that will cost more and more over time, according to the free software campaigner.

From the article:

The concept of using web-based programs like Google’s Gmail is “worse than stupidity”, according to a leading advocate of free software. Cloud computing – where IT power is delivered over the internet as you need it, rather than drawn from a desktop computer – has gained currency in recent years. Large internet and technology companies including Google, Microsoft and Amazon are pushing forward their plans to deliver information and software over the net.

People have often wondered when and if Google will start charging people for all the services that are currently free, including Documents, Gmail and especially Google Books - where Google is scanning hundreds of thousands of books as part of their efforts create a universal library. But will Google charge for all these things one day? And will then all of us be “locked in”?

Email   Front Page   Printable Post   Share/Bookmark

September 28th, 2008

My 9/28/08 Missoulian column: Even today, “garbage in, garbage out”

Here’s a story that shows the interconnectedness of the Internet. That, in itself, isn’t anything new, but when I first started following this story, I remembered an old programmer’s saying that seemed to sum it up: “garbage in, garbage out.” I think you’ll see why.

The big picture is one of a few small mistakes on the Web and the unintended consequences exacerbated by software, which resulted in the loss of a large amount of money by some people. Not too many years ago, a similar cascade of events couldn’t have happened, but now, with the myriad connections in human and cyberspace, it has and likely will again. And again. The dust is starting to settle on this case, except in certain lawyer’s offices, I’ve read.

Let’s start at the source of the problem: a Florida newspaper’s Web site and an article from 2002 about United Airlines going bankrupt - nothing too complex. The story was in the newspaper’s online archive and was read a number of times, perhaps by people looking at the history of United or by others who just stumbling across it.

That’s where the cascade begins: Because the United bankruptcy story was viewed a number of times, the article appeared in the “most read” sidebar on the newspaper’s home page, a common feature on many news sites.

That innocent rise up the “most read” column was compounded by another detail - or, rather, a missing detail. The 2002 article appeared to be a current news story because the original date was missing.

Now, the “most read” column was the result of an algorithm. What’s an algorithm? It’s the method a computer uses to perform a complex task. In this case, the algorithm counts hits on articles and display links to the most popular stories in the “most read” column.

That innocent action was complicated by the missing date, a mistake from a programmer somewhere down the line. The original article must have had a date, because that was how it was archived in the first, but it didn’t appear on the screen.

The next event in the cascade is that Google News happened by the newspaper’s site. Google “crawls” across thousands of newspaper Web sites a day - some many times a day - in order to gather news, sort articles and rank them in terms of importance.

If you scroll to the bottom of the Google News page, you’ll see this phrase: “The selection and placement of stories on this page were determined automatically by a computer program.” In other words, another algorithm automatically gathers the news and presents it on Google News.

So, the United story turned up on Google News and was (presumably) placed higher on the page because it was in the “most read” column on the newspaper’s Web site. With the missing date, Google News was only doing what it does best.

Next event in the cascade of events is a broker on Wall Street - whose business it is to act on breaking news - spotted the United article on Google News and sent it out on Bloomberg News. The broker either didn’t have the institutional knowledge that United had gone bankrupt six years ago, or he didn’t read notice that some of the reader comments at the bottom of the story were dated from 2002. He just wanted his clients to know as soon as possible so they could act on their stock holdings.

The broker’s “news” was also posted on a crawler on the floor of the stock exchange. Computer-based trading took place - by more algorithms - and United’s stock tanked. Quickly. To the tune of a billion dollars in a few minutes.

True, it was revealed within the hour that United wasn’t going bankrupt, and the company’s stock recovered that day. The details of the cascade of events were pieced together over the next few days, but some people lost a lot of money - and, I suppose, others gained - and now lawyers are hashing it out.

What’s the postmortem? Both “tipping points” in the cascade were human errors exacerbated by software. Concerning the first point - that the article didn’t have a date on it - information doesn’t write itself. The lack of a date was a programmer’s mistake. This story would have most likely would have died if the article had a date; both machines and humans down the line would have recognized it as old news.

The second tipping point was obviously human. Someone didn’t have the institutional knowledge to know that United had gone bankrupt in 2002 and didn’t check out the story before it was passed on. That mistake was exacerbated by the speed of software and by people who decided to sell stock based on the story. For more on this story read the New York Times article.

“Garbage in, garbage out” is an old programmer’s phrase that hasn’t lost its relevancy these days. Computers only do exactly what they’re told. Give them bad data, and you’ll get bad results. Or, in this case, let Google News find a hot news item with a missing date, then watch the cascade of events build on human-developed software and human mistakes.

How the Internet and the world is connected these days might be rocket science, but it’s not rocket science that these things happen. And they will happen again, because we’re human and we built the tools use - computers, software and algorithms.

“Garbage in, garbage out.” That might make a good T-shirt.

Email   Front Page   Printable Post   Share/Bookmark