RE: Grand challenges for software engineering

Rohit Khare (
Wed, 4 Aug 1999 05:27:12 -0700

[Hint for FoRK readers: we're having a discussion about new
"grand-challenge" problems for motivating research investment in
Software Engineering. One professor in our group replied that such
challenges -- such as Apollo -- are not usually stated w.r.t. a
single scientific discipline.]

[ I am ACTIVELY seeking encouragements/brickbats/comments so that
this outline finally reaches escape velocity -- unlike so many other
munch-rants -- becomes polished enough to become a personal
plan/mission statement that can be debated much more widely]

>(1) most people could agree that there was a
>benefit to achieving the goal (vague though the anticipated benefit may have
>been), (2) it was very easy to measure progress toward and completion of the
>goal, (3) its achievment required research in several scientific
>disciplines, (4) many of the innovations that came from the different
>disciplines could not be predicted at the time the goal was stated, and (5)
>the goal was not stated with the purpose of benefitting a particular

OK, in that vein, let me restate my life's-work :-)

"Every person on the planet has a right to communicate freely with anyone else"

Let us take the challenge of bringing telecommunications to the other
four billion humans on our planet, bringing with it knowledge of the
whole wide world and the liberating power of imagination that comes
with it. No person should be without the security of a lifeline to
his or her community, nor denied the news and information needed to
make his or her life better.

Munchkins, a Grand Challenge Problem

"We should commit ourselves to developing a $1 chipset that can relay
messages in an ad-hoc, peer-to-peer, planetary-scale wireless
network. Such a network should be fair yet self-supporting, allowing
users to "own" rather than "rent" network access. We will use this
platform to bring basic telecommunications to every human community,
and the software principles behind it to eliminate network
configuration & administration from the scale of PCs on a LAN to
microdevices within a minefield or vending machine to software
components within distributed applications. We will also develop new
software architectural styles to exploit global messaging and event
notification, to truly build a "mirror world" in cyberspace to better
understand and manage the real one."

Let me pause to cite SF writer Arthur C. Clarke's standing wish: that
as humanity's millennial birthday gift to itself, it abolish
long-distance telephone charges. Originally, I recall it being "free"
(ca. 1958), but as of 1992, it was moderated to 'flat-rate':

>WIRED: Incredible to think that it's been close to 50 years since
>you came up with the idea of communications satellites. What do you
>see as the next natural - or inevitable - step that we'll be taking
>in terms of global communications?

>ACC: The personal telephone. I mean, it may be a waist-belt, but
>that's it - when everybody has his or her own personal
>communications devices. The end of the telephone as a fixed
>instrument. It's started with the cellular telephones, and it'll go
>farther with the cellular satellite telephones.

>WIRED: You suggest in your most recent non-fiction book, How the
>World Was One, that telecommunications companies ought to celebrate
>the year 2001 by abolishing all long-distance phone charges. Do you
>think the phone companies are taking this proposal seriously?

> ACC: There'll be so much more business if they do. We've been
>through this whole thing already with the Penny Post. Charles
>Babbage, the father of the "difference engine," worked out that the
>cost of sending a letter was independent of the distance it
>traveled. In those days, every letter was charged a different rate
>depending on how far it had to go. There were armies of clerks
>working it out. Mail was very limited and very expensive. But once
>they had a flat rate it multiplied, and totally transformed the
>postal service. It's a similar thing with long-distance calling.

Yes, this means bringing "bandwidth" to every corner of our planet,
but our success will not be measured in channel capacity alone.
Unilke Apollo, we cannot "buy" a solution to this problem: it is not
in merely extending the current infrastructure of telephony and PC
networking to ever-greater numbers of people. Frankly, there is *no
business case* for wiring up the 80% of us who produce less than 20%
of the wealth on the planet. Phones and PCs as currently framed will
never become "cheap enough" for the masses, since it's always going
to be more expensive than food and shelter. Nor will "buying" the
solution -- a Teledesic terminal for every village, say, which is
only a 5Mx$2,000 = $10B problem -- really be a solution, since this
will be rented bandwidth, payable every year to a small oligopoly of

No, the key is shifting the info-peasants of the world from
sharecropping & tenancy to landholders: *giving people renewable
generators of bits rather than leases on bit-service*. This is not
the Internet we know how to build today, with its "upstreams" and
"downstreams" and un-settled peering. Routing, root name servers,
backbones are all centralized and rented resources.

Now, before we fly off in pursuit of fantasies such as
self-assembling, bartering, social networks, let's try a Grand
Challenge reality check: we should believe that the goal is
*possible* even if we don't know *how* to reach it.

From birth, communication in human communities manages to proceed
without 1) central registration and with 2) fair security between 3)
trusted subgroups. Yet, in extremis, anyone on the planet can reach
the attention of any other 4) within only a few degrees of separation
(classically, 'six').

