Understand()

A Philosophical Argument for P != NP

2006-10-31T17:46:00Z

David Levin sent me a link to a great blog post that talked about the question of whether P == NP. From the post:

More often than I can remember, I've been asked some form of the following question: "If you computer scientists can't prove P=NP or P!=NP, then why aren't we justified in believing whichever one we want? And why is the 'consensus' that P!=NP anything more than a shared prejudice -- something you repeat to each other so your work won't seem irrelevant?"

The author then goes to offer 10 arguments for why it's overwhelmingly likely that P != NP.

I found the Philosophy Argument (#9) to be truly beautiful:

If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in "creative leaps," no fundamental gap between solving a problem and recognizing the solution once it's found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett. It's possible to put the point in Darwinian terms: if this is the sort of universe we inhabited, why wouldn't we already have evolved to take advantage of it? (Indeed, this is an argument not only for P != NP, but for NP-complete problems not being efficiently solvable in the physical world.)

It's beautiful for many reasons. First, the analogy itself is beautiful. Second, it's self-referential -- after reading it, I was struck by its elegance and surprised that I had never seen it in that way. But, of course, that's the point -- it's very hard to formulate such an analogy, but it is comparatively easy to appreciate it.

Very nice indeed.

Facebook Redesign & New Job

2006-09-06T15:42:00Z

Yesterday, the Facebook launched a redesign of their site that included two new features -- News Feeds and Mini Feeds.

In short, I thought the features were absolutely brilliant.

Ever since I graduated college (2002), I've basically had one overarching goal around computers and technology -- figuring out ways to help people maintain and grow interpersonal relationships. The impetus is fairly obvious -- at college, I was surrounded by some of the most amazing, kindest, and most brilliant folks in the world, and I wanted to make sure that I didn't lose that once I left.

Every so often at Microsoft, a group of folks are asked to come together as a group and pitch an idea to execs. About three years ago (and again two years ago), I gave basically the same pitch -- I had a friend in college (Al Cho) who was basically the nicest person I've ever met. Once we graduated, I largely lost contact with him. I'd get periodic snapshots of where he was (studying at Oxford, working at the U.N., etc.), but I'd lost a recurring touch. I wanted an app that helped me keep track of all my friends in one place. It would have blogging, photo sharing, friend-of-friend, events, mobile phone integration, maps integration (e.g., see all friends in a certain area if you're traveling ...), etc.

Friendster had some of that a few years ago, but it was painfully slow, etc. And then Friendster slowly atrophied. I think people just stopped having a reason to come back once it lost its novelty. But that's because Friendster missed the ball -- it's about your friends' lives, stupid. It's about keeping in touch and seeing what's changing. They didn't really optimize for that (they felt like they were primarily about search at first).

About two months ago, I was chatting with Nick Murphy and I observed that the real killer feature for MySpace or Facebook would be a personal RSS feed that was a changelist for all your friends. Ultimately, you could track what's going on with your friends in Safari, in Outlook, on your phone, etc. It would be brilliant.

Then, this week, Facebook added essentially that feature. IMHO, I mean, Facebook has got a lot of stuff going for them. Elegant interface. Photo sharing and tagging is really quite nice. Blogging / notes is a little weak, but ok. They have a developer platform (brilliant -- kudos Fetterman). And now they have a feed that helps you keep track of your friends and what they're doing. (They still need to make it RSS, though.)

All-in-all, I think it's great. Kudos.

