For more up-to-date notes see http://www.cs.yale.edu/homes/aspnes/classes/465/notes.pdf.

The session problem demonstrates some limitations on globally simulating a synchronous message-passing system with an asynchronous message-passing system. In a global simulation, our goal is to produce a simulation that looks synchronous "from the outside"; that is, that looks synchronous to an observer that can see the entire schedule. In contrast, a synchronizer (see Synchronizers) produces a simulation that looks synchronous "from the inside"—the resulting execution is indistinguishable from a synchronous execution to any of the processes, but an outside observer can see that different processes execute different rounds at different times.

In our description, we will mostly follow AttiyaWelch §6.2.2; see AttiyaWelch for references on the origin of the problem.

A solution to the session problem is an asynchronous protocol in which each process repeatedly executes some special action. Our goal is to guarantee that these special actions group into s sessions, where a session is an interval of time in which every process executes at least one special action. We also want the protocol to terminate: this means that in every execution, every process executes a finite number of special actions.

A synchronous system can solve this problem trivially in s rounds: each process executes one special action per round. For an asynchronous system, a lower bound of Attiya and Mavronicolas (based on an earlier bound of Arjomandi et. al., who defined the problem in a slightly different communication model), shows that if the diameter of the network is D, there is no solution to the s-session problem that takes (s-1)D time or less in the worst case. The argument is based on reordering events in any such execution to produce fewer than s sessions, using the happens-before relation from LogicalClocks.

1. Outline of the proof

(See AttiyaWelch §6.2.2 for the real proof.)

Fix some algorithm A for solving the s-session problem, and suppose that its worst-case time complexity is (s-1)D or less. Consider some synchronous execution of A (that is, one where the adversary scheduler happens to arrange the schedule to be synchronous) that takes (s-1)D rounds or less. Divide this execution into two segments: an initial segment β that includes all rounds with special actions, and a suffix δ that includes any extra rounds where the algorithm is still floundering around. We will mostly ignore δ, but we have to leave it in to allow for the possibility that whatever is happening there is important for the algorithm to work (e.g. to detect termination).

We now want to perform a causal shuffle on β that leaves it with only s-1 sessions. The first step is to chop β into at most s-1 segments β₁,β₂, ... of at most D rounds each. Because the diameter of the network is D, there exist processes p₀ and p₁ such that no chain of messages starting at p₀ within some segment reaches p₁ before the end of the segment. It follows that for any events e₀ of p₀ and e₁ of p₁ in the same segment β_i, it is not the case that e₀⇒_βδe₁. So there exists a causal shuffle of β_i that puts all events of p₀ after all events of p₁. By a symmetrical argument, we can similarly put all events of p₁ after all events of p₀. In both cases the resulting schedule is indistinguishable by all processes from the original.

So now we apply these shuffles to each of the segments β_i in alternating order: p₀ goes first in the even-numbered segments and p₁ goes first in the odd-numbered segments, yielding a sequence of shuffled segments β'_i. This has the effect of putting the p₀ events together, as in this example with (s-1) = 4:

• βδ|(p₀,p₁)
  = β₁β₂β₃β₄δ|(p₀,p₁)
  = β'₁β'₂β'₃β'₄δ|(p₀,p₁)
  = (p₁p₀) (p₀p₁) (p₁p₀) (p₀p₁) δ
  = p₁ (p₀p₀) (p₁p₁) (p₀p₀) p₁ δ

(here each p₀, p₁ stands in for a sequence of events of each process).

Now let's count sessions. We can't end a session until we reach a point where both processes have taken at least one step since the end of the last session. If we mark with a slash the earliest places where this can happen, we get a picture like this:

• p₁ p₀/p₀ p₁/p₁ p₀/p₀ p₁/p₁ δ

We have at most (s-1) sessions! This concludes the proof.

CategoryDistributedComputingNotes