Recall, though, that neither the Internet nor classical telephony
networks quite map onto this human network. Only a small fraction of
people have telephone numbers, nor does global, centrally allocated
addressing seem feasible when many kinds of human communities barely
even allocate unique identifiers amongst themselves ("you may be one
in a million, son, but there's still a thousand Indians just like
you..." ;-).

Now, onto question (1): is there a benefit to this GC? Yes, of the
sort we can already prototype with, say, Grameen Bank's micro-capital
loans to equip Bangladeshi villages with cellphones: increased
personal security, political representation, and economic efficiency.
That's just person-to-person communication. Access to libraries,
video, and other cultural media should accelerate such growth.
Second-order effects may include greater social mobility (being able
to marry into the next village over), but also perhaps greater social
control (if the network is too central or surveillable) and greater
economic competition (outsourcing service work to the Third World).

Second, is progress easily measurable? Yes, especially with the kind
of grand-challenge 'device' I propose below: cost, penetration,
ease-of-use, and actual use will all make effective project metrics.
More to the point, such metrics will help sort competing proposals
and prototypes in the development phase: how many million
non-interfering nodes can this radio support per square kilometer?
with what user interface affordances? at what cost?

Third, is it interdisciplinary? Yes. In a narrow technological
context, such a goal requires simultaneous progress in at least:
* wireless communications (radios, access control, power)
* user interfaces (speech, internationalization, lifestreams,
* distributed computing (naming, addressing, and routing)
* software engineering (event-based decentralized applications, *TP)
* economics & game theory ( market-based allocation & valuation)
* electrical engineering (asynchronous and analog VLSI)
* materials science & manufacturing (to achieve $1 cost)

Furthermore, non-engineering dimensions are critical as well:
* political science & law (ensure democratic limits to use)
*anthropology (to monitor adoption & adaptation in use)
* business process (to take advantage a vast, but marginalized, market)

Fourth, do we know what innovations to expect in each domain? Fifth,
are we targeting only one domain? I believe the answers are negative
for both, but we still have enough landmarks on the horizon to map it
out. There is a pair of critical innovations this project rests on:
ad-hoc ultrawideband networking (already in progress with good
momentum) and ad-hoc network applications development (largely
missing). Yet the consequential developments ("spinoffs") could be
numerous and wide-ranging for the Rich world, too: vastly improved
search, social navigation, presence, displays, security, and
micropayments, at least.

So what's a cogent protrait of this grand-challenge device we want to build?

[Nova Express Cafe, 12:50 AM. A black-lit, alien-themed
pizza-n-smoothie joint open til 4AM, across from Cantor's deli on

I had tried writing this section before, but lost it in a system
crash. That's actually for the best, all considered. I had written a
day-in-the-life scenario for a villager with a cool hardware
pendant-communicator. You know the type, the Popular Mechanics-style
centerfold model of the future: credit-card size flexible polymer
with LEP color display on one face, solar-cell polymer battery on the
other, and a cpu, ccd, microphone, antenna, and GPS etched between.
An uber-PalmV, so to speak. It sounded like the kind of earnest BS we
shovel all the time. See, for example, the "Proud Worker" commercial
from 3Dfx:

In fact, my scenario utterly failed to differentiate this grand
challenge from mere extrapolation of IPv6-based "deeply networked
systems" -- all of it was conceivable in the current technological
frame. No, the only delta bit was that nobody paid monthly fees, or
per-bit fees, or per-page fees -- and yet, there was economic
settlement throughout.

Since I'm stumped at the moment, let me try to at least list some
requirements I have in mind. I will try to sort them from most basic
to most general, in three categories: "network", "transport", and

1. Munchkin Network Services

The network layer is intended to isolate the munchkin from any
details of the underlying transport (IPv4, mobile IP, IPv6, acoustic
coupler, fax, etc). Let's treat the "real" network as merely an
asynchronous message delivery service, one that requires *link*
addresses, like today's telephone numbers or IP numbers. Admittedly,
we are abstracting away real-time, broadcast, and signalling ("push",
"urgent") semantics from our links.

* Public-key Addressing

The "bottom turtle," as it were, for our "superimposed" network is a
*device* address, not a link address. It's a fundamental tenet of IP
that we number *interfaces* to a host, not *hosts* themselves. That
is to say, on either side of a router, users will see different IP#s
for each attachment point.

Instead, let's postulate that every device is "born" with a unique
keypair, which becomes a 2,000-bit universally-unique identifier. Not
one allocated from a central, "coherent" registry, but chosen at
random with statistical bounds on collision probability nonetheless.

This way, my digital camera will have the same "address" wherever it
pops up in real space, whether its IP has changed (different ISP), or
is forwarded (Mobile IP, cellular forwarding), or is using an
entirely other network (wireless directly to my laptop, say).

[advanced note: of course, to protect keys, and allow "resale" to new
owners, the actual device private key, generated by random noise at
burn-in, forms the root of a mini-key hierarchy. E.g.having the
camera's key sign the key corresponding to the lifetime of my
ownership of it.]

* Self-Centered Namespaces

Names are an indirection upon (groups of) addresses. Munchkins shall
each have a self-rooted directory of names.

These addresses form the bedrock for our naming system. I shall hold
my camera up to my laptop, verify that they display each other's keys
correctly, and proclaim thusly to both, "I deem 37 to be 'Rohit's
Camera'". [This is intentionally quite PGP-like]. To make this
statement, though, I also need to define the abstract entity
"Rohit", by generating another keypair on my Laptop, and naming it
Laptop's Rohit, and thus in turn naming the camera Laptop's Rohit's
Camera. It will take a great deal of usage before a community of
devices all owned by me can use the prefix "Rohit's" in shorthand,
since the Laptop remains where this identity was born, no matter
however many subsequent organizations attest to its Rohitness....

Suppose I use the public keys 37, 43, and 51 for the camera, laptop,
and "Rohit" in this extended example. Thus, the final states ought to

camera believes Self->37, Self's Rohit->51, Self's Rohit's Camera->37
laptop believes Self->43, Self's Rohit->51, Self's Rohit's Camera-> 37

[Note that the laptop does not have a name yet...]

* Trust Management

To reach that final state, some message has to be delivered to both
devices proclaiming the new name, say "Rohit's Camera is 37, (signed)
51". How will both devices trust key 51 to speak for new entries in
the Rohit namespace?

... the answer is that somehow both devices must have been told that
Self's Rohit, as nominal "owner" is always-trusted for the "Rohit"
namespace. Following precisely in the vein of PolicyMaker, KeyNote,
&c, the *key* 51 shall be granted the authority to make these

Of course, there will be a variety of trust levels less than
"absolute", and myriad aspects of trust (such as capabilities to add
new names, execute methods, spend money, etc). For that reason, I
postulate an "absolutely-secure" trust management subsystem is part
of the platform, ideally guaranteed through hardware.

*Relay Auctioning: Every Link a Market

Suppose I want to broadcast that new-name announcement on a shared
wireless channel. I will be taking something from the common good,
because I will exclude others from speaking while I am speaking. The
best way to allocate such costs is through... costs. That is to say,
every link in the network is its own currency, its own internal

Forget the wireless part. Let's clamp it down to a serial cable -- we
want munchkins to parasitically reuse any kind of channel it can
find, from Bluetooth to $10/minute airplane satphone, after all. The
100Kb/sec channel is like an oak tree, dropping a hundred acorns to
the ground every season. For our purposes, the 100Kb is "free" much
like the oak's production is "free", from sunlight and CO2. Perhaps
differently from the squirrels, though, these "acorns" rot after a
period, though -- bandwidth is a use-it-or-lose-it proposition.

... nifty explanation that escapes me as yet... I suspect it has
something to do with modeling the channel as a series of
interdependent markets -- send now, or sent after one-slot delay,
after two-slot, kind of like a bond ladder, and then using option
pricing on the result, to price different baskets of (bandwidth,

At any rate, market-based allocation of scarce resources -- even for
a step-function-cost good (zero marginal cost until saturation, then
infinite) -- is a reasonable research agenda many people are looking
at, including the DARPA Fault Tolerant Networks program.

... but the key is tying the market-price of bandwidth to the *value*
of the information committed to it.

Suppose that after a six-hour flight composing memos great and small
-- a sell order to my broker and a video-mail to mom -- I arrive at
the airport with five minutes to dial in. I'd like the network to
auction off that scarce bandwidth internally to the queued messages
of greatest value: the sell order first. This is quite different from
measuring bit rates, to promulgating a consistent measure of value
all the way up to the application, indeed, to the UI.

It's worth observing that, in the long-run, link "cost" should be
shared by relative usage. So if there is an equal amount of "value"
transferred between two devices, barter should equalize the cost. If
one side transmits disproportionately, it may have to buy bandwidth
credits on the spot market (MCIbucks, say) to compensate its
counterparties. This is one way in which real money may intersect
with this virtual currency. Thus in the long run, if the network's
average diameter is N, a user should be able to speak 1/N as often
as they relay others' packets for "free".

Somewhere in here is the key to bringing munchkins to the other 4
billion: it's the difference between having acorns and having an oak.
Right now, we pay utilities, who sponsor the cost of links. If
everyone owns their own link -- can contribute to relaying packets --
then access costs collapse to the marginal cost of operating the
link. It's like replacing nuclear plants with personal fuel-cells and
batteries, buying and selling electricity from the grid as optimal
for your use. If, overall, your usage is the same as your fuel-cell's
capacity, you should not owe the grid anything.

[Astute readers may quip that so far, I have reinvented FidoNet and
UUCP. This is even more true than it seems -- the future of the
connected Internet may lie in the past, disconnected,
everyone-pays-their-own-modem-share BBSes.]

* Bounty Delivery

Bandwidth alone is not the service we're selling, though. It's the
successful delivery of stamped mail. If you simply tape pennies to an
envelope, though, and allow everyone who handles it to remove one,
you're going to run several risks: fraud, insufficiency, and worst of
all, latency, as each party holds on the the envelope for a few
seconds or days, hoping to run into the ultimate addressee to collect
the remaining share. The Pony Express was a systematized form of the

But electronically, we can duplicate opaque cryptolopes and offer a
bounty to whomever confirms delivery. My sell-order may have ten
times the going rate posted, in hopes ten parties, not one, will find
it worthwhile to attempt delivery. This may not make sense on today's
connected Internet, but those who recall the variable propagation
times of old USENET might see the differences of choosing your
ingress ("posting") point -- and even of posting the same msg-id to
several locations at once and flood-filling the netnews relays in

But wait, how can I deliver the message signed 51 without 1) knowing
I can trust 51 to pay up and 2) knowing who 51 is to guess what
direction might get it "closer"? The former problem seems to augur
that *every* munchkin has to agree to some common, secure,
currency-settlement algorithm. This might range from a
burned-in-hardware secure "money coprocessor" (a la Cox's
_Superdistribution_) to a reputation-based system where credit is
freely extended until a consensus to blacklist a key emerges. Note
that I'm not predicting a 'gold standard': choosing a single
ultimately underlying currency; but rather, a 'banking system' with
all the sorts of credit checks and risk underwriting we'd expect.

* Decentralized Routing

The second problem is the crux of the whole system, though. There's a
damn good reason we don't use public-keys as addresses today: routers
rely on the internal structure of IP addresses to map out the
network. They need to look up, on-the-fly that "17-22 is on my right,
23-99 is on my left". Replacing two compressed entries with 100
individual entries ("camera last seen at LAX") is suicide for
high-speed, "core" routers. I'm gambling that 1) there's vast enough
storage at leaf-nodes to maintain entirely private self-centered
naming and routing tables and 2) making every node a router reduces
the 'hotspot' dependency to a lookup rate proportional to one's "own"
usage instead of 100-1000 clients' aggregate demand.

[I consider it a requirement that munchkin-networks function with
homogenous parts: that there are no "privilged" viewpoints from 100x
more powerful "routers" ]

Yes, the net-effect may be that mail from me to Steve Case won't take
a single transcontinental leap to, but in fact traverse the
meandering six-degrees-of-separation path mirroring my own social
friendships with people who might be friends of Steve's -- I will be
sacrificing global routing for shards of partial, relative views of
the network. At the same time, email from me to my boss might just
hop over six feet, rather than following some administratively-set
MX-record chutes and ladders back-and-forth across the continent four
times.... that's the breaks of self-organizing networks.

2. Munchkin Transport Services

What kind of interface will we offer "end-user" applications, then?
Today, there's an expectation streams/sockets are the end of the
line. In fact, I think end-to-end isochronous channels are too
strong, and we need a looser asynchronous abstraction for
event-notification and message delivery. This is an endorsement of
the REST architectural style of Fielding's for programming munchkin

* *TP ("star-tee-pee")

The main unit of conversation across the kernel boundary of our
munchkin meta-OS will not be bytestreams, but *representations* of
object state as messages to a (group of) name(s). Ideally, having
signed, encrypted, and stamped the envelope, economic rules will
automatically govern the selection of propagation flows, which range
today from point-to-point push (SMTP) to point-to-multipoint push
(NNTP) and multipoint-to-point pull (HTTP).

The relevant technology development here is a 'risc-http' for
labeling bags-o-MIME-typed-bits and the cache tags, destination
names, and so on that bridge existing TP choices.

Instead of SMTP queues, NNTP spools, and HTTP archives, I envision a
homogenous mesh of storage space, also market-allocated, that should
handle flash-crowds and migration.

* Event Notification

Another abstraction, in place of "pipe" and "socket" is "event
channel". It's an abstraction like "opening"
/event/I-405-freeway/miles-23-to-47 instead of /dev/traffictelemetry.
Of course event notifications are just messages, so *TP and
financially-grounded QoS still make sense. It's just that the
destination of the notification isn't an endpoint like "Rohit's
Camera" or "Rohit's Pager", but to an abstract event-channel (which
might also match another listener's profile at
/event/I405-freeway/miles-31-to-65 ). Actual delivery is
intermediated by subscriptions, akin to the group management
challenges of today's Multicast applications.

