Distributed mutual exclusion is a basic building block of distributed systems that coordinates the access to critical shared resources. This work introduces a novel permission-based k-mutual exclusion algorithm for distributed systems with crash faults. Processes monitor each other and organize themselves on an adaptive virtual topology that is based on the hypercube and presents several logarithmic properties. Mutual exclusion is deployed on top of this monitoring system. Processes communicate through spanning trees which are created with a fully distributed strategy that tolerates faults by using process state information provided by the underlying monitoring system. Both the mutual exclusion and the distributed spanning tree algorithm are formally specified. The strategy is proven to guarantee the safety and liveness of the concurrent access of n processes to k critical resources. Experimental results are presented, showing that the algorithm performs efficiently even when up to n-1 processes are faulty.

Cut trees are a compact representation of the edge-connectivity between every pair of vertices of an undirected graph, and have a large number of applications. In this work a parallel version of the well known Gomory-Hu cut tree algorithm is presented. The parallel strategy is based on the master/slave model. The strategy is optimistic in the sense that the master process manipulates the tree being constructed and the slaves solve minimum s-t-cuts independently. Another version is proposed that employs a heuristic that enumerates all (up to a limit) of the minimum s-t-cuts in order to choose the most balanced one. The algorithm was implemented and extensive experimental results are presented, including a comparison with Gusfieldâs cut tree algorithm. Parallel versions of these algorithms have achieved significant speedups on real and synthetic graphs. We discuss the trade-offs between the two alternatives, each of which presents better results given the characteristics of the input graph. In particular, the existence of balanced cuts clearly gives an advantage to Gomory-Huâsalgorithm.

Routing protocols present a convergence latency for all routers to update their tables after a fault occurs and the network topology changes. During this time interval, which in the Internet has been shown to be of up to minutes, packets may be lost before reaching their destinations. In order to allow nodes to continue communicating during the convergence latency interval, we propose the use of alternative routes called detours. In this work we introduce new criteria for selecting detours based on network connectivity. Detours are chosen without the knowledge of which node or link is faulty. Highly connected components present a larger number of distinct paths, thus increasing the probability that the detour will work correctly. Experimental results were obtained with simulation on random Internet-like graphs generated with the Waxman method. Results show that the fault coverage obtained through the usage of the best detour is up to 90%. When the three best detours are considered, the fault coverage is up to 98%.

No abstract available.