EDITOR'S EYE

The World of Software Development.

October 2007

Congratulations to Giorgio Parisi, a professor of quantum theories at the University of Rome "La Sapienza" and researcher into complex systems. Parisi is this year's recipient of the the 2007 Royal Society and Academie des sciences Microsoft European Science Award, which recognizes scientists working in Europe who have made a significant contribution to the advancement of science through computational methods.

Parisi's work on the theory of spin glasses has had an important impact on theoretical computing, particularly formal neural networks and optimization. This award recognizes his work on quantum chromodynamics and spin glasses, his approach of using computers to corroborate the conclusions of analytical proofs, and to motivate further research fundamental in his field. He is also the author or co-author of books on field theory, spin glass theory, and related topics.

Parisi plans on using the 250,000 Euro (let's see, that's about $360,000 US) cash award to build IANUS, a massively parallel system machine based on a 2D array of FPGA processors with nearest-neighbor connections. IANUS will be able to simulate physical systems, such as spin glasses, for a much longer time than is possible by actual computers.

"It will significantly improve the range of complex systems that can be studied, both in the size and the time we can observe them," said Parisi. "One would be able to eliminate the artifacts due to small system size. This will be crucial in order to make predictions for real systems, because, in this case, the number of components is very large, and the observation time is much longer than microscopic time."

"The power of software is, on a practical level, helping us expand the frontiers of knowledge," added Jean-Philippe Courtois, president of Microsoft International. "Through this award and other Microsoft European Science Initiative programs, we hope to accelerate advances in science and computing, and encourage and support the scientists of today and tomorrow." The 250,000 Euro award was funded solely by Microsoft.

Posted by Jon Erickson at 09:02 AM  Permalink |

Efficient public transportation is a thing of beauty. Normal public transportation is a pain in the caboose. I was reminded of this last week in London when attending the Symbian Smartphone Show. Step off one Underground train, step onto another. From Gatwick to the Docklands, I'm here to tell you that I flogged that day pass. But then back in the U.S. and catching a bus from the airport terminal to longterm parking, I watched three empty buses go by with nary a glance. So you wonder: If London can precisely schedule hundreds of trains, what's so hard about an airport scheduling a handful of buses?

This is exactly the kind problem that Jiamin Zhao, Maged Dessouky, and Satish Bukkapatnam tackled in their paper Optimal Slack Time for Schedule-Based Transit Operations which recently won a "Best Paper for 2007" award from the Institute For Operations Research and Management Science Transportation Science and Logistics Society.

The question they addressed was: How much "slack time" should be schedulers of a bus or tram line add to keep operations from bunching up? (Slack time is extra time built into a bus schedule to accommodate unexpected delays.) In the paper, the authors note that "if slack time is insufficient, buses are unlikely to be able to catch up with the schedule when they fall behind, deteriorating reliability. But too much slack time reduces service frequency, which may inconvenience passengers."

For the simplest case, a single vehicle traveling in a loop, their algorithm gives an exact number, based on the size of the loop and the distribution of the of the travel time delay. The analysis also provides a way to approximate the effect of adding more busses to the loop.

The effects that the equations model involve human behavior that is easy to describe, but hard to quantify. For example, if trains or buses are spaced close together (less than 10 minutes apart, typically), travelers tend not to consult schedules or expect vehicles to arrive exactly on time, and buses can leave early without upsetting travel plans. If buses are an hour apart, this isn't true.

And delays tend to be cumulative. "Buses on frequent lines have a tendency to bunch…when a bus falls slightly behind schedule it tends to pick up more passengers, causing it to slow further" -- which is exactly what I had to put up with at the airport.

The author's research is based on studies that Dessouky did in analyzing bus operations at the Los Angeles Metropolitan Transit District. At the time Dessouky, who with Zhao and Bukkapatnam were members of the University of Southern California Viberti School of Engineering, measured an average slack time ratio of 0.25 on three MTA lines; a bus trip scheduled to take an hour generally was accomplished in 45 minutes, with the extra 15 minutes in the schedule built in to accommodate possible delays.

But was the 15 minutes more than necessary? Dessouky later worked with the MTA to incorporate these delay measurements into more effective scheduling, while continuing to try to build the dynamics he found into equations to find out what the optimal level might be.