(Of course, it's funny -- there also seems to be a huge backlash against the new site and the new features. I was a little surprised. Presumably if they just change the defaults to only publish certain things by default (new photos, new notes, new walls) and not other things (relationship status, etc.), people will be ok.)

On an unrelated note, I haven't blogged about Indigo (er, the Windows Communication Foundation) in a while. That's due, in part, to the fact that I've moved from being a producer to being a consumer of WCF. I've moved from being a PM on the WCF team to being a developer on the some of the backend infrastructure for Windows Live. My infrequent blog posts will probably slowly migrate from stuff like WS-Addressing to Amazon and Google. We'll see.

Ed Helms Takes On Microsoft

2006-06-29T23:32:00Z

Ed Helms (from the Daily Show) did a video for Microsoft College Recruiting. It's fan-freaking-tastic.

The "free soda" person is the awesome Julie Farago.

http://www.microsoft.com/College/default.mspx

Fantastic.

John Battelle Interviews Gary Flake

2006-04-29T18:27:00Z

John Battelle has a good interview with Gary Flake, a Technical Fellow over in MSN: http://battellemedia.com/archives/002471.php.

It reminded me of a relatively recent conversation I had with some other folks that joined the company within the past 5 years.

Basically, a few of us were sitting around a table, swapping stories about how we came to the company.

Some folks talked about knowing that they wanted to come at Microsoft. They'd waited on line for Windows 95 and they'd knocked on Microsoft's doors come recruiting time.

My experience was pretty different. I grew up as a dedicated Mac user (which still holds true today). I came from a college environment that was violently anti-Microsoft and pro-BSD and pro-Linux. When I was first contemplating coming to Microsoft in my senior year, I had a lot of angst about going to the "evil empire."

That said, the reason I came (and the reason I stay) is because of the people. I think Gary pretty much nailed it:

Let's talk about people as a preface to culture, because I want to get the "evil" thing out of the way. I know the reputation that MS has with some communities. I was hacking Linux in the early nineties, I have a four digit Slashdot userid, and I've personally written over 100,000 lines of open source code. I say all of this to qualify my opinion. Being new to MS, the biggest surprise for me was the people. I knew they were smart. I knew they were driven. I knew they were competitive. But I had no idea they would also collectively tend towards kindness, openness, self-criticism, passion, righteousness, and even uncertainty. These are great people -- from the executive team down to the rank and file -- these are simply wonderful people in every way.

Amen. Another quote which rings true:

Okay, now I know I am sounding like a corporate drone and I am well aware that for every example above, there are plenty of people in the valley that will bitch about my characterization. When you assume evil, then an ecosystem looks less than well-intentioned. When you assume goodness, then an ecosystem looks like benevolence. The truth is more complex and vastly more interesting.

I'm always a little amused when a random act of stupidity by some random Product Manager in some random product is taken as Microsoft corporate policy. As it turns out, if you go in looking for evil, it's usually pretty easy to find it.

Anyway -- a good interview. Kudos to Gary for his openness and honesty (both good and bad).

Area Codes

2006-04-22T23:40:00Z

At some point I heard an interesting piece of trivia about the initial assignment of area codes. With rotary phones, the time it takes to dial a digit is actually a function of the digit itself (dialing a 2 takes twice as much time as dialing a 1, dialing a 0 takes 10 times as long as dialing a 1, etc.).

Keeping this in mind, the people who initially laid out the area codes allocated them as a function of population or importance.

Intrigued, I munged a web page to give me an ordering of all the area codes based on number of pulses (i.e., sum of digits counting 0 as 10).

The top few are as follows:

5 - 212 NY New York (New York City Manhattan area, overlays with 646 and 917)
6 - 213 CA California (Downtown Los Angeles area only)
6 - 231 MI Michigan (Traverse City, Ludington, Muskegon, Petoskey and northwestern Michigan)
6 - 312 IL Illinois (downtown central Chicago area)
6 - 321 FL Florida (Orlando, Cocoa Beach, St Cloud and central eastern Florida, overlays with 407)
7 - 214 TX Texas (Dallas area, overlays with 469 and 972)
7 - 313 MI Michigan (Dearborn, Detroit and inner Detroit suburbs)
7 - 412 PA Pennsylvania (Pittsburgh area, McKeesport, Braddock, Duquesne, overlays with 878)
8 - 215 PA Pennsylvania (Philadelphia area, overlays with 267 and 445)
8 - 224 IL Illinois (Waukegan, Des Plaines, northwest Chicago suburbs and northeastern Illinois, overlays with 847)
8 - 251 AL Alabama (Mobile, Jackson and southwestern Alabama)
8 - 314 MO Missouri (St Louis, Florissant, Crestwood, Affton and surrounding suburbs)
8 - 323 CA California (Florence and Los Angeles excluding downtown Los Angeles)
8 - 413 MA Massachusetts (Pittsfield, Springfield, Holyoke, Greenfield and western Massachusetts)
8 - 512 TX Texas (Austin, Lampasas, Bastrop, Milam and central Texas)

The bottom few are:

27 - 908 NJ New Jersey (Washington, Elizabeth, Warren, Plainfield and west central New Jersey)
27 - 980 NC North Carolina (Charlotte, Kingstown and south central North Carolina, overlays with 704)
28 - 909 CA California (San Bernardino, Ontario, Pomona, Chino, Arrowhead and Big Bear Lake areas)

I'm guessing they came along later, but it is fun to think of Elizabeth, NJ as, basically, the least interesting place in the US.

Random. Anyway.

Kudos to Steve Maine & the Atlas Folks

2006-03-21T12:38:00Z

Kudos to Steve, who just shipped some of the stuff he's been working on: http://hyperthink.net/blog/2006/03/20/atlas++Indigo++Crazy++Delicious.aspx.

He's been working on WCF's REST and POX support, specifically the stuff we need to do to have a pretty seamless experience with Atlas. It is, as Steve puts it, crazy delicous. Cool stuff.

WS-Policy & WS-PolicyAttachment Are Published!

2006-03-09T16:53:00Z

We have just re-published WS-Policy and WS-PolicyAttachment (with co-authors IBM, BEA, SAP, Sonic Software, and VeriSign). Congrats to Dan Roth, Jeff Schlimmer, Asir, and everyone else who was involved.

It looks like the spec locations are:

WS-Policy

Web Services Policy Framework (WS-Policy) version 1.2

WS-Policy defines a base set of constructs that can be used and extended by other Web services specifications to describe a broad range of service requirements, preferences, and capabilities.

WS-PolicyAttachment

Web Services Policy Attachment (WS-PolicyAttachment) version 1.2

WS-PolicyAttachment specifies three specific attachment mechanisms for using policy expressions with existing XML Web service technologies. Specifically, we define how to associate policy expressions with WSDL type definitions and UDDI entities. We also define how to associate implementation-specific policy with all or part of a WSDL portType when exposed from a specific implementation.

WS-Addressing Interop is Achieved!

2006-03-09T16:44:00Z

I'm a couple of days late, but still thought I'd share.

WS-Addressing is currently in the process of becoming a W3C Recommendation. There are a bunch of steps in that process (think School House Rocks, “I'm just a bill ...”). One of those steps is the “Candidate Recommendation” step. That's where the Core and Soap specs are today.

In order to get to the next step (”Proposed Recommendation”), one of the requirements that the working group put in place was that we achieved a certain level of practical interop between vendors. Specifically, the Working Group wanted there to be at least four different implementations that interoperated on all of the required features of WS-Addressing and at least two different implementations that interoperated on all of the optional features of WS-Addressing.

Towards that goal, a sub-group of the working group spun-up to start tackle interop testing.

After 3 months of work, we achieved our goal two days ago: http://www.w3.org/2002/ws/addr/testsuite/report/.

Specifically, the Microsoft, IBM, Sun, WS02, and JBoss implementations demonstrated full interop on the required features. The Microsoft, WS02, and JBoss implementations demonstrated full interop on the optional features.

Now on to PR!

Serializing (Binding, Address) Pairs in WCF

2006-03-07T04:02:00Z

One of the great ways to procrastinate from finishing a presentation is to blog.

Another way to procrastinate is to find a better blog editor. ;) I'm having issues w/ code snippets in this UI. But I'll save that procrastination venture for another time.

One of the core virtues (imho) of WCF is its strong emphasis on the decoupling between contracts, bindings, and addresses.

As I'm sure you know already, contracts define the “what“ of your service (from both the client and service perspective). They are develop-time, compiled-in assumptions about your app.

Bindings represent the way that you interact with a particular contract. This allows you to, say, expose the same application contract over multiple different bindings for the wide array of clients with whom you may have to interact. Typically, your contract exposes some set of constraints on the binding (and you can optionally add more constraints with the [DeliveryRequirements] attribute). Our goal in designing those constraints were to make them tight enough to ensure correctness while permissive enough to allow a strong degree of polymorphism amongst bindings.

Lastly, addresses represent the location of your service.

Typically, if you are writing a fairly robust client / service app, you want to minimize the couplings between the client and service.

In terms of endpoints, the pessimal set of couplings you could probably get would be by hard-coding the contract, binding, and address to your service in both your client and service application. This means that if the service moves, you would have to re-compile both the client an the service to make everything work again.

A small improvement over that model would be to separate both the service's address and the client's view of that address into a run-time specifiable value. Most apps either do this themselves or rely upon some built-in support in their app framework. For instance, in WCF, if you want to change your service location, you can do that by updating both your client and service's config.

For WCF specifically, an improvement over that model would be to separate both the service's binding and address, as well as the client's view of that information, into a run-time specifiable value. In fact, our config system is engineered to make this easy and our guidance is pretty prescriptive about this being a Good Thing(tm). As such, if you wanted to change the binding and address where a WCF was located, you could do that by only updating the client and service config (no recompiles necessary).

In both cases, though, you still need to update both the client and the service for what is essentially a service change; this is a little non-ideal. Ideally, you'd like the client to automatically adapt to the service changes.

One way that people typically do this is by having the address of the service be found through some sort of discovery mechanism (either directory-based or “peer-to-peer“-ish). In those cases, the client asks for a service based on some quality (e.g., “give me a service that implements the contract foo at a binding bar“). Via whatever discovery mechanism is defined, the client discovers an address for that service and then proceeds to interact with the service. In this way, a service could update its address and the client would pick up that update “for free.“

In WCF, of course, you'd really want to go one step further. Ideally, the only coupling between your client and your service is the contract (as contract-compatibility is a fundamental assumption that is compiled into your app). The binding and address can be discovered at runtime.

We have some built-in support to the product for this scenario using the MetadataResolver and MetadataTransferClient scenarios. The MetadataResolver class can be used to programmatically retrieve the metadata for a service and surface it as a set of ServiceEndpoints. If you combine this with a discovery approach for metadata addresses, you can essentially achieve the aforementioned decoupling.

Another approach to solving this problem, however, is to make a (Binding, Address) pair itself serializable. This means that you can pass it around itself. For some samples that I've been writing, I've found the ability to do this quite useful.

Here's the code; warning, this is compiled against the very latest bits on my machine, so it may be slightly ahead of the latest CTP.

[DataContract]

public class SerializableEndpoint

{

ServiceEndpoint endpoint;

int priority;

public SerializableEndpoint(ServiceEndpoint endpoint, int priority)

{

this.endpoint = SanitizeContractInEndpoint(endpoint);

this.priority = priority;

}

public EndpointAddress Address

{

get { return this.endpoint.Address; }

}

public Binding Binding

{

get { return this.endpoint.Binding; }

}

public string ContractName

{

get { return this.endpoint.Contract.Name; }

}

public string ContractNamespace

{

get { return this.endpoint.Contract.Namespace; }

}

public string Name

{

get { return this.endpoint.Name; }

}

[DataMember(IsRequired = true)]

public int Priority

{

get { return this.priority; }

internal set { this.priority = value; }

}

[DataMember(IsRequired = true)]

private MetadataSet Metadata

{

get

{

WsdlExporter exporter = new WsdlExporter();

exporter.ExportEndpoint(this.endpoint);

IEnumerable<MetadataSection> sections = exporter.GetGeneratedMetadata();

return new MetadataSet(sections);

}

set

{

WsdlImporter importer = new WsdlImporter(value.MetadataSections);

ServiceEndpointCollection endpoints = importer.ImportAllEndpoints();

if (endpoints.Count != 1)

{

throw new ArgumentException("MetadataBundle must contain exactly one endpoint.");

}

this.endpoint = SanitizeContractInEndpoint(endpoints[0]);

}

private ServiceEndpoint SanitizeContractInEndpoint(ServiceEndpoint endpoint)

{

ServiceEndpoint newEndpoint = new ServiceEndpoint(new ContractDescription(endpoint.Contract.Name, endpoint.Contract.Namespace));

newEndpoint.Address = endpoint.Address;

newEndpoint.Binding = endpoint.Binding;

newEndpoint.Name = endpoint.Name;

return newEndpoint;

}

I include the contract's name and namespace because I hope that's sufficient to correlate the contract with your local one. I've found it useful if I, say, get back a set of these (Binding, Address) pairs and want to see if any of them are usable with my contract. I use priority as a way of weighting multiple matching (Binding, Address) pairs.

The serialization mechanism is a little non-ideal, but we are investigating better ways to make a binding itself serializable.

Interestingly, ieSpellCheck thinks that WsdlExporter is incorrectly spelled. It thinks “sexpot” is a better spelling. I find this amusing, especially knowing that AlexDeJ named the class.

With that, back to the presentation.

(Nit: Another issue with the blog editor is the lack of “preview;” sorry to those folks that saw the first draft before I re-read it.)

Fancy Addressing in WCF

2006-02-01T21:08:00Z

One of the core specs that WCF implements is WS-Addressing.

At the highest level, WS-Addressing essentially defines three things.

First, WS-Addressing defines a core address construct called Endpoint Reference. An Endpoint Reference provides a mechanism for identifying a Web service endpoint. In the WCF object model, we call this thing an EndpointAddress.

Second, WS-Addressing defines a set of Message Addressing Headers. These headers -- To, ReplyTo, FaultTo, MessageID, RelatesTo, etc. -- are useful for defining (a) where an initial message is going, (b) how to send messages in reaction to that initial message and (c) how to tell that those reactionary messages are related to the initial message.

Third (though it's not usually called out separately), WS-Addressing defines an Action header. This essentially defines the intent of the Message. Typically, if you want to figure out how to process a Message, you use the action as your key.

We tend to think of the Message Addressing Headers primarily as plumbing. For instance, if you want to correlate a request message with a response message over TCP or UDP, you need the ReplyTo, MessageID, and RelatesTo mechanisms. If you want to figure out to what endpoint you should dispatch a message, you look at the To. Etc. Our runtime adds and inspects these headers to do things like request-reply correlation.

Sometimes, though, people end up wanting to do fancy things with addressing at the application layer.

For instance, one pattern is to send a one-way message to a lot of folks (e.g., using UDP multicast) and provide them with a mechanism for sending back one-way reply messages.

To do this in WCF, you just need to use OperationContext.

For instance, suppose I had the following two contracts:

[ServiceContract]

interface QueryContract

{

    [OperationContract(IsOneWay = true)]

    void Query(string query);

}

[ServiceContract]

interface QueryCallbackContract

{

    [OperationContract(IsOneWay = true)]

    void Response(string response);

}

The first contract (QueryContract) represents the one-way message that I want to send out. The second contract (QueryCallbackContract) represents the one-way message I expect in return.

Now, suppose you want to correlate a Query message with a Response message.

To do that, you'd first create up the appropriate channel / channel factory:

CustomBinding binding = new CustomBinding(new TextMessageEncodingBindingElement(), new HttpTransportBindingElement());

ChannelFactory<QueryContract> factory = new ChannelFactory<QueryContract>(binding, new EndpointAddress("http://destination/"));

QueryContract channel = factory.CreateChannel();

Next, you would wrap your call to Query() in an OperationContextScope. This essentially populates an OperationContext.Current.

Inside your using block, you could add the address of your local endpoint to the ReplyTo header as well as add a correlation ID:

using (new OperationContextScope((IContextChannel)channel))

{

    OperationContext.Current.OutgoingMessageHeaders.ReplyTo = new EndpointAddress("http://callback/");

    OperationContext.Current.OutgoingMessageHeaders.MessageId = new UniqueId();

    channel.Query("foo");

}

After this, you would typically store off the Message ID you created, along with information about the request, in some thread-safe dictionary.

On the service-side, you might implement Query() as follows:

class QueryService : QueryContract

{

    public void Query(string query)

    {

        EndpointAddress replyTo = OperationContext.Current.IncomingMessageHeaders.ReplyTo;

        UniqueId messageId = OperationContext.Current.IncomingMessageHeaders.MessageId;

        CustomBinding binding = new CustomBinding(new TextMessageEncodingBindingElement(), new HttpTransportBindingElement());

        ChannelFactory<QueryCallbackContract> factory = new ChannelFactory<QueryCallbackContract>(binding, replyTo);

        QueryCallbackContract channel = factory.CreateChannel();

        using (new OperationContextScope((IContextChannel)channel))

        {

            OperationContext.Current.OutgoingMessageHeaders.RelatesTo = messageId;

            channel.Response("bar");

        }

    }

}

First, you would fish out the addressing headers that you set (ReplyTo, MessageId). Next, you would create a channel back to that ReplyTo. Next, you would create a new OperationContextScope and use that around the new channel, set the RelatesTo header to match the MessageId, and then send the response message.

(Note, you'd probably want to be slightly fancier than creating a new binding / channel factory for each operation.)

Lastly, back on the client-side, you would probably fish out the RelatesTo, go back to that dictionary you set on the initial request, and complete the outstanding operation.

class QueryCallbackService : QueryCallbackContract

{

    public void Response(string response)

    {

        UniqueId relatesTo = OperationContext.Current.IncomingMessageHeaders.RelatesTo;

        // use relateTo to correlate to initial request

    }

}

It should be noted that in a real application, you might want to be more sophisticated about deciding whether or not to trust the incoming ReplyTo before creating a channel to it.

So there you go.

Interestingly, I just realized that utilizing the ReplyTo header has a nice property over utilizing a custom header as you can use EndpointAddress directly (and we will pick up the right addressing version for free). If you were to define a MessageHeader via CreateMessageHeader(...), you would have to pick a serializable type of EndpointAddress (either EndpointAddressAugust2004 or EndpointAddress10) or write a custom sub-class of MessageHeader that grabbed the ambient Message Version and used that when reading / writing the EndpointAddress.

But I digress.

Edit (2006.03.21): Fixed Typo -- Changed QueryContract --> QueryCallbackContract.

Greetings

2006-01-31T06:20:00Z

Greetings from Building 42!

(Yes, the Windows Communication Foundation (as well as the .NET Framework and the CLR) are built in Building 42.)

After years of resisting, I've finally decided to sit down and do the blog-about-WCF thing.

My name is Mike, and I'm a Program Manager on the WCF team. I work on the design and implementation of the Service Model, including the core programming metaphors (Services, Endpoints, Contracts, Behaviors, Bindings, Addresses) and the core runtime pieces (Dispatcher, Channels, etc.). I also work closely with the way we map to and from WSDL and XSD.

I plan to use this space to basically rant, but every so often I may make fun of Don or Doug.

My first rant, though, is reserved for the fine poster people at Microsoft.

One of the plagues that, I guess, infects any large corporation is the need for lots and lots of informative posters. Update Your Benefits! Cheer Your Local Localization Team! Etc.

One of my new favorites is the poster entitled “Super Meetings.“ To be frank, the poster basically stands alone:

To quote classic Simpsons: “Unless your being ironic, turn that off now!”

-mike