1
$\begingroup$

Could someone explain to me the following quote from Interaction Nets 1991 paper by Simon Gay. To be specific, what are bad cycles and how connected ports in the same partition eliminates them?

The solution is to divide the ports of each agent into partitions which are used in the following way. If a net is built up from the empty net by successively adding agents, which may or may not be connected to existing agents, then at any time the net consists of a number of connected components. Connecting two or more ports of a new agent to a single component forms a cycle in the net. The rule is that this can only be done if all the ports being connected to the same component are in the same partition. This guarantees that nets containing bad cycles cannot be constructed; and, since the same constraint applies to the net on the right hand side of an interaction rule, that no bad cycles can be introduced by reductions.

Improve this question
$\endgroup$
3
  • $\begingroup$ Can you edit your post to ask a more specific question and clarify what you are asking? "I cannot fully get..." is not a question. I'm not sure what you mean by "what kind..." or what it means to "element" a cycle. It might help to tell us what you do understand and summarize the main ideas of the paper as you do understand them. $\endgroup$
    – D.W.
    Commented Jan 20, 2023 at 6:48
  • $\begingroup$ @D.W. Hi and thx for passing by. I have added more specific questions in my edit. Hopefully, someone can help me answering them. $\endgroup$
    – geeko
    Commented Jan 20, 2023 at 9:54
  • 1
    $\begingroup$ I am not sure I'll find the time to write an answer (sorry!), but you should look at Lafont's original paper (dl.acm.org/doi/pdf/10.1145/96709.96718), it defines everything formally and is much clearer. $\endgroup$
    – Damiano Mazza
    Commented Jan 25, 2023 at 9:21

1 Answer 1

Reset to default
1
$\begingroup$

Quoting from the paper:

It is possible to define rules which lead to non-terminating computations, [...] but further constraints on nets can ensure that when a sequence of reductions terminates, the result can be interpreted as a meaningful answer rather than a deadlock situation.

and:

But if the net contains cycles, the situation is a deadlock, and it is these cases which should be eliminated.

The goal is apparently to avoid deadlock. Thus, my reading is that the design seeks to find a way to prevent construction of cycles that could cause deadlock.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hi again. To understand bad cycles better, what is the difference between these cycles: "However, it is possible to distinguish between innocuous and pathological cycles"? What happens when it is say a deadlock that is different than when it is not? $\endgroup$
    – geeko
    Commented Jan 21, 2023 at 4:46
  • $\begingroup$ Also, I would like someone to explain this solution to me and why it works: "The solution is to divide the ports of each agent into partitions which are used in the following way. If a net is built up from the empty net by successively adding agents, which may or may not be connected to existing agents, then at any time the net consists of a number of connected components. Connecting two or more ports of a new agent to a single component forms a cycle in the net. The rule is that this can only be done if all the ports being connected to the same component are in the same partition." $\endgroup$
    – geeko
    Commented Jan 21, 2023 at 4:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.