Events that are not concurrent can be ordered in time. For example, if event e1 can be shown to always precede event e2 in time, then e1 and e2 are obviously not concurrent. Notationally we indicate that e1 precedes e2 by writing e1->e2. Note that the precedes relation is transitive, as expected. Thus if e1->e2 and e2->e3, then we can also note that e1->e3.
Sequential events in a single computation are not concurrent. For example, if a particular computation performs the operations identified by events e1, e2 and e3 in that order, then clearly and e1->e2 and e2->e3.
Computations in a distributed system communicate by sending messages. If event esend corresponds to the sending of a message by one computation, and event erecv corresponds to the reception of that message by a different computation, then we can always note that esend->erecv, since a message cannot be received before it is sent.
In this problem you will be supplied with lists of sequential events for an arbitrary number of computations, and the identification of an arbitrary number of messages sent between these computations. Your task is to identify those pairs of events that are concurrent.
For each test case, print the test case number (they are numbered sequentially starting with 1), the number of pairs of concurrent events for the test case, and any two pair of the concurrent event names. If there is only one concurrent pair of events, just print it. And if there are no concurrent events, then state that fact.
2 2 e1 e2 2 e3 e4 1 e3 e1 0There are two computations. In the first e1->e2 and in the second e3->e4. A single message is sent from e3 to e1, which means e3->e1. Using the transitive property of the precedes relation we can additionally determine that e3->e2. This leaves the pairs (e1,e4) and (e2,e4) as concurrent events.
2 2 e1 e2 2 e3 e4 1 e3 e1 3 3 one two three 2 four five 3 six seven eight 2 one four five six 1 3 x y zee 0 2 2 alpha beta 1 gamma 1 gamma beta 0
Case 1, 2 concurrent events: (e1,e4) (e2,e4) Case 2, 10 concurrent events: (two,four) (two,five) Case 3, no concurrent events. Case 4, 1 concurrent events: (alpha,gamma)