We describe two problems and their optimal solutions for partially ordered sets. We first describe an optimal algorithm for computing the largest anti-chain of a partially ordered set given its decomposition into its ...
详细信息
We describe two problems and their optimal solutions for partially ordered sets. We first describe an optimal algorithm for computing the largest anti-chain of a partially ordered set given its decomposition into its chains. Our algorithm requires O(n2m) comparisons where n is the number of chains and m is the maximum number of elements in any chain. We also give an adversary argument to prove that this is a lower bound. Our second problem requires us to find if the given poset is a total order. Our optimal algorithm requires 0(mn log n) comparisons. These algorithms have applications in distributed debugging and recovery in distributed systems.
This paper reports an investigation to build a tool for the debugging and monitoring of highly parallel systems. The investigation is based on the principle of folding/unfolding graphical user interface and materialis...
详细信息
This paper reports an investigation to build a tool for the debugging and monitoring of highly parallel systems. The investigation is based on the principle of folding/unfolding graphical user interface and materialised in the design of GRIP . Initially we based our investigation on transputer-based systems but will be extended in a later stage to incorporate other non-transputer-based parallel systems.
An integrated system design for debuggingdistributed programs written in concurrent high-level languages is described. A variety of user-interface, monitoring, and analysis tools integrated around a uniform process m...
详细信息
An integrated system design for debuggingdistributed programs written in concurrent high-level languages is described. A variety of user-interface, monitoring, and analysis tools integrated around a uniform process model are provided. Because the tools are language-based, the user does not have to deal with low-level implementation details of distribution and concurrency, and instead can focus on the logic of the program in terms of language-level objects and constructs. The tools provide facilities for experimentation with process scheduling, environment simulation, and nondeterministic selections. Presentation and analysis of the program's behavior are supported by history replay, state queries, and assertion checking. Assertions are formulated in linear time temporal logic, which is a logic particularly well suited to specify the behavior of distributed programs. The tools are separated into two sets. The language-specific tools are those that directly interact with programs for monitoring of and on-line experimenting with distributed programs. The language-independent tools are those that support off-line presentation and analysis of the monitored information. This separation makes the system applicable to a wide range of programming languages. In addition, the separation of interactive experimentation from off-line analysis provides for efficient exploitation of both user time and machine resources. The implementation of a debugging facility for OCCAM is described.
The debugging cycle is the most common methodology for finding and correcting errors in sequential programs. Cyclic debugging is effective because sequential programs are usually deterministic. debugging parallel prog...
详细信息
The debugging cycle is the most common methodology for finding and correcting errors in sequential programs. Cyclic debugging is effective because sequential programs are usually deterministic. debugging parallel programs is considerably more difficult because successive executions of the same program often do not produce the same results. In this paper we present a general solution for reproducing the execution behavior of parallel programs, termed Instant Replay. During program execution we save the relative order of significant events as they occur, not the data associated with such events. As a result, our approach requires less time and space to save the information needed for program replay than other methods. Our technique is not dependent on any particular form of interprocess communication. It provides for replay of an entire program, rather than individual processes in isolation. No centralized bottlenecks are introduced and there is no need for synchronized clocks or a globally consistent logical time. We describe a prototype implementation of Instant Replay on the BBN Butterfly? Parallel Processor, and discuss how it can be incorporated into the debugging cycle for parallel programs.
暂无评论