Self-organized scheduling means that the desired distribution of processes on nodes solely emerges from the interactions between the nodes in a dynamic process. For this purpose we define a virtual quantity assigned to each node, called its disposition, which corresponds to its suitability for performing one of a set of communicating processes. Nodes interact by the exchange of their disposition values which is implemented by a lightweight User Datagram Protocol (UDP). The disposition function maps a value on each node which indicates its appropriateness for participating in the distributed execution of medium-grained parallel computation. Disposition values also take the performance of each node into account can also take into account. Positive disposition values characterize nodes with adequate performance and with high quality of their mutual connectivity, so that they can perform communication among each other with low latency. An optimal distribution of the disposition values is illustrated below, where nodes with a positive disposition value are indicated by a shaded background. The intensity of the shade corresponds to the magnitude of the disposition value.

The dynamic assignment of communicating processes among peers within a domain of positive disposition values by a scheduling mechanism allows the execution of medium-grained parallel computations. These are presently performed on computer clusters over the Internet. In the figure above these domains are appearing as islands. The set of nodes inside such a domain forms a cluster of well-connected nodes.

Every peer manages a hash map object availablePeers containing closely located peers according to the distance measure given by the latency. This hash map is frequently updated and its members are recruited from the underlying Peer-to-Peer (P2P) overlay network. P2P systems rely on the phenomenon of small-world networks and are implemented by so-called friends lists. These lists are realized by another HashMap object knownPeers. Due to the phenomenon of small-world networks, even though most peers are not known of one another, most peers can be reached from every other by a small number of friend connections provided by the friends lists. In this way an overlay network emerges that potentially comprises the entire Internet.

In each domain of positive disposition values a peer with the highest disposition exists. This peer is referred to as the Primary Scheduler of such a cluster of well-connected nodes with good performance. A job scheduling based on the underlying P2P system can be realized by sending requests to all Primary Schedulers, until one of these accepts the job, for there are enough idle peers with a positive disposition in its availablePeers hash map. This Primary Scheduler handles the process scheduling of that job by its own. With the provided disposition values, an ideal process scheduling represents the mapping of communicating processes to peers inside a connected domain with positive disposition values. This can be accomplished as the Primary Scheduler maps the communicating processes of a computational job to peers inside its availablePeers hash map according to their disposition values.

The measurement of latencies and the interactions between nodes are performed by a topological information service (TIS). Through the interchange of disposition values between each peer and all peers in its availablePeers hash map, the disposition values of all nodes are updated and successively converge to a stable distribution, as illustrated in this computer animation. The clustering of nodes according to the quality of their interconnectivity can be described as a dynamical system of disposition values. We have simulated the dynamics of disposition values for many different network topologies. Some results of these simulations are presented on this site.