Dessouky et al. use the equations to create curves to correlate average levels of delay and slack time ratios and, by further transpositions, with resulting waiting time for passengers, leading to an approximation of how much slack time is optimal, depending on total round trip travel time. The bottom line? Build in between 15 and 20 percent slack, more for longer trips.

-- Jonathan Erickson
jerickson@ddj.com

Posted by Jon Erickson at 10:02 AM  Permalink |

In the spirit of "that Erickson, he's a heck of a guy," I'm going to make you an offer that's hard to beat. Here's the deal: T-shirts, everybody loves t-shirts, right? Well I have some extra ones and I'll send you one if you will send me a photo of yourself holding a copy of Dr. Dobb's Journal magazine. It's as easy as that.

What I'll then do is include your photo in Dr. Dobb's Wide World of Programmers Photo Album. Worldwide. The photo can be in your favorite coffee shop, curry house, office, or wherever. I only have about 50 and when those are gone, that's it. First come, first serve.

To get your t-shirt, send your photo to ddj.photos@gmail.com, along with your mailing address and a short bio. Let me know if you prefer a size or color; I'll do my best to get as match up. Thanks in advance for your participation.

Posted by Jon Erickson at 08:23 AM  Permalink |

Of all of the classic computer-science problems, the Travelling Salesman Problem--a problem in discrete or combinatorial optimization--is the one I like most. Probably because it is among the ones I first puzzled over, not to mention that it is so darn practical.

In a nutshell, the problem statement for the TSP is: Given a number of cities and the costs of travelling from any city to any other city, what is the cheapest round-trip route that visits each city exactly once and then returns to the starting city?

If you've paid to fill up the gas tank of a car or delivery van recently, you know why this question is probably more relevant today than when it was first tackled more than 100 years ago. Clearly, any way to cut fuel costs is a win for the person paying for the fuel.

Which is where T.T. Narendran, a professor at the Indian Institute of Technology-Madras, and Chandra Sunil Kumar, a Ph.D. student who specializes in Logistics Management, enter the picture. What they've done is develop an update to the TSP algorithm and built a computer model to implement it.

In their paper "Heuristics for the Real-Time Pickup-and-Delivery Travelling Salesman Problem" to be published in the International Journal of Logistics Systems and Management, Narendran and Kumar assume a single vehicle operating within a region. Each day, there are calls from customers, packages to deliver, and others to collect and deliver elsewhere. Static customer requests are those that are known in advance, while dynamic requests arise as the day progresses. The vehicle starts from the depot, and moves to serve static customers according to a schedule of advance requests. As the day progresses, new requests come in and the dispatcher has to re-route to fulfill these new requests while minimizing the total distance traveled in accommodating advance bookings.

The vehicle then follows the latest determined route until a new dynamic request arrives. At that time, the vehicle is between the start and finish of the original plan. Now the plan has to add a pickup and delivery point into the unexecuted part of the plan so that the additional distance to be traveled is minimized. At this juncture, the computer model inserts a heuristic. In one method, the customer's new request is positioned appropriately between two of the places to be visited as per the original plan. In the second approach, the entire sector remaining to be served is reframed with the inclusion of the new request; this part of the problem is solved using an optimization approach.

Narendran and Kumar have tested the model computationally and found that the distance traveled by the vehicle increases with increasing numbers of new requests. However, the heuristics can work in real time and every time a new request arises, they can process the information and re-route the vehicle to keep the total distance as low as possible.

And less distance, less cost.

Posted by Jon Erickson at 10:07 AM  Permalink |

I came to London to attend the Symbian Smartphone Show, which is all about mobile phones. Alas, it wasn't a conference for mobile phones I stumbled into, but an exhibition on mobile food. I'd like to say it was because I hadn't yet had my morning coffee, but that isn't an excuse the boss will buy.

In any event, I'd just settled into a comfortable chair and was looking forward to hearing Lee Williams, Nokia's senior vice president for software platforms, talk about "New Innovations in User Experiences" when someone named Sue Ellis walked onto the stage and launched into a speech entitled "Reducing Litter in the Food to Go Sector." While it wasn't what I expected, it was interesting -- especially considering the dearth of litter bins I've witnessed in London.

