Lambda the Ultimate

I'm not far from believing in it myself

Not sure what's hard to believe. A REST-ful URI is just a lambda name! If you then maintain memory-safety, you now have a secure, distributed lambda calculus.

Besides URIs we have other defining traits in REST (e.g. HATEOAS, uniform interface), some of which aren't well mapped to well known theories. Also nothing says that a distributed lambda calculus is a good fit to distributed systems when compared to distributed Pi or Join.

The actual comment was believing that it's just a sociological problem. IMHO there's some issues that are still open (e.g. service versioning, authentication) and need some engineering work. Don't get me wrong, I've been working solely with REST based architectures this year and I'm not looking back to anything else (to work within the Internet).

Also nothing says that a distributed lambda calculus is a good fit to distributed systems when compared to distributed Pi or Join.

It's closest to a distributed lambda calculus with futures. The Waterken server was influenced heavily by E.

(e.g. service versioning, authentication)

I highly recommend you read the site I linked to. Tyler Close's web-calculus/web-keys work discusses all of these issues and solves them quite elegantly IMO.

I'm a lurker on cap-talk for some time now, Waterken is what I point people to when they ask me about caps on the web ;). The fact that the web-calculus exists and is elegant is great, but there's a distance between having a theoretical solution and it being practical. I'm not trying to diminish Tyler's efforts or abilities, but there are many great ideas that don't scale. I think that the web-calculus is the solution to the problems I discussed above, but its just my opinion, until there's a large base using and deploying it we don't know if it'll work as intended. I would bet on the web-calculus (and caps in general) but we can only say the problem is solved when it is "used in anger" by late adopters.

I'm not trying to diminish Tyler's efforts or abilities, but there are many great ideas that don't scale.

Very true. If you've been following cap-talk, then I think a Horton implementation on the web would get Waterken close enough to implementing existing ACL-based policies so as to reap the benefits of both worlds.

There are also scalability concerns with traffic volume, and development tools, but I think they're all fundamentally solvable.

REST says nothing about the distributed algorithms needed to coordinate or collaborate. REST provides global naming of resources and conventions to build client/server applications on the Internet. This is only the first step.

Sequential code, private to an organization:
* Determinstic scheduling: yes
* Topology: Fixed.
* Migration: N/A
* Global consensus ("god's eye view"): yes
* Partial failure: no
* Malicious third parties: no
* Malicious clients: no
* Administrative domains: single
* Bandwidth: Extremely high
* Latency: Extremely low (nanoseconds to tens of nanoseconds)

Multithreaded code, private to an organization, running on a single CPU with pre-emption:
* Deterministic scheduling: no
* Topology: Fixed
* Migration: N/A
* Global consensus: yes
* Partial failure: no
* Malicious third parties: no
* Malicious clients: no
* Administrative domains: single
* Bandwidth: Extremely high.
* Latency: Extremely low (nanoseconds to tens of nanoseconds)

SMP/Multicore, private to an organization:
* Determinstic scheduling: no
* Topology: Extremely stable (occasional CPU upgrade in some systems)
* Migration: Trivial (one processor as good as another)
* Global consensus: Possible, though more expensive (cache coherency issues)
* Partial failure: no
* M3P: no
* MC: no
* Administrative domains: single
* Bandwidth: Extremely high
* Latency: Very low (tens to hundreds of nanoseconds, cache coherency, again)

NUMA architectures:
* Deterministic scheduling: no
* Topology: Very stable (occasional CPU upgrade in some systems)
* Migration: Somewhat trivial--support provided by underyling OS typically.
* Global consensus: Expensive, often "no"
* Partial failure: no
* M3P: no
* MC: no
* Administrative domains: single
* Bandwidth: Very high
* Latency: Low (hundreds of nanoseconds to microseconds)

Dedicated clusters with fixed topology, decoupled or isolated from an organization's intranet:

* Deterministic scheduling: no
* Topology: Stable-very stable (such systems are not reconfigured without good reason)
* Migration: somewhat difficult--though often supported by OS or grid/clustering software.
* Global consensus: No
* Partial failure: Yes, though uncommon and usually quickly detectable
* M3P: no
* MC: no
* Administrative domains: single (administrative responsibility may be subdivided, though there is usually one person "at the top")
* Bandwidth: High
* Latency: Medium-low (tens to hundreds of microseconds)

Intranets in general and similar private distributed systems

* Deterministic scheduling: no
* Topology: moderately stable (often changes to topology, though most are harmless or published in advance)
* Migration: difficult.
* Global consensus: No
* Partial failure: Yes, though somewhat uncommon and usually quickly detectable
* M3P: no
* MC: no
* Administrative domains: single (administrative responsibility may be subdivided, though there is usually one person "at the top")
* Bandwidth: High
* Latency: Medium (hundreds of microseconds to milliseconds or more)

Clusters, other loosely coupled systems, via a VPN (all nodes private to an organization, but over a public network; possibly with negotiated QoS)
* Deterministic scheduling: no
* Topology: moderately stable (often changes to topology, though most are harmless or published in advance). Topology of intermediate network is often a "don't care" and is abstracted away by VPN.
* Migration: difficult. Global consensus: No
* Partial failure: Yes
* M3P: yes, though modern VPN abtractions reduce the risk via transport-layer encryption (transparent to the application).
* MC: no
* Administrative domains: multiple. Nodes are technically under a single point of control, though geographically distributed sysadmins are often better modeled as multiple domains. Network service provider(s) are additional domains, though they are often required to provide some level of QoS even if best-effort.
* Bandwidth: Medium
* Latency: Medium (milliseconds to tens of milliseconds)

Distributed systems over the open internet, all nodes private to an organization:
* Deterministic scheduling: no
* Migration: difficult.
* Topology: unstable
* Partial failure: Yes
* Global consensus: No
* Partial failure: Yes, with fault isolation difficult.
* M3P: yes. In addition, some service providers may be hostile to some applications (ie BitTorrent).
* MC: no
* Administrative domains: multiple. Intermediate domains may be difficult to identify, intermediate service providers may be indifferent to endpoints.
* Bandwidth: Medium-low
* Latency: Low (tens to hnudreds of milliseconds)

External services over the open Internet:
* Deterministic scheduling: no
* Migration: difficult.
* Topology: very unstable; client nodes come and go at will.
* Global consensus: No
* Partial failure: Yes, with fault isolation very difficult.
* M3P: yes. In addition, some service providers may be hostile to some applications (ie BitTorrent).
* MC: yes. tons of them.
* Administrative domains: multiple, including clients under different domains.
* Bandwidth: Low, especially if client is over dialup or other low-bandwidth connection.
* Latency: Low to very low (hundreds of milliseconds or more)

Hm. I disagree with the statement that "External services over the open Internet:" have "low to very low" latency. My experience with ISPs in Russia directly contradicts this statement.

Obviously, that should say "high" latency. Brain fart.

Developers consistently underestimate the risk of clients on an intranet. The simple fact of the matter is that many security breeches are "inside jobs," or at least have some help from the inside. The larger or higher-profile your organization is, the greater your risk.

No code is safe when run on a compromised system; the security model in the chart above deliberately excludes the possibility of viruses/trojans which have infected a system--focusing instead on attacks that are enabled by running over public infrastructure. Perhaps a questionable assumption, but a simplifying one.

(On second though--perhaps applications which have user interfaces ought to be considered distributed applications, and things like mice, keyboards, monitors, and other peripherals ought to be considered "nodes"? Many attacks against a system are done by compromising such peripherals--think of keystroke loggers and the like.)

Yes, you are right, there are lots of different kinds of loosely coupled systems. The chart gives a good overview of the different problems. Partial failure (yes/no), imperfect failure detection (yes/no), bandwidth (high/low), latency (high/low), malicious entities (yes/no), etc. The dataflow techniques that work well for multi-core processors can also be used in some of these loosely coupled systems. MapReduce, for example, works well in systems with partial failures. A fortiori, these two points reinforce the conclusions of the position paper.

