In the prioritized algorithm of Naimi-Trehel [1], the global queue is ordered using a distributed sort. This requires a lot of additional messages among requesting sites within the distributed queue. We transform this distributed sort into a local one and propose a new algorithm based on request priorities and on a unique token, moving throughout a dynamic tree. Each request is forwarded towards the root of a request routing rooted tree. The tree root is the token holder site. Requests are recorded in a global mobile waiting queue localized at the token holder. The request routing rooted tree is modified when the token moves (the request routing tree is dynamic) rather than the requests are routed (the request routing tree being still static).
展开▼
