[e-lang] Lamport Slots, what are they exactly?

Mark Miller erights at gmail.com
Sat Mar 29 14:09:44 EDT 2008


On Sat, Mar 29, 2008 at 7:53 AM, Baldur Johannsson
<zarutian+e-lang at gmail.com> wrote:
>   Is an Lamport Slot an Unum that is ordered by an Lamport Logical Clock?
>   (ordered in the sense that the progression of the lamport slot values
>    is same for all presences of the lamport slot)

No, it's ordering properties are not nearly as strong. Their named
after yet another idea[1] by the prolific Leslie Lamport, as well as
being a contraction of "Latency Accommodating Memory PORT".



>   Or is it an slot that can subscribe to another source and be
>  subscribed from other
>   such slots (or similar destinations)?

There are two levels. The low level local-slots are pass-by-proxy and
subscribe as you say. IIUC Martin Sheffler has built the
long-anticipated slot-unum level of abstraction on this, where a
single distributed unum-slot consists of a slot-presence per vat
participating in the slot-unum. A slot-presence wraps a local-slot.
The difference is that when a reference to a slot-presence is passed
between vats, it serializes and unserializes into a reference to a
presence of the same unum local to the arrival vat.

All presences of the same slot-unum should agree by construction on
which presences of the unum are _authoritative presences_. When there
is only a single fixed authoritative presence for any given unum, we
call it the _primary presence_ (after the database practice of
"primary copy replication"). More complex arrangements among
authoritative presences are possible, generally to increase
availability under various failure conditions.

Non-authoritative presences are _shadow presences_. Their local slots
are subscribed to the local-slots of authoritative presences.


          A first attempt at an Unum-update memory model


Under the conventional assumptions that the shadow presences reify
only read-access to the unum, and that everyone plays their part in
the protocol correctly, the ordering properties within a single unum
are

* Any value reported by a .get() on a presence is a value that was
earlier .set() on some authoritative presence of the same slot-unum.

* Successive .set()s on the same authoritative presence are fully
ordered by their arrival order at that presence.

* A sequence of values reported by successive .get()s on a presence
are some full order consistent with the order constraints imposed by
the .set()s.

* After a .set() on an authoritative presence, a .get() on the *same*
presence can be no less recent than that .set().

So far, the above constraints taken together specify only fail-stop
fifo ordering of updates between pairs of una. Given a static set of
presence relationships, all that's relevant is fifo plus one
additional constraint:

* Under connected quiescence, all presence of the same unum settle on
the same agreed "most recent" value.

The dynamic case must take account of unum-reference passing. The
generalization of E-order applied to dynamic unum update order is

* When A is constrained to report a value at least as recent as X, if
a reference to A is passed and arrives as a reference to presence B, B
is then additionally constrained to reports values no less recent than
X.



[*] which I have not been able to find.

-- 
Text by me above is hereby placed in the public domain

 Cheers,
 --MarkM


More information about the e-lang mailing list