{"id":140,"date":"2012-03-25T17:35:53","date_gmt":"2012-03-25T22:35:53","guid":{"rendered":"https:\/\/dalnefre.com\/wp\/?p=140"},"modified":"2016-03-29T15:01:36","modified_gmt":"2016-03-29T20:01:36","slug":"futures-and-capabilities","status":"publish","type":"post","link":"https:\/\/dalnefre.com\/wp\/2012\/03\/futures-and-capabilities\/","title":{"rendered":"Futures and Capabilities"},"content":{"rendered":"

In the Actor Model, concurrency is the default. Sequencing must by arranged explicitly. An important case of sequencing occurs when there is a data dependency between different parts of a system. One part produces a value that another part needs to perform its function.<\/p>\n

\nOne mechanism for sequencing data-dependent operations is to create a Future<\/a>. This is sometimes known as a single-assignment data-flow variable (e.g.: in Mozart\/Oz<\/a>) [1]. It is basically a storage cell that can be written to only once, but read from multiple times. If a read occurs before the write, the read-reply is delayed until the write provides a value. This effectively suspends readers until the write occurs. Note, however, that there is no blocking in an actor system. The asynchronous reply to a read request is simply deferred until a value is available.<\/p>\n

<\/a><\/p>\n

Future<\/h2>\n

When an actor representing a Future is created, its value is unknown. In this state, it expects either a #read<\/code> or a #write<\/code> request.<\/p>\n

\r\nLET future_beh = \\msg.[\r\n\tCASE msg OF\r\n\t(cust, #write, value) : [\r\n\t\tBECOME value_beh(value)\r\n\t\tSEND SELF TO cust\r\n\t]\r\n\t(cust, #read) : [\r\n\t\tBECOME wait_beh(cust)\r\n\t]\r\n\tEND\r\n]\r\n<\/pre>\n
When an actor with future_beh<\/var> receives a #write<\/code> request, it becomes bound<\/a> to the value<\/var> and sends its SELF<\/code> to the customer cust<\/var>.  This serves as a synchronization signal, indicating that the value<\/var> has been set.<\/p>\n
\nWhen an actor with future_beh<\/var> receives a #read<\/code> request, it becomes waiting<\/a> for the customer cust<\/var>.  Notice that there is no reply<\/strong> to the customer at this time.<\/p>\n
<\/a><\/p>\n
Value<\/h3>\n
When a Future has been bound to a value, it expects only #read<\/code> requests.  Any other messages (including #write<\/code> requests) are silently ignored.<\/p>\n
\r\nLET value_beh(value) = \\msg.[\r\n\tCASE msg OF\r\n\t(cust, #read) : [\r\n\t\tSEND value TO cust\r\n\t]\r\n\tEND\r\n]\r\n<\/pre>\n
When an actor with value_beh<\/var> receives a #read<\/code> request, it simply sends its value<\/var> to the customer cust<\/var>.<\/p>\n
<\/a><\/p>\n
Wait<\/h3>\n
When a Future receives #read<\/code> requests before a value is provided by a #write<\/code> request, the deferred readers are buffered in the waiting actor.<\/p>\n
\r\nLET wait_beh(waiting) = \\msg.[\r\n\tCASE msg OF\r\n\t(cust, #write, value) : [\r\n\t\tBECOME value_beh(value)\r\n\t\tSEND SELF TO cust\r\n\t\tSEND waiting TO NEW broadcast_beh(value)\r\n\t]\r\n\t(cust, #read) : [\r\n\t\tBECOME wait_beh(cust, waiting)\r\n\t]\r\n\tEND\r\n]\r\n<\/pre>\n
When an actor with wait_beh<\/var> receives a #write<\/code> request, it becomes bound<\/a> to the value<\/var> and sends its SELF<\/code> to the customer cust<\/var>.  Now that a value<\/var> is available, it creates a broadcast<\/a> actor to send replies to all the waiting<\/var> readers.<\/p>\n
\nWhen an actor with wait_beh<\/var> receives a #read<\/code> request, it adds the customer cust<\/var> to the list of deferred readers.<\/p>\n
<\/a><\/p>\n
Broadcast<\/h3>\n
A Broadcast actor is created specifically to send a value<\/var> to a list of customers.  A Future uses a Broadcast actor to deliver replies to deferred readers.<\/p>\n
\r\nLET broadcast_beh(value) = \\waiting.[\r\n\tCASE waiting OF\r\n\t(first, rest) : [\r\n\t\tSEND value TO first\r\n\t\tSEND rest TO SELF\r\n\t]\r\n\tlast : [\r\n\t\tSEND value TO last\r\n\t]\r\n\tEND\r\n]\r\n<\/pre>\n
An actor with broadcast_beh<\/var> is created with a value<\/var>.  When it receives a waiting<\/var> list, it uses pattern matching to determine if the list is compound, or just a single value.  If the list is compound (a pair), it sends the value<\/var> to the first<\/var> customer, and sends the rest<\/var> of the waiting list back to itself.  If the list is just a single value, it simply sends the value<\/var> to the last<\/var> customer.<\/p>\n
\nOnce the value<\/var> has been delivered to all the waiting<\/var> customers, there will be no further references to the Broadcast actor, so it can be reclaimed by the garbage-collector.<\/p>\n
<\/a><\/p>\n
Example<\/h3>\n
The following example demonstrates the operation of a Future receiving concurrent #read<\/code> and #write<\/code> requests.  We create two customers, foo<\/var> and bar<\/var>, which simply label any message they receive and send it to the console (via println<\/var>).  These customers are used in two concurrent #read<\/code> requests for the Future var<\/var>.  A concurrent #write<\/code> request sets the value of the Future to 42<\/code>.  The customer for the #write<\/code> request is sink<\/var> (which ignores all messages) because, in this case, we don’t care about when the value is set.<\/p>\n
\r\nCREATE var WITH future_beh\r\nCREATE foo WITH \\msg.[ SEND (#foo, msg) TO println ]\r\nCREATE bar WITH \\msg.[ SEND (#bar, msg) TO println ]\r\nSEND (foo, #read) TO var\r\nSEND (bar, #read) TO var\r\nSEND (sink, #write, 42) TO var\r\n<\/pre>\n
Since the #read<\/code> and #write<\/code> requests are issued concurrently, the Future var<\/var> will receive them in a non-deterministic order.  The #write<\/code> request could arrive first, in which case the #read<\/code> requests will be satisfied immediately.  The #read<\/code> requests could both arrive before the #write<\/code>, in which case the read-replies will be deferred until the value is set by #write<\/code>.  Or, the #write<\/code> request could arrive between the two #read<\/code> requests, as shown in Figure 1.<\/p>\n
\"\"<\/a>
Figure 1 - Future Message Flow<\/p><\/div>\n
<\/a><\/p>\n
Capability<\/h2>\n
Access to a Future, as described above<\/a>, implies the capability [2] to #read<\/code> or #write<\/code> its value.  In many cases we would like to separate those capabilities.  We may want to give read-only access to several potential consumers, while reserving write access for the producer.  One powerful feature of pure-actor systems is that Actors act as security capabilities<\/a>.  In order to attenuate the capability of a client, we simply create a proxy<\/a> actor that enforces our desired security policy.<\/p>\n
\r\nLET read_only_beh(future) = \\msg.[\r\n\tCASE msg OF\r\n\t(cust, #read) : [\r\n\t\tSEND msg TO future\r\n\t]\r\n\tEND\r\n]\r\nCREATE ro_var WITH read_only_beh(var)\r\n<\/pre>\n
An actor with read_only_beh<\/var> is created with a reference to a future<\/var>.  When a #read<\/code> request is received, the message is forwarded to the future<\/var>.  All other messages are silently ignored.<\/p>\n
\nSimilarly, we might want to create a proxy that provides only write capability.  This is slightly more complicated due to the write synchronization signal.  The Future responds to a #write<\/code> request by sending its SELF<\/code> back to the customer.  Our proxy must intercept this response and substitute its own identity to maintain encapsulation of the future.<\/p>\n
\r\nLET write_sync_beh(cust, msg) = \\_.[ SEND msg TO cust ]\r\nLET write_only_beh(future) = \\msg.[\r\n\tCASE msg OF\r\n\t(cust, #write, value) : [\r\n\t\tSEND (k_write, #write, value) TO future\r\n\t\tCREATE k_write WITH write_sync_beh(cust, SELF)\r\n\t]\r\n\tEND\r\n]\r\nCREATE wo_var WITH write_only_beh(var)\r\n<\/pre>\n
When an actor with write_only_beh<\/var> receives a #write<\/code> request, it sends a #write<\/code> request to the future<\/var>, providing a customer k_write<\/var> with write_sync_beh<\/var>.  When the future responds, k_write<\/var> sends the identity of the proxy to the original customer cust<\/var>.<\/p>\n
<\/a><\/p>\n
Race<\/h3>\n
Sometimes it is useful to arrange a race among multiple producers.  You may have multiple algorithms competing to provide a result.  Different algorithms may win under different circumstances.  The first one to determine a result will #write<\/code> to the Future.  Subsequent results are ignored.  In this case, the write synchronization signal is unimportant, so we change the protocol to expect a #result<\/code> message with no customer.  This behavior acts like an adapter<\/a> between the racers (sending #result<\/code> messages, expecting no reply) and the future (expecting #write<\/code> requests and sending a synchronization reply).<\/p>\n
\r\nLET result_race_beh(future) = \\msg.[\r\n\tCASE msg OF\r\n\t(#result, value) : [\r\n\t\tSEND (SELF, #write, value) TO future\r\n\t\tBECOME \\_.[]\r\n\t]\r\n\tEND\r\n]\r\n<\/pre>\n
When an actor with result_race_beh<\/var> receives a #result<\/code> message, it sends a #write<\/code> request to the future<\/var> with the result value<\/var> and its SELF<\/code> as the customer.  Then it becomes a behavior that ignores all subsequent messages.  Note that this serves two purposes; to ignore any other race results, and to throw away the write synchronization signal.<\/p>\n
<\/a><\/p>\n
Summary<\/h2>\n
Futures are a fundamental synchronization mechanism in concurrent systems.  We have shown how futures work through an actor-based description, illustrating the events that transition a Future through its life-cycle.  Building on that foundation, we have demonstrated how, following the Object Capability Model<\/a>, we can exercise fine-grained control over access to the Future.  This is extended to the case of arranging a race among concurrent speculative computations.<\/p>\n
<\/a><\/p>\n
References<\/h2>\n
\n
[1]<\/dt>\n
P. Van Roy, S. Haridi. Concepts, Techniques, and Models of Computer Programming<\/em><\/a>. MIT Press, 2004.<\/dd>\n
[2]<\/dt>\n
J. Dennis, E. Van Horn.  Programming Semantics for Multiprogrammed Computations<\/a>. ACM Conference on Programming Languages and Pragmatics, San Dimas, CA, August, 1965.<\/dd>\n<\/dl>\n","protected":false},"excerpt":{"rendered":"
In the Actor Model, concurrency is the default. Sequencing must by arranged explicitly. An important case of sequencing occurs when there is a data dependency between different parts of a system. One part produces a value that another part needs to perform its function. One mechanism for sequencing data-dependent operations is to create a Future. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[4,84,26,16,49,23,12,15,79,80,81,17,83,82,24,30,19],"class_list":["post-140","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-actor","tag-adapter","tag-asynchronous","tag-blocking","tag-capability","tag-concurrency","tag-data-flow","tag-deadlock","tag-dependency","tag-future","tag-promise","tag-protocol","tag-proxy","tag-security","tag-sequence","tag-synchronization","tag-value"],"_links":{"self":[{"href":"https:\/\/dalnefre.com\/wp\/wp-json\/wp\/v2\/posts\/140","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dalnefre.com\/wp\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dalnefre.com\/wp\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dalnefre.com\/wp\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dalnefre.com\/wp\/wp-json\/wp\/v2\/comments?post=140"}],"version-history":[{"count":0,"href":"https:\/\/dalnefre.com\/wp\/wp-json\/wp\/v2\/posts\/140\/revisions"}],"wp:attachment":[{"href":"https:\/\/dalnefre.com\/wp\/wp-json\/wp\/v2\/media?parent=140"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dalnefre.com\/wp\/wp-json\/wp\/v2\/categories?post=140"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dalnefre.com\/wp\/wp-json\/wp\/v2\/tags?post=140"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}