The second man Mr. Allchin tapped was Amitabh Srivastava, now 49, a fellow purist among computer scientists. A newcomer to the Windows group, Mr. Srivastava had his team draw up a map of how Windows' pieces fit together. It was 8 feet tall and 11 feet wide and looked like a haphazard train map with hundreds of tracks crisscrossing each other.
That was just the opposite of how Microsoft's new rivals worked. Google and others developed test versions of software and shipped them over the Internet. The best of the programs from rivals were like Lego blocks -- they had a single function and were designed to be connected onto a larger whole. Google and even Microsoft's own MSN online unit could quickly respond to changes in the way people used their PCs and the Web by adding incremental improvements.
In April 2004, Google, seemingly out of nowhere, introduced its Gmail service, competing with Microsoft's Hotmail program. Tiny Internet browser maker Mozilla Foundation beat Microsoft to market with browser features planned for Longhorn.
Most alarming: By July 2004, it became clear that Google was working on a "desktop search" tool for finding information on a PC -- offering some of the features that Mr. Gates's WinFS program was supposed to bring to Longhorn. Google, previously focused exclusively on the Internet, was now stepping onto Microsoft's turf as the creator of software inside the PC.
While Windows itself couldn't be a single module -- it had too many functions for that -- it could be designed so that Microsoft could easily plug in or pull out new features without disrupting the whole system. That was a cornerstone of a plan Messrs. Srivastava and Valentine proposed to their boss, Mr. Allchin. Microsoft would have to throw out years of computer code in Longhorn and start out with a fresh base. It would set up computers to automatically reject bug-laden code. The new Longhorn would have to be simple. It would leave bells and whistles for later -- including Mr. Gates's WinFS, Messrs. Srivastava and Allchin say.
Mr. Allchin signed on to the plan and broke the news to Messrs. Gates and Ballmer. Mr. Allchin remembers that Mr. Gates pushed him to keep going with the original version of Longhorn, saying if the software writers needed more time Microsoft could ship a scaled-down version in the interim. The executives agreed to reserve a final decision until Mr. Ballmer returned from a business trip, according to Mr. Allchin and Mr. Valentine, who was also present.
Over the next few weeks, Mr. Gates expressed frustration. At one meeting on Aug. 17, he berated Longhorn engineers for the mess, say people familiar with the meeting. (Mr. Gates says he doesn't remember it.) Afterward, Mr. Srivastava says he called his team together, acknowledging that he had underestimated the scope of the challenge they faced in fixing Longhorn, though he was heartened by the group's apparent willingness to change.
As Microsoft's chief software architect, Mr. Gates says that his role is "almost paradoxical" because he has to push for innovation while being the "ultimate realist" when problems arise on that quest. In this case, he says he and Mr. Ballmer needed to make sure that the recommendations from Mr. Allchin's group were sound.
On Aug. 27, 2004, Microsoft said it would ship Longhorn in the second half of 2006 -- at least a year late -- and that Mr. Gates's WinFS advance wouldn't be part of the system. The day before in Microsoft's auditorium, Mr. Allchin had announced to hundreds of Windows engineers that they would "reset" Longhorn using a clean base of code that had been developed for a version of Windows on corporate server computers.
As he started to learn more about Mr. Srivastava's broader plan, Mr. Gates was concerned that the unproven tools for keeping the Windows core clean would levy a "tax" on engineers -- in other words, that they would spend so much time trying to meet Mr. Srivastava's standards that they wouldn't be able to devise innovations for Windows users. At a meeting on Sept. 8, Mr. Srivastava's team was walking Mr. Gates through the plan when he challenged them. Why, he wondered, weren't the reformers asking the mass of Windows engineers for their view of the changes?
"It was all just, 'Hey, bless this process,' which I was unwilling to do," Mr. Gates says. "They're just talking about process and I'm frustrated we're not talking about how the teams are responding to it."
By late October, Mr. Srivastava's team was beginning to automate the testing that had historically been done by hand. If a feature had too many bugs, software "gates" rejected it from being used in Longhorn. If engineers had too many outstanding bugs they were tossed in "bug jail" and banned from writing new code. The goal, he says, was to get engineers to "do it right the first time."
Recognizing Mr. Gates's concerns over the impact on programmers, Mr. Srivastava hit on a plan to win their hearts and minds. On Nov. 5, he visited the computer-filled office of Dave Cutler, a revered elder statesman among Windows engineers and a stickler for good code writing. Would he publicly throw his weight behind the new approach? Mr. Srivastava asked.
On Dec. 1, Mr. Srivastava escorted Mr. Cutler to Microsoft's auditorium where the software guru told 1,000 engineers that he had used the tools to build Windows code that was nearly bug-free. That Mr. Cutler -- famous for never attending meetings -- would emerge to back Mr. Allchin's revolution helped persuade some engineers to drop their objections.
Others weren't so easily convinced. Responding to an attendee questioning the merits of the new regime, Mr. Valentine, the enforcer, shot back, "Is your code perfect? Are you perfect? If not, you should shut up and support this effort," according to one of his team members, G.S. Rana. (Mr. Valentine says he doesn't remember the remarks but doesn't dispute Mr. Rana's recollection.)
As engineers began cooperating and Mr. Srivastava's team worked overtime to refine the tools, the quality of the code flowing into Longhorn began to improve. The time to create a new "build" fell to just a few days, allowing a faster cycle of writing and testing new code. After the Windows group was able to install a workable version of the system on their PCs four days before Christmas, Mr. Srivastava says the group celebrated by not working over the holidays.
Not everything went so quickly, as engineers grappled with the challenge of making Longhorn more like Lego blocks. Microsoft missed its June deadline for the first "beta" or test version of Longhorn. On the Fourth of July Mr. Srivastava monitored the progress on his wireless laptop, set up next to his grill as he cooked veggie burgers and teriyaki chicken for family guests. Mr. Srivastava was so preoccupied with Longhorn that he inadvertently agreed to his wife's plan to remodel their bedroom. He recalls that when he protested, she joked, "You got the Windows job. I get this. It's a small price to pay."
On July 27, Microsoft shipped the beta of Longhorn -- now named Windows Vista -- to 500,000 customers for testing. Experience had told the Windows team to expect tens of thousands of reported problems from customers. Instead, there were a couple thousand problem reports, says Mr. Rana, the team member.
And last month, Microsoft delivered a test version of Mr. Gates's WinFS idea -- not as a part of Longhorn but as a planned add-on feature. Microsoft this month said it would issue monthly test versions of Windows Vista, a first for the company and a sign of the group's improved agility.
It could take years before Windows can be as flexible as Microsoft needs it to be to pump out new features quickly. But the cultural shift is in swing. Hours after showing off Windows Vista to software makers this month, Mr. Gates in an interview noted how Microsoft's Office group is now using some of Mr. Srivastava's tools to improve its code. "It's amazing the invention those guys have brought forward," he said. "I wish we'd done it earlier."
This week Mr. Allchin announced that as part of the restructuring he will retire next year after Windows Vista is in customers' hands. In a recent interview he said his demons aren't fully exorcised. "There're weaknesses in everything we're doing today," Mr. Allchin says. "But it's such a huge step up from where we were."
Write to Robert A. Guth at rob.guth@wsj.com