Can you show me that there can't be a better way than dataflow programming to make multi-core easy? :)

While dataflow programming's power is obvious at a glance, there is surely a reason that I, a programming languages enthusiast, student, and inventor, have never heard of any of the dataflow languages listed by Wikipedia. I expect more popular success from a Silver Bullet for multi-core, especially these days.

Is there something I'm missing which should be telling me that dataflow programming is The Way?

Wikipedia lists quite a few dataflow languages, some of them have Wiki pages of their own.

Edit: Please disregard this utterly stupid comment, I've obviously misread your post.

I can't show you that there can't be a better way than dataflow to make multi-core easy. But monotonic dataflow (a.k.a. deterministic concurrency) is really very easy: it's not harder than usual functional programming. I.e., if you know how to program without explicit state, then you have all you need for programming multi-core. Chapter 4 is the place to look!

I can't blame you for not having heard of dataflow languages. It's a problem of education: most computing curricula teach almost nothing about programming languages. They teaching programming as if it were just a cookbook of object-oriented techniques. It's a great tragedy.

Data flow is a natural model for many domains (music, hardware, signal processors), but, at least with my experiences in Flapjax, application-level abstractions common to VB/RoR/Cocoa style programs are often hard to encode (though many that are annoying in functional/imperative are much easier!). In particular, I've recently been struggling with structured, versioned, and (inclusive) shared data. I saw a couple of programs listed on your home page, which hopefully will provide a better intuition as to why you believe such common application tasks are solved problems. First I'll need to learn oz/mozart, but luckily I finally snagged a copy of CTM..

Your examples (music, hardware, signal processors, Flapjax) are not what PvR calls dataflow programming. A variable in Flapjax is a stream of values (like a mutable variable). An Oz dataflow variable is only one value, like in functional programming. The difference between an Oz variable and for example a Scheme variable is that a Scheme variable has a value if it is visible whereas a dataflow variable can be unbound even if it is in scope.

Scheme:

(let ((a 3)) ; you have to give it a value
  ... a ...)

Oz:

local A in % you don't have to give it a value
  ...   % here A is not bound
  A = 3 % now it's bound
  ...
  A = 4 % illegal, dataflow variables have a fixed value once they're bound
end

Using an unbound dataflow variable blocks the current thread until the variable is bound by another thread.

An example. You need to do two computations in parallel. Then you combine the result of the two computations.

local A B in
  thread 
    A = <computation 1>
  end
  thread 
    B = <computation 2>
  end

  <combine A B>
end

This program first spawns two threads, one for each computation. Then it immediately tries to combine the results. The results probably aren't available yet (A and B are not bound), so the <combine A B> step waits until A and B are bound. A better explanation is in CTM (with much more advanced examples, like storing unbound dataflow variables in data structures).

There are at least three kinds of dataflow:

• monotonic dataflow: very similar to pure functional programming, can use lazy evaluation (in Oz: chapter 4 of CTM)
• nonmonotonic dataflow: tokens moving along wires; similar to concurrent logic programming (in Oz: section 5.8 of CTM)
• functional reactive programming: refined version of the previous one that does not create extra nondeterminism (in Oz: see FRP in Oz)

(To keep things clear I leave out synchronous programming for now.) All can be used to program multi-core processors, but the first is by far the easiest. This programming paradigms taxonomy shows how they relate to each other and to other paradigms.

CTM were to one day get an extra "chapter" in which FRP were to be discussed. Probably you and Prof Haridi are busy, and a second edition is probably not due out for a couple more years (if not the better part of a decade), but if you're looking for additional material to cover, there's one idea.

There will be a new printing (the fourth) of CTM available in July that corrects all the errors on the errata page. I am collecting raw material (including about FRP) for a possible second edition, but I don't think it will happen for several years (11 years passed between the first and second editions of SICP!).

