accesses since February 23, 1999
copyright notice
link to published version: Communications of the ACM, May, 1999
accesses since February 23, 1999Here we are 6 months out and counting down. We've already seen glimpses of things to come:
The Web, newspapers and magazines are replete with similar stories. And there is every expectation that these sorts of things will continue for the immediate future. Examples might include:
Of course, the gloom-and-doom forecasters see things in a very different light.
As we showed in an earlier column (CACM, March, 1998) the generic problem underlying the Y2k or "millennium bug" is actually an inductive, logical fallacy. This "new riddle" of inductive reasoning (aka, Goodman's Paradox) derives from the fact that we cannot always distinguish law-like regularities from contingent or accidental ones. We blithely assumed that an operating system date stamp satisfied the predicate "___ is the current date on the Gregorian calendar" when, in fact, the predicate was "___ is the current date on the Gregorian calendar only before time, t; and not thereafter." The accuracy up to this point in computing history has been contingent and not law like. In the normal course of events, this would be confirmed at t = midnight, December 31, 1999. Literally billions of dollars are being spent to avoid this result. It is, in the end, the same sort of short-sightedness behind the 5-digit automobile odometer: as it was inconceivable in 1920 that any car would last 100,000 miles, so it was inconceivable in 1959 COBOL legacy applications would still be in use in 1999?
The Y2k problem is actually a hydra-headed monster which rears it's ugly head in multifarious ways. For one, even if a patch handles the year 2000 transition, it may not handle the leap year. Our astronomical year is 365.242 days on the Gregorian calendar. Falling short of 365.25 by .008 days/year causes big problems over time, so three-fourths of the century years are common (i.e., non-leap), while those evenly divisible by 400 - as in the year 2000 - are leap. So any enduring Y2k fix, has to accommodate the leap year status in 2000 denied it's century predecessor, 1900. Every year evenly divisible by 4000, in contrast, is a common year despite the fact that it's also evenly divisible by 400. Just think, our descendants may teleport themselves around the universe in search of quick fixes for the Y4k bug.
As another illustration, even if the Year 2000 problem disappears, we will still have to deal with the sister problem of calculating the "elapsed time in Unix.". A manual might say that Unix function x produces today's date in Register 1. In fact, it won't "report" the date at all, rather it will "calculate" the date on the basis of the number of seconds which have expired since January 1, 1970, until count, t = 2**31 (assuming the sign bit is retained, this is January 18, 2038). Just as with Wintel machines, we naively designed our computers for projectable predicates, but actually implemented non-projectable ones in hardware.
There may be several layers of Y2k problems. In my earlier column, I used DOS as an example. Not only does DOS not roll-over automatically to the 21st century, it only recognizes dates reported by the real-time clock that fall within the interval 1980-2099. We observe that this only appears ad hoc and arbitrary until one traces back the origin of the PC. This gets even more convoluted when one looks at FILE_DATE values. In this case, the reported date is a compression of the DOS reported date according to the formula ((year-1980) x 512)+(month x 32)+day. Hence, December 31, 1999 becomes the unsigned word integer 279Fh (10,143). It is interesting to note that the roll-over for the file date would actually be 1980+2**7 years=2108, but since DOS will only recognize the 19th and 20th centuries, the file date will be undefined under DOS beyond 2099. As I observed before, the inductive fallacy which underlies Y2k is to be found in our hardware and the inner-most recesses of our BIOS.
Still another example involves the lack of orthodoxy when it comes to four-byte REPORT_DATE standards (ISO, Microsoft, European). There are several in use, all incompatible with one another, which will continue to present headaches long after the aftertaste of Y2k has past.
The following categorization of Y2k fixes is adapted from Capers Jones article "Finding Time for the Year 2000 Repairs" (see URL below):
1. Replacement of non-compliant applications with compliant ones. Most appropriate with popular, commercial software such as productivity applications and utilities. Advantage: simplicity and economy (assuming that everything goes according to plan). Disadvantage: applies mostly to popular, commercial software.
2. Repair of non-compliant applications. Most appropriate with proprietary and legacy applications. Advantage: infinitely customizable. Disadvantage: probably not enough time left to handle large systems.
3. Termination of non-compliant programs on an as-needed basis. Advantage: this is a real managerial no-brainer, and it may be the default strategy after midnight next New Years eve. Disadvantage: it will require that automated processes be done manually or partially during the repair cycle, which will be very expensive.
4. Masking the data exchange between applications rather than try to fix the applications themselves. Masking consists of several forms, including
a. Pivoting. A pivot year is the internally-defined boundary that software uses to distinguish between the 19th and 20th century. For example, if the pivot year were chosen to be 29, a program could interpret any two-digit date within the range 29-99 as 19xx; else, 20xx Other fixes have set pivot years at 30, 40, 48, 51 "current + 20","current + 70", 1980, and so forth. Of course, these application-specific fixes have to all have to cooperate with each other. The test case will be the import and export of data between applications with different pivot dates - which should produce some excitement.
b. Conversion of the two-byte date field into some other form. For example, 16-bit binary enumeration beginning at year 0 on the Gregorian calendar would carry us through for another 60-odd thousand years. The problem of course is that everyone has to agree to the convention, and it's not likely that this agreement will surface in the next six months.
c. Encapsulation of date exchange information between application and data. To illustrate, the shift of a date downward by a multiple of 28 years mirrors the day-date correspondences of the current calendar. So, an application might retrieve the date of 03 from a file, reduce it to 75 for internal processing, and then convert it back by adding 28 back before storing, thereby avoiding any Y2k collision (hopefully).
d. Creating Redundancy across a databases so that applications will only run on them if their date fields are the same size. An obvious downside is that this technique consumes twice the space until everything converges on the 4-digit date field, but this pales in comparison with the enormous difficulty of keeping the databases synchronized.
e. Object-code Interception which is predicated on the assumption that the internal representations of dates is irrelevant if we can intercept, change and maintain them as they are shared across applications and systems. One of the most innovative ideas for object-code interception is to be found in Bob Bemer's clever Xday (eXchange day) proposal discussed below.
Bob Bemer is a genuine computer pioneer. Among his many advertised accomplishments are the first use of the ESCape sequence, the creation of ASCII, and coining the term COBOL and inventing its "Picture Clause." Since 1949 he's held prominent positions with IBM, Honeywell, Bull and General Electric to name but a few. Having been bitten by Y2k fever, Bemer came out of retirement to solve the problem. While his product, Vertex 2000, uses an object-code interception strategy, it's independent of Bemer's Xday strategy discussed here.
Bemer was early to recognize that a Y2k fix can take one of two strategies: internal (e.g., converting 2-digit date fields to 4-digit fields) or external (e.g., object-code interception). As it turns out, the former solution is more difficult and permanent, while the latter may be easily implemented but ephemeral. However, given this late date a quick fix with just a century's breathing room would be of enormous value.
That's where XDay comes in. Bemer observed that if we substitute for our Gregorian solar calendar a variant of its Julian parent, we have a unique way of representing each day into which every conceivable date format may be mapped. 1 A.D. is Julian 1721475. 1900 A.D. is 2415021. 2000 A.D. is 2451545, 2400 A.D. is Julian 2597642. Coincidentally, Bemer observes, the most significant digit in the Julian date stays unchanged for 27 centuries, with 15 centuries remaining (Figure 1). Assuming that Y2k will no longer be a problem in 3500, we imply the first digit without reservation.
FIGURE 1: Gregorian vs. Julian Dating
Now the magic comes in. Bemer points out that the next 2 digits of XDay (Julian date sans leading digit) fall within the range of 45 to 99 until August 14, 3501. This has enormous consequences for his object-code interception strategy, because these two digits cannot be confused with existing day, month or year values, regardless of the cultural format or order in which the fields appear (Figure 2). A collision could have occurred when 43-10-03 would have corresponded with XDay of 431001, but that's not much of a clink in the armor as it pre-dates the computer era.
FIGURE 1: Conflict-free XDating
As if that isn't clever enough, it also turns out that XDay occupies the same 6 digit space which is used for existing date formats, so it can be used interchangeably. If one has the time and energy, the XDay value could actually be used to replace the problematic date fields (ala' replacement strategy discussed above). On the other hand, it will also serve well (and is really intended) for object-code interception since it can't conflict with other other date fields in data streams. Of course, the interchange requires some arithmetic (related algorithms may be found at www.software.ibm.com/year2000/tips15.html. We note that Xday = LillianDay + 299160), and there has yet to be a reliable estimate of overhead, and there are sundry implementation issues to be resolved, but none loom large enough to detract from Bemer's brilliant idea. Unfortunately for all of us, it's an idea whose time has not yet come - and time is running out.
I would be remiss if I failed to also mention that XDay methodology is a public-domain resource which involves no proprietary or patented ideas or concepts. As such it is to be distinguished from the "Y2k Silver Bullet Patent" (#5,852,824) which was issued to Roger Brown by the U.S. Patent and Trademark Office as as this column goes to press (Feb, 1999) which involves proprietary encapsulation routines, and an even earlier patent (#5,600,836) was awarded to TOPS (Turn of the Century Solution) in November, 1995 for another encapsulation routine.
As the sidebar shows, there is no shortage of information on Y2k on the Web, ranging from alarmist documents ravings to corporate repair strategies. For most of us who fall into the category of millenia moderates, Y2k is expected to be a major inconvenience - which some authors have likened to a granddaddy of all brownouts, a flood of the century, and an ice storm to end all ice storms. Such being the case, we'll have a considerable mess on our hands. But life as we know it will go on, and Y2k, too, will pass. Should that not happen, I herewith reserve the right to withdraw this statement and to deny under oath that I ever made it.
Our Web Ferret meta-level search engine found 4,000 URLs matching the query "year2000" or "Y2k" before my connection timed out. Here are a few dozen of them that I found interesting.