Can the end-to-end principle be formalized?

Question

In the late 1990s, when I was in graduate school, the paper

JH Saltzer; DP Reed; DD Clark: End-to-end arguments in system design. ACM Trans. Comput. Syst. 2(4):277-288, 1984. DOI=10.1145/357401.357402

was pretty much required reading in every operating systems class at every university, and it still seems to be one of the primary guiding principles underlying the design of the internet. (See for example: J Kempf, R Austein (eds), and the IAB, "The Rise of the Middle and the Future of End-to-End: Reflections on the Evolution of the Internet Architecture," RFC 3724, March 2004.)

The end-to-end principle states (Saltzer et al., 1984):

[If] the function in question can completely and correctly be implemented only with the knowledge and help of the application standing at the end points of the communication system, ..., providing that questioned function as a feature of the communication system itself is not possible. [Although] sometimes an incomplete version of the function provided by the communication system may be useful as a performance enhancement.

Or more briefly (from the abstract):

The end-to-end argument suggests that functions placed at low levels of a system may be redundant or of little value when compared with the cost of providing them at that low level.

But I've had little success applying the end-to-end principle in my own experience (which is in computer architecture, not internet architecture). Since the principle is stated as a "poem" (i.e., in English prose with a bunch of terms that are not mathematically defined) it is quite easy to fool oneself into thinking that "the function in question can completely and correctly be implemented only with the knowledge and help of the application." But what is "the function in question," let alone "the knowledge and help" of an application?

Example: On-chip networks (unlike the internet) aren't allowed to drop packets, but have quite limited buffering, so you need to have some way of either avoiding or recovering from deadlock. On the other hand, the application needs to make itself deadlock free as well, right? So I might reason that I should make the common case (no deadlock) fast and push deadlock avoidance off on the app. This is, in fact, what we tried on Alewife and Fugu (Mackenzie, et al., Exploiting Two-Case Delivery for Fast Protected Messaging, Int'l Symp High-Perf Comp Arch, (HPCA-4):231-242, 1998. Or John Kubiatowicz's dissertation.) It "worked," (by having the interconnect interrupt the processor when the buffers got filled and having the OS augment with software buffering) but I haven't seen anyone in academia or industry (including any of us that were authors on that HPCA paper) racing around trying to replicate the idea. So apparently deadlock avoidance in a network is not the same "function in question" as application-level deadlock avoidance, or the end-to-end principle is wrong.

Is it possible to turn the end-to-end principle from a "poem" into a theorem? Or at least, can it be stated in terms understandable to a computer architect?

Answer 1

I believe there may be two shortcomings in your application of the end-to-end (e2e) principle:

Firstly, in the sense that you apply it for performance. The end-to-end is a design principle such as to ensure architecture orthogonality, composability, regularity, one or all, provide primitives etc. Such principles have been outlined in related textbooks. Performance is not one of them. In fact, Clark et al, implies that strict end-to-end may result in worse performance so it uses such, as an exception to this principle.

So, if you still want to formalize:

"The end-to-end argument appeals to application requirements, and provides a rationale for moving function upward in a layered system" so you will need formalized application requirements and formalized layered system. Here is an attempt that might help taking it one step further:

Say you have Layer(i) requirements (Layer(0) is for the set of applications you expect to support now or in the future, the application layer) and firm interfaces Interface(i,i+1) and Interface(i+1,i) (from Layer i to i+1 pre-assume no cross-layering here, easy to change and make it a requirement) and functions Function(i,j) (Layer i, Function index j, assume data part of function to have it simpler)

Input: Layer(0) requirements (as we said these need to be formalized)

Output: everything else

END-TO-END Output is an Output such that: For each L, Layer(L) accomplishes its requirements only by functions Function(L,j) (i.e. functions within the layer) and Interface(L,L+1), Interface(L+1,L)

For each Layer L and function Function(L,F) there is no set of Functions S in the output such that Function(L,F)=S (= means equivalent output and side-effects)

So, coming to the second possible shortcoming for the specific e2e principle application (and if I am reading correctly what is being attempted) one can claim that it does not follow the e2e principle at all, quite the contrary. You have your chips provide "some deadlock avoidance" and you have an Interface that is out-of-the-ordinary non-firm and specific to trigger (interrupt) more help from upper layers. This is arguably a cross-layer approach not an end-to-end approach. In other words you have a Function(1,x) not accomplishing its task completely and correctly with set Interfaces - if you want to use the draft formalization provided above (which of course is just a start useful to an extend to fully answer your question but likely not full in itself).