I wouldn’t call it a deadlock, but rather a race condition. Too see why it happens, let’s first name these processes:

def sample do
  # process A
  lab_pid = self()

  spawn_link(fn ->
    # process B

    spawn_link(fn ->
      # process C

      Process.flag(:trap_exit, true)

      receive do
        {:EXIT, _pid, :normal} ->
          send(lab_pid, :done)
      end
    end)
  end)

  receive do
    msg ->
      msg
  end
end

So without a timeout, it’s possible that process B stops before Process.flag in process C has been invoked. This happens because spawn and spawn_link are asynchronous. When these functions return, the process has been created, but it’s possible that they still haven’t executed any instruction.

So in this scenario, if process C starts trapping exits after process B had stopped, the corresponding exit signal won’t be converted into a message. So now, you have process C waiting forever for a message which will never arrive, and consequently, process A is also waiting forever for a message which process C will never send.

The solution would be to use synchronous start, e.g. with :proc_lib:

def sample do
  lab_pid = self()

  spawn_link(fn ->
    :proc_lib.start_link(Kernel, :apply, [fn ->
      Process.flag(:trap_exit, true)

      # `:proc_lib.start_link` will return after this function is invoked
      :proc_lib.init_ack({:ok, self()})

      receive do
        {:EXIT, _pid, :normal} ->
          send(lab_pid, :done)
      end
    end, []])
  end)

  receive do
    msg ->
      msg
  end
end

This is what :proc_lib.start_link and :proc_lib.init_ack do under the hood too See here and here.

This is also a good example as to why monitors are often better then links+traps.