[erlang-questions] Question about message passing paradigm

[Tim Watson]

Hi Edwin,

I hadn't thought of using timeouts like this, but yes, it sounds like
a viable idea. I guess my concern(s) about liveliness still stand, but
Richards use of a last minute collection strategy seems to address
that quite well. I'd try to avoid this kind of locking protocol if at
all possible though, refactoring towards a push based design (as per
Richard and Hynek Vychodil's discussion elsewhere on this thread), but
where this is just the art of the possible, it seems good to me.

Cheers,

Tim

2008/7/1 Edwin Fine <erlang-questions_efine@REDACTED>:
> Well, Richard's response to my question (and the OP's question) was most
> enlightening.
>
> I believe that deadlocks can be dealt with quite easily by the judicious
> choice of timeouts. For example, in the suggestions I posted involving the
> use of a gen_fsm behavior, it would be relatively trivial to add a timeout
> that reverts the state back to "unlocked" should the set of operations not
> be complete within a reasonable period of time. Indeed, I think Joe had an
> example of that in the book, or else the gen_fsm documentation does, showing
> a gen_fsm used to hold the combination to a safe. After a period of time, if
> digits are entered the safe is not unlocked, the state reverts to "locked"
> again and it has to start from scratch.
>
> Richard's idea of sending individual queries which don't allow the receiver
> to handle any other queries until it gets an ACK could also be protected by
> timeouts.
>
> In this way, I don't think the broadcasting of deaths would be necessary: if
> a process is not "unlocked" in a reasonable amount of time, it unlocks
> itself. This covers a multitude of sins: process death, network death,
> programmer death (well, maybe not :).
>
> As Richard aptly pointed out, I tend to see solutions in a framework of
> Erlang/OTP, not pure Erlang the language.  So if using a gen_fsm behavior,
> erlang:send_after() is perfect for this timeout strategy.
>
> For example:
>
> try
>    A = thing_a:get_value(),
>    B = thing_b:get_value(),
>    C = thing_c:get_value(),
>    {ok, {A, B, C}}
> catch
>    Cls:Exc -> {error, {Cls, Exc}}
> after
>    thing_c:release(),
>    thing_b:release(),
>    thing_a:release()
> end.
>
> Even if the node running the above code crashes, if timeouts exist in
> thing_a, thing_b, and thing_c, they will unlock themselves regardless of if
> release() is called. Of course, you could get a spurious old release()
> coming in after a timeout occurred, messing up the next transaction, but you
> could deal with that by using a common ref to correlate the three. If a
> stale release came in with the wrong ref, it would be ignored.
>
> I dunno. Too simplistic? Thoughts?
>
> Edwin
>
> On Tue, Jul 1, 2008 at 3:06 AM, Tim Watson <watson.timothy@REDACTED> wrote:
>>
>> Hi Edwin,
>>
>> I'm quite fresh around here too and I agree, someone definitely needs
>> to write up some common patterns for the paradigm. I also suggested a
>> locking solution using selective receive, but being a little tired, I
>> managed to post it with the wrong subject line. Twice. <sigh>
>>
>> Still, it wasn't really a solution, but a discussion about the
>> applicability of selective receive - I can't see another way of doing
>> this. My concern with the approach is that there is no way for a
>> process to "safely lock itself" unless it can trap exists from the
>> process trying to "acquire the lock," as it were. If A starts
>> communicating with B and asks B to stay in a particular state until it
>> [A] is ready, then A had better broadcast it's death if anything goes
>> wrong so that B can "unlock itself," for want of a better description.
>> The more processes are involved, the more interesting that gets. My
>> original solution was to lock each container process against a
>> specific value (key) and continue to serve reads while blocking
>> writes. My solution doesn't however, deal with process failures very
>> well! Here's a quick stab:
>>
>> loop(State, LockList) ->
>>   %% ... some interesting code...
>>   receive
>>       { SenderPid, acquire, ItemId } ->
>>           case get_item(ItemId, LockList) of
>>               { acquired, Response } -> SenderPid ! { { acquired, ok
>> }, Response }
>>             ; _ -> SenderPid ! error
>>           end,
>>           loop(State, [ ItemId | LockList ])
>>     ; { SenderPid, read, ItemId } ->
>>           SenderPid ! { { read, ok }, get_item_readonly(ItemId) },
>>           loop(State, LockList)
>>     ; { SenderPid, write, { ItemId, Value } } ->
>>           { acquired, Response } = get_item(ItemId, LockList),
>>           Write = write_item(ItemId, Value),
>>           SenderPid ! { { write, ok }, Write }
>>   end.
>>
>> Obviously I've imagined some code in get_item that checks the lock
>> list before a successful acquire, etc. This solution is non blocking
>> for reads, but in the event that you try and get a write (i.e,
>> acquire) a locked item, the process dies with a pattern matching
>> failure (based on the assumption that get_item will return an 'error'
>> atom or something like that, on failure). This is hardly a solution,
>> but I wanted to look at the selective receive bit. What happens if the
>> process who "acquired" item X dies and doesn't notify you!? X sort of
>> "goes missing,", which is hardly ideal. In your example, where the
>> individual processes actually block until released, a fatal error in
>> the lock owner will deadlock the system.
>>
>> You could always check the sender pid against your linked nodes and
>> link to it if it's not already in there. Personally, I don't like this
>> approach though - it all feels like a kludge. I like the idea of
>> changing from a pull to a push design (mentioned earlier), as this
>> whole locking multiple processes feels horrible. Think about a typical
>> (Joe forgive me) OO implementation in java or some such. The number 1
>> rule is don't call into some other object while holding a lock, as
>> you've no idea what might happen and you might end up deadlocked. This
>> question raises the same questions for me - do I really want these
>> distributed locks cropping up all over the place? If data consistency
>> is really that important, then maybe we should find a better way to
>> accumulate the data we need to perform a given operation.
>>
>> As another contrived example, I can't imagine that if in the process
>> of say, selling broadband, you need to fist check the network
>> inventory, then provision an engineer and finally set up a billing
>> record against a customer account, that you'd want to deal with the
>> locking protocol in this way. Say the network inventory and engineer
>> availability rosters are in different parts of the system, which you
>> need to call via some RPC (say they're not actual Erlang nodes, but
>> some java application that you hit over HTTP), or maybe just in a
>> database or whatever. I would've thought that the safest way to do
>> this with pessimistic locking is surely to lock the whole provisioning
>> activity (e.g., upon receiving the initial call) - this might entail
>> exposing the provisioning process as a gen_server and performing the
>> locking there (this might even happen implicitly, if you use the
>> synchronous 'call' function instead of the async 'cast') or something
>> like that. This is going to have a bad effect on your liveliness,
>> naturally, but that's life. A course grained lock is safer, but less
>> lively. A lock that doesn't deal with error conditions sounds bad
>> though.
>>
>> Hopefully someone with a bit more experience will chime in here and
>> point out the obvious to us new folk!? ......
>>
>> Cheers,
>>
>> Tim Watson
>>
>>
>> > ------------------------------
>> >
>> > Message: 7
>> > Date: Mon, 30 Jun 2008 23:42:51 -0400
>> > From: "Edwin Fine" <erlang-questions_efine@REDACTED>
>> > Subject: Re: [erlang-questions] Question about message passing
>> >        paradigm
>> > To: "Richard A. O'Keefe" <ok@REDACTED>
>> > Cc: Mike T <talmage.news@REDACTED>, erlang-questions@REDACTED
>> > Message-ID:
>> >        <6c2563b20806302042q2605badie220bd1acb7d72b3@REDACTED>
>> > Content-Type: text/plain; charset="utf-8"
>> >
>> > Richard,
>> >
>> > I'm new to Erlang and FP, and I want to learn from my mistakes or
>> > misunderstandings. Please could you critique the suggestion I sent in
>> > regarding this problem? The fact that nobody commented means either that
>> > it
>> > was (a) totally naive and not worthy of comment (or to spare my
>> > feelings),
>> > or (b) such a good idea that all were rendered speechless with
>> > admiration.
>> > Somehow the probability of (b) seems rather low. So... where did I go
>> > wrong?
>> >
>> > Regards,
>> > Edwin FIne
>> >
>> > On Mon, Jun 30, 2008 at 11:33 PM, Richard A. O'Keefe <ok@REDACTED>
>> > wrote:
>> >
>> >> The problem we are discussing is
>> >>    processes B, C, D hold information X, Y, Z respectively;
>> >>    process A wants a coherent snapshot of X, Y,Z.
>> >>
>> >> There are actually two slightly different cases depending on
>> >> A needs "X Y Z as of *now*" (A, B, C, and D must all
>> >> synchronise), or A needs "X Y Z as of *some* time in the
>> >> recent past" (B, C, and D must all synchronise but can then
>> >> send the information to A without waiting for A to receive it).
>> >>
>> >> I like this problem because it is simple yet subtle.
>> >> One way that it is subtle is that in "multithread" programming
>> >> most people STILL think in terms of a single absolute time
>> >> shared by all threads.  (After all, there _is_ such a thing,
>> >> the system clock.  And yes, it's not exactly true, but it's
>> >> close enough to make people _think_ it's true.)  But when you
>> >> start thinking about Erlang and especially *distributed*
>> >> Erlang, you start realising that "now" is a pretty fuzzy
>> >> concept.
>> >>
>> >> To me, the easiest approach to *think* was
>> >>
>> >>        A sends "tell me X" to B, "tell me Y" to C,
>> >>          and "tell me Z" to D in any order,
>> >>          then does three receives in any order to
>> >>          collect the results, then
>> >>          sends "thanks" to B, C, and D in any order.
>> >>
>> >>        B receives "tell me X" from A, computes X,
>> >>          sends "here is X" to A, then waits for
>> >>          "thanks" from A.
>> >>
>> >>        C and D are just like B.
>> >>
>> >> This has 9 messages compared, but it is symmetric, and it is
>> >> actually pretty close to the locking technique (to "lock" a
>> >> process, send it a message asking it to wait, receive its
>> >> acceptance, and then send it a message telling it to proceed).
>> >> This extends to any number of processes E, F, G, ... and none
>> >> of the processes except A has to know about any of the others.
>> >>
>> >> On 30 Jun 2008, at 6:45 pm, Erik Reitsma proposed a scheme
>> >> that doesn't actually need any functions to be sent around
>> >> (which is nice if you are doing distribution):
>> >>
>> >>        A sends "I need X Y and Z, ask C and D for Y and Z"
>> >>          to B then waits.
>> >>        B sends "A needs Y and Z, ask D for Z, here is X"
>> >>          to C.  B then waits for the go-ahead.
>> >>        C sends "A needs Z, here are X and Y" to D,
>> >>          then waits.
>> >>        D sends "here are X Y and Z" to A.
>> >>          If a four-way synchronisation is wanted, D waits.
>> >>          If a three-way is wanted, it doesn't.
>> >>        A receives X, Y, and Z.  It sends "go ahead" to B
>> >>          and C (and to D if four-way is wanted).
>> >>
>> >> This is 7 messages if the "NOW" reading with four-way
>> >> synchronisation is wanted, or 6 if the "some time in the
>> >> recent past" reading with three-way synchronisation is
>> >> wanted.  Since B, C, and D have to be told that their
>> >> information is needed and A has to receive the results,
>> >> four messages are needed.
>> >>
>> >> Can it be done in fewer than 7 (or 6) messages?
>> >> Are there other readings of the requirements that I've missed?
>> >> How do/should we think about these problems?
>> >>
>> >> Pace Dijkstra, I'm afraid that I came up with the schemes
>> >> above in a very anthropomorphic CRC-card-ish way:
>> >>        who knows what?
>> >>        who needs to know what?
>> >>        can the message count be reduced if I ask
>> >>        someone to do something for me?
>> >> plus a sort of intuitive idea that
>> >>        to get N processes to synchronise, get all
>> >>        but 1 of them waiting for something
>> >>
>> >> There has to be a tutorial, perhaps even a textbook, waiting
>> >> to be written about "how to think about messages".
>> >>
>> >>
>> >>
>> >>
>> >
>> >
>> > --
>> > The great enemy of the truth is very often not the lie -- deliberate,
>> > contrived and dishonest, but the myth, persistent, persuasive, and
>> > unrealistic. Belief in myths allows the comfort of opinion without the
>> > discomfort of thought.
>> > John F. Kennedy 35th president of US 1961-1963 (1917 - 1963)
>> > -------------- next part --------------
>> > An HTML attachment was scrubbed...
>> > URL:
>> > http://www.erlang.org/pipermail/erlang-questions/attachments/20080630/5455b955/attachment.html
>> >
>> > ------------------------------
>> >
>> > _______________________________________________
>> > erlang-questions mailing list
>> > erlang-questions@REDACTED
>> > http://www.erlang.org/mailman/listinfo/erlang-questions
>> >
>> > End of erlang-questions Digest, Vol 14, Issue 1
>> > ***********************************************
>> >
>>
>
>
>
> --
> The great enemy of the truth is very often not the lie -- deliberate,
> contrived and dishonest, but the myth, persistent, persuasive, and
> unrealistic. Belief in myths allows the comfort of opinion without the
> discomfort of thought.
> John F. Kennedy 35th president of US 1961-1963 (1917 - 1963)