Global predicate detection, which is an important problem in testing and debugging distributed programs, is very hard due to the combinatorial explosion of the global state space. The paper presents several techniques to tackle the state explosion problem in detecting whether an arbitrary predicate /spl Phi/ is true at some consistent global state of a distributed system. We present space efficient online algorithms for detecting /spl Phi/. We then improve the performance of our algorithms, both in space and time, by increasing the granularity of the execution step from an event to a sequence of events in each process.

The design of survivable all-optical networks based on self-healing WDM rings (SHR/WDM) to provide 100% protection from any single link failure requires the joint solution of three sub-problems. These are the ring cover of the mesh topology (the RC sub-problem), the routing of working lightpaths between node pairs to support traffic demands (the WL sub-problem) and the selection of the SHR/WDM spare wavelengths for the protection of every link traffic (the SW subproblem). This paper presents an integer linear programming (ILP) formulation of the problem of minimizing the total wavelength mileage (/spl lambda/-miles) required to support a set of given traffic demands in a given network topology using SHR/WDM employing 1:N line protection mechanism (the WRL problem). This formulation allows to jointly and optimally solve the three subproblems, and yields up to 15% reduction of the total /spl lambda/-miles required by existing solutions that separately resolve the sub-problems. A simplified sub-optimal solution of the WRL problem is also provided, that yields results few percent worse than the optimal solution and that is tractable for networks whose size is on the order of the pan-European network, i.e., 19 nodes.

There is a growing trend towards using mobile computing environment for several applications, and it is important that the mobile systems are given adequate support both at the systems level and at the communication level. Causal ordering is a useful property, particularly in applications that involve human interactions. (Such applications are common in mobile computing environments.) In this paper, we present three algorithms for causal ordering in mobile systems. The first algorithm handles the resource constraints of the mobile hosts, but the system is not easily scalable with respect to the number of mobile hosts and is not graceful to host disconnections and connections. Our second algorithm eliminates the above disadvantages at the cost of inhibiting some messages. The third algorithm is a combination of the first two algorithms.

We present an optimistic crash recovery technique without any communication overhead during normal operations of the distributed system. Our technique does not append any information to the application messages, it does not suffer from the domino effect, and each processor rolls back at most once during recovery. We present three distributed rollback algorithms, their complexities, and correctness proofs. Their performances are measured through extensive simulations.

Detecting properties about a distributed program is an important problem in testing and debugging distributed programs. This problem is very hard due to the combinatorial explosion of the global state space. For a given execution, we consider the problem of detecting whether a predicate /spl Phi/ is true at some global state of the system. First, we present a space efficient algorithm for detecting /spl Phi/. Next, we present a parallel algorithm to reduce the time taken to detect /spl Phi/. We then improve the performance of our algorithms, both in space and time, by increasing the granularity of the execution step from an event to a sequence of events in a process.