Lambda the Ultimate

Any scalable system has a scalable strategy for dealing with breakage. Whole-system versioning isn't all that scalable, because it requires a lot of duplication and communication to distribute consistent versions to everyone. The bigger the system gets, the greater the communications burden per node gets to distribute a version. And usually at precisely the moments when communications are problematic if version rollbacks are an error strategy.

The strategy with RDP is that remote resources, protocols, etc, don't simply lock. Or at least, not for long. If a protocol is interrupted in the middle, the server just drops it; the "demand" represented by the other party's use of the protocol goes away and the server, after a short wait, just frees up the resources for use on something else.

What this means, if I understand it, is that "consistency" is local consistency. You've control of local resources and local data and locally you know what they were at any point in time. Someone who observes the system from a different locality may see events having happened in a different order due to speed-of-light delays or choking routers with a backlog delay or whatever, but they also have a consistent local picture of the local resources that they control.

Is this a "correct" understanding?

Disruption in a distributed system is generally non-deterministic. But that doesn't mean we need to abandon every useful consistency property: if distributed parties can agree on the logical instant of disruption, they can achieve a consistent view of the disruption - a "breaks cleanly" guarantee. In RDP, the logical instant would be continuously negotiated by the heartbeat protocol (on a per-session basis).

For performance and prediction, it is useful to speculatively evaluate well ahead of the negotiated instant. Potentially, that requires rolling back a little and performing some rework after disruption. RDP is structured in a manner that ensures the rework necessary can be precisely computed. RDP's temporal semantics are inspired from time warp protocols - a technique that harks back to 1985.

RDP cannot guarantee strong global consistency. But many forms of weaker global consistency are easily achieved: snapshot consistency between threads or processes (which protects against all malign glitches) is easily achieved by batching updates; eventual consistency for straggling updates (albeit with only a small window before negotiated disruption) is easily achieved for state resources. (I don't bother with long-term eventual consistency because it's useless beyond a certain point.)

Someone who observes the system from a different locality may see events having happened in a different order

There are no events in RDP. You could observe states changing in different order, if you are different latencies from them. However, latency properties are expressed formally and logically in RDP, by use of a `bdelay` behavior to model all those speed-of-light delays. A choking router, if it has any observable impact, must be formally modeled in RDP by use of an external stateful resource. Local computations achieve a consistent view of not only how local resources appear this instant, but also a consistent view of how remote resources appeared some (formal, logical, compositional) number of nanoseconds ago.

Preferably the `bdelay` is on the conservative side so you end up buffering future updates (instead of suffering straggling updates). However, RDP can tolerate an occasional bdelay underestimate via the small eventual consistency window. Either way, varying latency in the system does not introduce non-determinism or global inconsistency. It is not difficult to reason about how different observer-code will see the same states.

With latency modeled logically, disruption is the only cause of inconsistency in a distributed RDP system. If latency varies outside the tolerance windows, that is modeled as disruption. And I described above how disruption is handled.

It would not be difficult to develop and enforce a sort of temporal type-safety to guarantee latency-valid distributed programs.

(Aside: Logical synchronization - achieved by matching logical latencies - has several wonderful performance and robustness advantages compared to the more traditional stateful (lock, semaphore, barrier) synchronization.)

One might also look at David Pollak's visi.io, which obtained some interest in the recent StrangeLoop.

I would echo Dave's comment to look at past work (there's been a lot), both commercial and research. Lotus Improv is the big example, as he mentioned. Many years ago I asked a friend who worked at Lotus about its reception, and his comment was that in general it worked very well, but when one wanted to create an exception for the general formula for a particular cell in an array, it was very difficult.

Other things to look at (Google for more references that what I give below):

Trapeze, which did away with a fixed grid and allowed you to draw arrays and give each a formula. At the time I thought of it as visual APL.

Spreadsheet 2000, similar to Trapeze, with nesting.

Quantrix, an existing product that continues and expands on the ideas of Improv.

This topic has been discussed several times before on Lambda-the-Ultimate, including this thread, which mentions some of the same things as above.

I did some research work (not really published) on this around 1989-1992, mostly trying to build an automated back-of-the-envelope calculator for casual calculations. You could enter values and formulas on a blank sheet, and rearrange them freely. I was particularly interested in making the formulas visible at all times. I think hidden formulas is one of the big issues with spreadsheets. The lack of visibility and the usual way of seeing only one formula at a time promotes errors. The other big problem is the awkwardness of assigning meaningful names to cells and blocks of cells.

You might also look up the research work of Bonnie Nardi, done around the same.

That's beautiful. For many years I've had a vague fluffy idea of how I would like to redesign a spreadsheet, after reading through the links I can see that it has been done and would be a clone of Trapeze. Halfway between a spreadsheet and a live programming language.

I think you meant this link.

Fixed.

This has some concepts in common with Cairntaker, an untested, unoptimized, and generally neglected garbage collector I've built on top of JavaScript. It supports mutable and immutable ephemeron tables, if it works. I haven't heard of the term "uniquely represented," but I wanted a table entry to be reachable if its key was an immutable table that could still be constructed, so my implemenation interned all immutable tables based on the key and value pointers they contained.

Whereas I was trying to build data out of finite functions between finite functions (maps of maps), it looks like you're trying to build data out of finite relations between finite relations (multimaps of multimaps). It's an interesting prospect, probably more interesting than the interface you use for it (at least to me). Do you have an example of what you're trying to accomplish with it?

Yes, you are right! A finite binary relation between relation. I just found out that the Spread data structure is 'just' a finite binary relation.

Even more powerful are ternary relations, although they can be represented with binary relations. Triple stores are big ternary relations but they are mutable - and they are but one level deep.

"Near miss" use-cases are what I tend to target - e.g. the problems where people try spreadsheets but get frustrated with them. For those cases, the question isn't "what are they used for?" but rather "why aren't they used here?" If I can improve spreadsheets for today's successful use-cases too, that's a nice bonus. I do believe higher-order spreadsheets are worthy of exploration, i.e. as a means of expressing functions and expanding and displaying intermediate computations.

PL and UI designs tend to be tightly interwoven and affect one another in deep ways. A PL viewpoint is useful to understand and address the problems of spreadsheets.

Many thanks for the reference - that's a pot of gold!