But the big news wasn't my wandering into the wrong hall and getting summarily booted out because I had the wrong color badge on. No, the big news for me was Nokia's interest in "Widgets". This came across loud and clear in a discussion I had with Craig Cumberland, Nokia's director of technology and applications for software platforms. In a nutshell, Nokia is ramping up its Web Run-time for its S60 smartphone platform.

The Web Run-time is a Web application development environment designed to let you create services and content rapidly, and in general lower the barrier of entry into to mobile platforms.

Key to this strategy are widgets -- lightweight Web applications developed with familiar, standards-based Web technologies used create Web pages -- HTML, CSS, JavaScript, and AJAX. With widgets, users can personalize the content and services that matter most to them. Cumberland referred to these as "on-device" applications, adding that "anything you can do on a Web page, you can deliver through a widget." Cumberland went on to say that "widgets on the desktop are okay, but on a mobile device they are a whole different story because of the customization standpoint." (Adding that Nokia is still trying to decide if the right descriptor is "customization" or "personalization".) But Cumberland was quick to point out that the two big issues for developers will continue to be the screen size and how to program soft keys.

Interestingly, Nokia is already looking ahead to the day in which hundreds if not thousands of third-party widgets will be available for users download. In particular, the issues of widget managment and security invariably come up. Posting malicious widgets for widespread download is a concern, and Nokia is being careful about which sandbox is which. Nokia is also starting to think about ways to monetize widgets in schemes that are fair to developers, users, and Nokia. It was suggested (okay, by me) that an iTunes like approach could open up the floodgates of widget development and use. Lots of inexpensive widgets in which Nokia gets a cut for managing and the developer gets a cut for developing. It could be fun.

In the meantime, there's an afternoon session entitled "Cater for the Vegetarian Food to Go Consumer" that I don't want to miss.

Posted by Jon Erickson at 07:09 AM  Permalink |

Thanks in part to a gentle nudge (which some might call a "reboot") from the boss, I've made it to London for the Symbian Smartphone Conference. Not that I needed much nudging -- I'm pleased as all dickens to be here and looking forward to what I can learn, especially in terms of applications built using Nokia's Open C.

While the conference itself doesn't kick off (another term the boss likes to use), I've already had *almost* enough action for the week. It all started with the Delta flight out of Atlanta. We hadn't been in the air 15 minutes, when the plane's info/entertainment system went bonkers. Instead of a movie, all I could see in front was screen-after-screen of Red Hat Linux configuration info scrolling by. Now I like configuration data as much as the next guy, but not at 20,000 feet in the air. All I could think of was Hugh Thompson's talk on How To Crash an In-flight Entertainment System which I've heard one time too many. It's amusing to hear Hugh's rendition of the process, but less so to hear a flight attendent say over the plane's loud speaker that the "system is rebooting" and will be up shortly. To heck with the movies playing, let's just keep the plane "up", okay?

Upon reaching London, the first hotel I camped out at was a small 6-story bed and breakfast that promised "free Internet access." And yes, it did have wireless access as long as you were in ground floor lounge. My room was on the 5th floor. But I did discover that there was one hotspot that I could pick up a signal in the room; move it 18 inches any way, and the signal was dropped. Unfortunately, that spot was on top of my pillow. Still, it was access.

Thinking it might be a good idea to be prepared and have a handle on what and where I'll be working for the next few days, I moved from Central London to the ExCel Centre in the dockyards of London. After forking over 10 pounds for Internet access in this somewhat more grand hotel (it's on a boat -- a floating hotel, if you will), there was no access to broadband. Free wireless, of course, but in the lounge. So they moved me to another room which does have access, so I'm happy.

When strolling over to the ExCel Center, to my disappointment, the Symbian show is a day or two from being set up. But to my great amusement, the event at the venue was a hairdresser's convention by Salon International 2007 -- "three days of live hairdressing....the biggest hairdressing event EVER to take place in the UK.

When it comes to hair, my instructions to my barber (ah, he might take offense at being called a "stylist") is "short on the sides, and flat on the top." Boy was I out of my element. Still, I have to say, style-wise, hairdressers have it all over software developers. I mean, London hairstylists ROCK!

