The "wandering token" home page

This is the reference page of my "wandering token" project. The purpose of the project is to study, both theoretically and practically, the potential of the basic token idea, whose introduction dates back to the 70's, when applied in a large network with a full mesh connectivity. The transport level of the Internet is one instance of such environment, but the idea can be applied also to other networks [4].

The token idea addresses the solution of resource sharing problems: this is not restricted to the mutual exclusion problem, but extends to the management of elastic resources. For instance, the resource may consist of a network backbone, shared by many users that download chunks of a media stream [1].

The idea of the token "wandering" in the network insists on the stochastic nature of the technique: it is not based on overlay networks designed with some optimality criteria. The routing strategy is random: at any move the token may be received by any node in the network. This apparently "zero knowledge" assumptions hides a membership maintenance problem: the token holder should know all members of the network in order to select one at random.

The problem cannot be bypassed assuming a centralized "master" with a global view of the network: one purpose of the distributed protocol is avoiding the presence of a single point of failure. Therefore we must assume that the knowledge of the membership is somewhat distributed among the nodes of the system.

One side effect of the stochastic nature of the "wandering token" technique is that its performance cannot be assessed deterministically. Here we start from the philosophy that, in practice, nothing can be proved "deterministically": most of the assumptions at the basis of proofs of deterministic properties are in fact valid with some probability.

So I decide to accept the challenge of modeling an environment ruled by probabilities, and to obtain a probability density as a performance figure. The theoretical approach may become at some point awkward, and simulation helps where analysis cannot go. Real scale setups for experiments are difficult to implement, since the approach works better with large numbers and a small scale experiment has limited significance.

From this point of view I enjoyed the help of Ali Asim, at the time with the University of Paris, which helped me to carry out tests of a specific implementation in the Grid5000 network, in the framework of the CoreGRID project [3]. A small scale experiment to assess the resilience of a token passing protocol was conducted in collaboration with the FORTH Institute in Crete (Greece) and with the INFN/CNAF Institute in Italy [2].

The software used for this last experiment can be easely installed for demonstration or evaluation purposes: the instructions for installation are found following the link below.

Resources

[1] Ciuffoletti, A. "The Wandering Token: Congestion Avoidance of a Shared Resource", Future Generation Computing Systems, Springer, 2010, 26, 473-478.

[2] Ciuffoletti, A. "Secure token passing at application level", Future Generation Computer Systems, to appear in 2010.

[3] Ciuffoletti, A., Asim, A. "Scalable concurrency control in a dynamic membership -- Experimental results", in Grid and Services Evolution, N. Meyer, D. Talia, R. Y. Yahyapour (eds.), Springer, 2008, 205-214.

[4] Ciuffoletti, A. "Collision avoidance for Delay_Req messages in broadcast media", International IEEE Symposium on Precision Clock Synchronization for Measurement, Control and Communication, Brescia, 2009.

[5] "How to install a wandering token agent", the installation manual.

The wandering token
View more documents from Augusto Ciuffoletti.
Design of a secure "Token Passing" protocol
View more presentations from Augusto Ciuffoletti.