Re: Roy's ApacheCon presentation

Mark Baker wrote,
> Sure, ok, you're O(Nlog(N)) as a best case, and O(N^2) as a worst
> case (thanks Miles).  Still, would you agree that that's
> significantly worse than O(N)?

Umm ... NlogN is my guess at the _typical_ case.

Seeing as you're referencing my mail, I'll repost it here for the full 
context ...

Mark Baker wrote,
> what it says is that with Web services, integration complexity is
> O(N^2), while O(N) with a common interface.

As an aside ...

I think this is a double-edged sword. Certainly the integration 
complexity is reduced. But OTOH the effort of reaching agreement on the 
common interface is increased.

Just to spell this out a bit more, with multiple point-to-point 
interfaces only two parties need to agree on any particular interface, 
whereas all N have to agree on the common interface. I'd conjecture 
that the cost of reaching agreement is exponential in the number of 
parties to the agreement. That gives us O(N^2)*O(2^2) (ie. just O(N^2)) 
cost for agreement in the multiple interface case (O(N^2) pairs each 
having to reach an independent bilateral agreement) vs. O(2^N) cost for 
agreement in the common interface case.

I'd also conjecture that O(N^2) is a wildly pessimistic worst case 
because in practice not everybody needs to talk to everybody else. You 
only need O(NlogN) edges in a random graph to get complete 
connectivity, so O(NlogN) seems like a good guess for the typical, as 
opposed to the worst, case. FWIW ... not proof, but I've seen data from 
a major (ie. one that hasn't gone bust yet ;-) B2B exchange which 
supports this.

For multiple interfaces that'd give us,

  O(NlogN)     cost of integration (ie. NlogN implemented interfaces)
  O(NlogN)     cost of agreement   (ie. NlogN bilateral agreements)

For a common interface it'd give us,

  O(N)         cost of integration
  O(2^N)       cost of agreement

Notice that the cost of agreement won't scale down to the typical case 
for the common interface in the same way as it does for multiple 
interfaces, because the common interface still requires global 
agreement whether or not all parties need to communicate with each 
other.

I guess that you know as well as I do that agreements are fraught, 
messy, political and expensive. I take that as a hint that reducing 
that element of the _total_ cost is likely to be a win.

And I also think that multiple interfaces are likely to scale better in 
the face of growth and change (yup, I realize that this runs completely 
counter to what _everyone_ else is saying ;-). That's because changes 
are liable to be local, hence in the multiple interface case only 
require local renegotiation and reimplementation; and because new 
participants only have to reach agreements with the subset of existing 
participants they actually need to communicate with.

OTOH, on the common interface model every change requires global 
renegotiation and reimplementation; and new particpants either have to 
get along with what the first-movers already decided on whether or not 
it's fully appropriate for them, or alternatively simply not become 
participants at all (or become participants in something else). And, 
again FWIW, I've seen data from several B2B exchanges that this last 
problem is a real one ... they have a tough time signing up anyone 
beyond the initial consortia.

Interestingly, the numbers above generate the exact opposite of the 
typical "network effect" on the common interface model ... we actually 
end up with _decreasing_ returns to scale.

Thoughts?

Cheers,


Miles

Received on Wednesday, 20 November 2002 15:26:21 UTC