Also, abstraction functions ("summarizers") can also apply to event
flows: ten square-mile weather reports can be profitably replaced
with a 10-square-mile update. As discussed in our internet-draft
following WISEN98, event-ordering , (limited) event-memory, and
event-revocation could be additional services.

3. Munckin Application Services

Here's where the actual use of munchkin-based device happens:
picture-taking, printing, battlemap updating, workflow, even stashing
away a lifestream of data. XML-based ontology reconciliation emerges
to support the "Semantic Web" Tim Berners-Lee has hypothesized.
Privacy management is another horizontal service, tracking
who-knows-what as need be. User-interfaces for trust-management are
a critical open area, especially in illiterate communities, forget
computer-illiterate. Accessible, declarative, multimodal user
interfaces for such widely-deployed devices will also consume lots of

A fine question is whether the whole munchkin abstraction suffices
recursively, to represent individual components (C2-grain) within a
software system rather than just whole devices. [Adam: link to oSpace
talk from 3/95]

[It was at this point that I finally wrote down my initial
"SUMMARY"... 3:12 AM]

Next steps:

Time to get some WinCE devices, 802.11 wireless Ethernet cards,
Ricochet transciever modems, an Apple Airport, and start coding up a
*TP store... I'm beginning to envision how we can prototype munchkins
with palmVs and palmVIIs, building a without Palm's per-bit
monthly fees and centralized clipping services... localizers and
other technology is maturing well enough: we need to start figuring
out how to program them, the software engineering of deeply networked