Elixir implementation of algorithm

Questions / Help
, ,
1

Hello, I was wondering as there is no while loop in elixir, how would that look like written in Elixir:
while exists (s, m, sn) ∈ pending such that sn = next[s] do
next[s] := next[s]+1;
pending := pending \ {(s, m, sn)};

2

I do not really get what that algorithm does. To me it seems like you have some problem with transcription of the original one.

1 Like
3

pending is a set of processes, next is an Array

4

Ahh, ok. Now I get. I can take a look later when I will be near computer

5

Generally you would turn the while loop into an Enum.reduce and the variables that you would have mutated get passed as part of the accumulator.

1 Like
6

This appears to be a fragment from Algorithm 3.12 in “Introduction to Reliable and Secure Distributed Programming”.

Folks will be able to answer this question a lot more effectively if they have that context.

In that algorithm, pending is a set of tuples {sender, message, sequence_number} while next is a map from sender to the next sequence_number expected from that sender.

The while loop finds {sender, message_to_deliver, sequence_number} values in pending, and does three things:

  • increments next for sender
  • removes the tuple from pending
  • delivers message_to_deliver from sender
1 Like
7

Something like this would be my attempt:

pending = [
  {1, "hello1", 2},
  {1, "hello2", 1},
  {2, "hello3", 1},
  {2, "hello4", 2},
  {2, "hello5", 4}
]

next = %{
  1 => 1,
  2 => 1
}

pending_transformed =
  for {sender, message, sn} <- pending,
      into: %{},
      do: {{sender, sn}, message}

{pending_transformed, next}
|> Stream.unfold(fn
  nil ->
    nil

  {pending_transformed, next} ->
    result =
      pending_transformed
      |> Map.keys
      |> Enum.find(fn {sender, sn} -> next[sender] == sn end)

    case result do
      {sender, sn} = key ->
        {message, pending_transformed} = Map.pop!(pending_transformed, key)
        next = Map.put(next, sender, sn + 1)
        {{:send, {sender, message, sn}}, {pending_transformed, next}}

      nil ->
        {{:done, {pending_transformed, next}}, nil}
    end
end)
|> Enum.reduce_while([], fn
  {:send, msg}, acc ->
    IO.inspect(msg)
    {:cont, acc}

  {:done, rest}, _ ->
    {:halt, rest}
end)

# Output
{1, "hello2", 1}
{1, "hello1", 2}
{2, "hello3", 1}
{2, "hello4", 2}

# Result
{%{{2, 4} => "hello5"}, %{1 => 3, 2 => 3}}
1 Like
8

Do you by any chance have that algorithm in code version ?