Two algorithms, RA1 and RA2, have been proposed by Joung (1998b) for the Congenial Talking Philosophers problem in asynchronous complete networks. RA1 is a straightforward modification from Ricart and Agrawala's algorithm for n-process exclusion. It works as follows:

• When a philosopher wishes to attend a forum, it multicasts a request message to every other philosopher, and enters the meeting room only when all philosophers have replied to its request. Request messages are processed as follows: When a philosopher P_j receives a request by P_i, it replies immediately if it is not interested in a different forum, or it is interested in a different forum and its priority is lower than that of P_i. Otherwise, P_j is interested in a different forum and has priority over P_i. P_j then defers the reply to the request until it has finished a forum and exited the meeting room.
• Priorities are assigned as follows: When a philosopher wishes to attend a forum, its priority value is set to the value of its current logical clock. The larger the value, the lower the priority. The philosopher keeps this value until it has attended a forum, and then resets its priority to the lowest.

  For a more detailed description of the algorithm and its analysis, please refer to Joung (1998b). For logical clocks, please see Lamport's seminal paper published in Communications of the ACM, July 1978.

Workbench of RA1.

One may have noted from the workbench for RA1 that most of the time, only one philosopher can be in the meeting room, regardless of the fact that some other philosophers may be waiting for the same forum simultaneously. Indeed, by the simulation study in Joung (1998b), RA1 provides virtually no concurrency; its performance is only slightly better than one that strictly imposes mutual exclusion on every entry to the meeting room!

RA2 significantly improves the performance of RA1. It does so by using vector timestamps and allowing philosophers in the meeting room to capture other philosophers to join the ongoing forum. In RA2, each philosopher P_i maintains two vector logical clocks VSN and VF, where VSN[j] records a count of requests that have occurred at P_j and that are known at P_i, and VF[j] records a count of entries to the meeting room that are made by P_j and that are known at P_i. VSN is used to implement the priority, and VF is used to let philosophers know if acknowledgments (i.e., replies) to their requests are "up-to-date". RA2 works as follows:

• Like RA1, a philosopher P_i multicasts a request to every other philosopher when it wishes to attend a forum. Unlike RA1, however, the philosopher may enter the meeting room either because every philosopher has replied to its request with an up-to-date acknowledgment, or because some philosopher has replied to its request with a Start message to join an ongoing forum. In the former case, we say that P_i enters the meeting room as a captor, while in the latter case P_i enters the meeting room as a captive.
• Upon receiving a request by P_i, P_j uses the following rules to determine how to reply to the request:
  • P_j replies with an acknowledgment immediately if either (1)it is also interested in the same forum but is not a captor in the meeting room, or (2) it is not interested in the same forum, is not in the meeting room, and has a priority lower than P_i.
  • P_j replies with a Start message if it is in the same forum as that requested by P_i and is a captor in the meeting room.
  • Otherwise, P_j must be interested in a different forum, and either it is in the meeting room, or has a priority higher than P_i. It delays the reply until it has exited the meeting room, and then replies with an acknowledgment.

  Priorities are implemented by the vector logical clocks VSN and maintained by timestamping each request message with the value of the requesting philosopher's VSN. Each acknowledgment is timestamped by the value of the replying philosopher's vector logical clocks VF. This vector timestamp is used by the receiving philosopher to update its VF and to determine whether the acknowledgment is up-to-date. In the algorithm, the receiving philosopher's VF[k] must be no greater than VF'[k] carried by an acknowledgment from P_k in order for the acknowledgment to be considered up-to-date.

  Workbench of RA2.