By my next posting, I hope to have some interesting technical details about what Symbian, Nokia, and others are up to when it comes to developing applications for mobile phones. But they're going to have to be good -- the hairstylists have put up a high bar to beat.

Posted by Jon Erickson at 11:57 AM  Permalink |

The problem with Netflix, large-screen TVs, and microwave popcorn is that people like me who are basically anti-social tend to get out to movies less and less. Which means, of course, we miss a lot. But luckily I didn't miss a recent movie -- King of Kong: A Fistful of Quarters, a documentary that's all about the classic video arcade game Donkey Kong. Well, actually, it is about more than Donkey Kong; it's about the people who play Donkey Kong -- I mean really play it. Competitively. Seriously. Hour-after-hour kind of playing.

Before turning to the movie, let's start with the game itself, just in case you're not familiar with it. In a nutshell, its a 1980-era arcade game in which Mario (the player) climbs ladders to free Pauline from Donkey Kong (a.k.a. King Kong). During the process of going from one stage to another, Donkey Kong tries to stop Mario by throwing barrels and other obstacles towards Mario.

What the movie "King of Kong" is about is the people who try to out do each other in attaining the highest possible scores. According to the official synopsis, the movie is about a "middle-school science teacher and hot-sauce mogul [vying] for the Guinness World Record on the arcade classic, Donkey Kong." But its really about much more than that.

Villaneous hot-sauce mogul Billy Mitchell, who describes himself as the "Darth Vadar of Donkey Kong," holds several records and has been unbeaten for decades. However, nice-guy newcomer Steve Wiebe, a middle-school science teacher from Redmond, Washington, discovers he's a Donkey Kong natural and decides to take on Billy. Then there are the long-simmering rivalies among other fans and Billy synophant, as well as people who simply have a love of the (video) game. For instance, there's Walter Day who is the founder of Twin Galaxies which keeps tab on all the world record scores for pinball and video games. Then there's Jillian Wiebe (Steve's daughter) says: "Work is for people who can't play video games."

I'm not going to tell you how it ends, but I will say that that it is as at least as exciting as the baseball playoffs and a lot more exciting than watching NASCAR or a golf match.