A variable in Flapjax is a stream of values (like a mutable variable). An Oz dataflow variable is only one value, like in functional programming.

It seems easy to derive a stream from a dataflow variable. Just resolve the variable to a (current value, closure to compute the next value) pair.

Having a closure sort of defeats the point of using dataflow variables. Instead, what you do is representing the stream as a list whose tail is a dataflow variable. Very much like a lazy stream, which in fact can be viewed as a special case.

A FRP variable seems like a declarative variable sans blocking semantics. FRP values, denotationally, are something like F = T -> (H + F) where T is time (perhaps on a discrete clock) and H is the host domain - they are never undefined in the Oz sense. For example,

a = getJson('http://1');
b = getJson('http://2');
c = a + b;

Perhaps you could encode blocking:

a = getJson('http://1');
b = getJson('http://2');
c = definedP(a) && definedP(b) ? a + b : NotDefined ;

This 'dP(a) && dP(b)' check could get annoying, but is systematic, so we could imagine creating a sugar for it or building it in. This wouldn't get you the scoping ability of Oz, but that can be achieved by a simple hoisting transform on an Oz style 'declare' statement. I'm not actually convinced that breaking linear flow is worth it (at least for the trivial examples I've read so far) - that was one of the big wins people report of our system!

I'm trudging through CTM this week - such a use of dataflow seems similar to futures, forces, etc., and not what I think people envision when suggesting dataflow for multicore, but will keep digging for the dataflow aspect of it. Not to say these ideas are not interesting - several of my friends are revisiting cooperative scheduling work related to it.

EDIT: changed 'x' to '+' in the denotation. Such a value should be flattenable to 'T -> H', but this flattening can be annoying.

You're right, a basic property of distributed computing is that many things are impossible. What I intended to say (maybe not clearly enough) is that the area of distributed computing is well understood, not that there exist algorithms to solve every problem. For example, a basic result that everybody should know is the impossibility of distributed consensus with a single faulty process. Assume asynchronous reliable communications (messages arrive after any finite time in any order). Assume at most one process may crash (stop permanently) at any time and that we cannot detect this failure directly. (These assumptions are essential to the result!) Then it is impossible for all processes to arrive at consensus on a single binary value. This basic result was first proved in 1985. A consequence is that totally asynchronous systems cannot have any kind of fault tolerance. To have fault tolerance we need something more, like failure detection or timing constraints on message delays.

Have you seen this paper:How the Hidden Hand Shapes the Market for Software Reliability by Birman et al? It's a little unfocussed but it has an interesting digression on the overly subtle definition of 'impossibility' used by FLP.

"For example, a fault-
tolerant leader election protocol might be tricked into never
quite electing a leader by an endless succession of temporary
network disconnections that mimic crashes. As a practical
matter, these patterns of message delay are extremely
improbable – less likely, for example, than software bugs,
hardware faults, power outages, etc. Yet they are central to
establishing the impossibility of guaranteeing that consensus
will be reached in bounded time. "

The paper then goes on to talk about the ways in which real-world distributed systems have access to all sorts of powerful features denied to the models used by FLP.

What kind of problem were you addressing? How and why did their "programming model" fail to deliver? What was it supposed to deliver? What are you basing your tools on?

What kind of problem were you addressing?
That's in the embedded space. We have a complex video decoder/encoder that is made of heterogeneous hardware blocks (processors, VLIW-like processors, specialized hardware..). All the blocks are connected through shared memory and different kind of hardware 'channels' with FIFO. An important point is that these channels may contain both data and addresses. So some blocks are basically just acting as finite state machines rather than processors.

All these features are non-standard, but in the embedded space the usual abstractions (shared memory, transactional memory, ...) do not give the suitable locality and/or are too costly in term of hardware.

How and why did their "programming model" fail to deliver?
They came up with the usual programming model: tasks, shared memory and some FIFO. Without going into the details, let me say that our hardware/software partitioning (the one devised by our engineers) was not even representable with the guys' programming model. That's why I'm saying all the technical challenges are not yet resolved. But the discussion with these guys was very interesting and I learned a lot.

What was it supposed to deliver?
A standardized way of looking at our system - e.g. a unified programming model.

What are you basing your tools on?
Intuition.

Any, the outcome is that we could not abstract our system and find a unified programming model (yet). To have a system with good performances, software guys needed to solve a lot of multicore-related issues that were specific to the algorithm and the hardware being implemented.

I would agree that my comments do not apply to SMP and homogeneous hardware, where most of the communication is standardized though.

...and cannot comment on the specifics of your architecture. But I *am* involved in the video equipment industry, and have encountered in my career numerous baroque and badly-done BMP (bizarro multiprocessing) designs, usually done by hardware guys who haven't a clue about software (or about the performance capabilities of modern CPU architectures). I also am familiar with what you can get away with using off-the-shelf x86-class microprocessors (either alone, or in tandem).

Unless you're building a reference-grade MPEG encoder, one that dances and sings and tries to squeeze every last bit out of the encoded bitstream using all the wonderful tricks in the MPEG playbook--that, or you're trying to real-time-encode a large number of streams in parallel (MPEG, H.264, or whatever else)--I have a hard time imagining what you are doing that can't be accomplished using stock PC components and stock PC architectures.

And if you ARE doing a reference-grade or highly-parallel design--you're probably building a gadget that you can sell for thousands, if not tens of thousands of dollars. So I'm also puzzled by your cost constraints (though am not too terribly surprised--I've seen projects fail around here due to management not willing to authorize sufficient manufacturing cost in order to build HW capable of meeting the requirements, thinking that engineering can square the circle with only a straightedge and compass, given enough unpaid overtime).

When I hear of the need to pass pointers between nodes in a non-SMP design, that smells bad. When I hear of designs guided by "intuition" that appear to not correspond to the relevant theory, that smells really bad.

My particular, off-the-cuff advices is unless you are Sun Microsystems (or some other experienced builder of massively-parallel supercomputers); avoid NUMA-ish designs. Either stick to homogenous SMP (in which case the chipset and OS does the hard parts for you), or highly-decoupled multiprocessing (using FIFOs only, not arbitrary shared memory). If you don't care about latency, on-board Ethernet is a great way to connect nodes in a loosely-coupled multiprocessor.
Make sure your hardware/software partitioning is appropriate--you want to a) balance the workload of the computing nodes, b) as a practical matter, ensure that high-volume I/O can be done using DMA on your general purpose processors, and c) minimize round trips between nodes. For example, using part of an FPGA as a coprocessor to do DCTs and IDCTs on behalf of the main processor, is generally not a good idea. Distributed nodes should do LARGE tasks, not small ones.

And if your system is non-orthogonal its design, the "programming model" should reflect that.

Did you program your hardware in C? If so, how is Cilk deficient?

few aloof gurus from academia *think* that they solved them long ago

This is why I love LtU: it's where aloof gurus meet pedal to the metal practitioners :-).

It's too bad there is no LtU workshop attached to a conference. These meetings would be even more fun over dinner and drinks :-)

If you make it, people will come.

I've been thinking about doing something like this at some point.

Where would it be held? POPL? ICFP? OOPSLA/ECOOP? The programming language community is a bit fragmented and many people (me) don't cross conference boundaries. Although LTU is FP oriented, a lot of OOPSLA people lurk here (see a Scala BOF at OOPSLA). BOF's at conferences are probably appropriate, although you'd be competing for time with other more focused interest groups.

There's nothing stopping there being multiple workshops, though ideally one would like a "main" one.

How about a quick pub night in Ehud's new home of California? I'm paying a short visit to San Francisco next week and I'd enjoy putting some faces to names. Wednesday evening perhaps?

This would be LtU Beer Night #2 after Ehud, Denis, and I inaugurated the event in Jerusalem last year. :-)