It was interesting that early in the film, Walter or Billy (I don't recall who) made the comparison between yesteryear's classic video games, like Donkey Kong, and today's online, graphic-intensive games, like Halo 3 which garnered $300 million in sales in the first week it was available, racking up more than 3.6 million hours of online gameplay. As Walter (or Billy) said, the classic games require a concentration and hand-eye coordination that today's games can't compete with. There's a lure to these "simple" games that's hard to top. Just as interesting the thick, dog-eared notebooks that top players like Steve and Billy keep describing in detail each and every screen in the game. In essence, they reverse engineer the game to figure out how to beat it.

And what does "kill screen" mean? Once the maximum score is reached in Donkey Kong -- the point at which the game can't tabulate any more points -- Mario disintegrates. According to the movie, there are only two or three known instances of this score being achieved. Does anyone in the "King of Kong" reach it? Well, go see the movie. You'll be glad you did.

Posted by Jon Erickson at 10:30 AM  Permalink |

At the risk of repeating myself (yet again), I want to make sure that you've heard we are making available for download the source code to Dr. Dobb's FlipBook -- the special digital edition we created using Microsoft's Silverlight.

It really is pretty cool -- video, audio, graphics, text. Of course, the first thing you probably thought was that there is way too much "me" in it, stuttering and stammering his way into the world of RIA.

But in the spirit of Dr. Dobb's Journal, we're taking another step with FlipBook -- we're releasing the complete source code for the application. That's a lot of JavaScript, XAML, and the like. Since FlipBook was built within Visual Studio, the usual suspects do apply.

What we didn't include was the video and audio files of your's truly (among others). Only the text articles remain. So what you have is essentially a framework for building your own FlipBook-like applications. And when you do so, I'd love to hear -- and see -- what you come up with. So when the time is right, keep us in mind. Of course, you might end up using only snippets of the overall code, or just reading the code to understand how the thing works. That's okay too. Let me know.

To download the source code, all you have to do is go to www.ddjsilverlight.com/flipbook/ and click the appropriate button. Have fun, learn, and enjoy. This is the fun part of the project.

Posted by Jon Erickson at 01:49 PM  Permalink |

If you've been looking for yet another reason to fan the "is it art or is it science?" flame, take a look at the American Mathematical Society's Mathematical Imagery page. Now I don't know a lot about math, but I know what I like -- and that usually means a balanced checkbook. And let me tell you, there's an art to making that happen.

But in the grand scale of things, is mathematics an art or science? Don't answer that too quickly, at least not until you've had a look at math imagery like that of Robert J. Lang, an artistic mathematician who specializes in origami -- paper folding, in other words. Remember those paper airplanes you used to throw around in 4th grade? Forget it. Dr. Lang's mathematical origami isn't like that.

While his origami says he is an artist, Lang talks like an engineer. Which isn't a surprise, since he trained as physicist and holds 40 patents on semiconductor lasers, optics, and integrated optoelectronics. But here's what he has to say about origami:

The intersections between origami, mathematics, and science occur at many levels and include many fields of the latter. We can group these intersections into roughly three categories:

• Origami mathematics, which includes the mathematics that describes the underlying laws of origami;
• Computational origami, which comprises algorithms and theory devoted to the solution of origami problems by mathematical means;
• Origami technology, which is the application of origami (and folding in general) to the solution of problems arising in engineering, industrial design, and technology in general.

Origami math defines the "ground rules" for computational origami's goal of solving origami design problems (and quantifying their difficulty). The results of computational origami, in turn, can be (and have been) pressed into service to solve technological problems ranging from consumer products to the space program.

That sounds like a lot of engineering to me, even though his origami is unquestionably art. (This reminds me of a stained-glass window I commissioned from a local stained-glass artist a few years ago. It turns out that he was a trained aeronautical engineer, who incorporated aircraft engineering principles in his windows to add lightweight strength to large windows.)

But Lang isn't the only artist/engineer who blurrs the distinction between art and science, and he isn't the only artist/engineer you can see at the Mathematical Imagery page. So what do you think? Science or art? And have you changed your mind?

Posted by Jon Erickson at 10:04 AM  Permalink |

According to a recently released survey from the SOA Forum (an organization of enterprise architects founded by automated SOA governance vendor WebLayers), organizations are more often than not implementing Web services without performing any type of compliance review. And when they are conducted, those compliance reviews are inconsistent or undocumented manual processes rather than rigorous, automated reviews.

Among other findings, the survey reported that:

• 88 percent of respondents feel their current SOA governance is not sufficient.
• 85 percent of companies depend on manual reviews in design and development stages to try to achieve architectural governance.
• 80 percent of companies feel that their organization is at measurable or large negative risk due to putting services in production that are not effectively governed.
• Significant dissatisfaction was reported when a registry/repository is deployed without policy management and automated enforcement.
• 56 percent report that half of their services are not reviewed for compliance at all before moving into production.

The issue of manual versus automated review was central to the survey. Those respondents who had automated the governance process said they are able to check at least 75 percent of their artifacts for compliance, and one third check 100 percent of their code and artifacts for compliance prior to implementation. Moreover, 100 percent of the respondents using automation state that their governance process is not an obstacle to their developement teams.

Additionally, of the responding companies that have more than 50 services in production, 83 percent rely on manula design and code/artifact review, while 54 percent use manual pre-registration checks. Of these companies, 42 percent have less than 10 people responsible for manul review processes.

Responding companies that are using automated policy enforcement are claiming higher success rates:

• 89 percent of companies using automated processes share governance policies across different operating groups or divisions within the organization.
• 86 percent of all companies using design-time automation claim that their governance processes are not an obstacle to their development process.
• 75 percent of these companies have over 50 services in production.
• 63 percent of these companies also leverage automated runtime monitoring.
• 88 percent of companies review over 50 percent of their services before moving them to production, with 50 percent of companies achieving 100 percent coverage of their service compliance reviews before moving them to production.

Organizations with 50 or more services and using automation claim to be seeing higher success rates in their SOA implementation.

The survey was conducted in May of 2007. Responses were solicited via email from the 1,300 SOA Forum members, with more than 500 respondents.

Posted by Jon Erickson at 10:59 AM  Permalink |