References

1

G. Alverson, W. Griswold, D. Notkin and L. Snyder. A flexible communication abstraction for nonshared memory parallel computing. Proceedings of Supercomputing '90, 1990.

2

F. Baiardi, N. De Fransesco and G. Vaglini. Development of a debugger for a concurrent language. In IEEE Transactions on Software Engineering, SE-12(4):547--553, Apr. 1986.

3

P. C. Bates. Debugging Programs in a Distributed System Environment. PhD thesis, University of Massachusetts, Amherst, MA 01003, 1986. Also COINS Technical Report 86--05.

4

A. Bowyer. Computing Dirichlet Tesselations. The Computer Journal, 24(2), pages 162--166, Feb. 1981.

5

B. Bruegge and P. Hibbard. Generalized path expressions: A high level debugging mechanism. In Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium in High-Level Debugging, pages 34-44, 1983.

6

R. Cooper and K. Marzullo. Consistent detection of global predicates. In Proceedings of the ACM/ONR Workshop on Parallel and Distributed Debugging, pages 167--174, 1991.

7

J. E. Cuny, A. Hough, and J. Kundu. Logical time in visualizations produced by parallel programs. Proceedings of Visualization '92, pages 186--193 (1992).

8

C. J. Fidge. Partial orders for parallel debugging. SIGPLAN Notices, 24(1), pages 183--194, 1989.

9

R. J. Fowler, T. J. Leblanc, and J. M. Mellor-Crummey. An integrated approach to parallel program debugging and performance analysis on large-scale multiprocessors. SIGPLAN Notices, 24(1), pages 163--173, 1989.

10

G. S. Goldszmidt, S. Katz, and S. Yemini. High level language for debugging concurrent programs. ACM Transactions on Computer Systems, 8(4), pages 311--336, Nov. 1990.

11

P. K. Harter, D. M. Heimbigner and R. King. IDD: an interactive distributed debugger. In Proceedings of the 5th International Conference on Distributed Computing Systems, pages 498--506, 1985.

12

M. Heath and J. Etheridge. Visualizing the performance of parallel programs. IEEE Software, 8(5):29--39, 1991.

13

D. Hembold and D. Luckham. Debugging Ada tasking programs. IEEE Software, 2(2), pages 47-57, Mar. 1985.

14

A. A. Hough. Debugging Parallel Programs Using Abstract Visualizations. PhD thesis, University of Massachusetts, Amherst, MA 01003, 1991. Also COINS Technical Report 91--53.

15

A. A. Hough and J. E. Cuny. Perspective views: A technique for enchancing visualizations of parallel programs. In 1990 International Conference on Parallel Processing, pages II 124--132, Aug. 1990.

16

W. Hseush and G. E. Kaiser. Modeling concurrency in parallel debugging. In Proceedings of the Second ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 11--20, March 1990.

17

L. Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558--565, 1978.

18

L. Lamport. The mutual exclusion problem: Part I-A theory of interprocess communication. Journal of the Association for Computing Machinery, 33(2):313-326, April 1986.

19

R. J. LeBlanc and A. D. Robbins. Event-driven monitoring of distributed programs. In Proceedings of the 5th International Conference on Distributed Computing Systems, pages 515--522, 1985.

20

T. J. LeBlanc and J. M. Mellor-Crummey. Debugging parallel programs with instant replay. IEEE Transactions on Computers, C-36(4):471--482, Apr. 1987.

21

T. J. LeBlanc, J. M. Mellor-Crummey, and R. J. Fowler. Analyzing parallel program executions using multiple views. Journal of Parallel and Distributed Computing, 9:203--217, 1990.

22

V. M. Lo, S. Rajopadhye, M. A. Mohamed, S. Gupta, B. Nitzberg, J. A. Telle, X. X. Zhong. LaRCS: A language for describing parallel computations for the purpose of mapping. Technical Report CIS-TR-90-16, University of Oregon Dept. of Computer Science, 1990.

23

B. Miller and J.-D. Choi. A mechanism for efficient debugging of parallel programs. SIGPLAN Notices, 24(1), pages 141--150, 1989.

24

L. Snyder. The XYZ abstraction levels of Poker-like languages. Languages and Compilers for Parallel Computing, David Gelernter and Alexandru Nicolau and David Padua(eds.), MIT Press, pages 470--489, 1990.

APPENDIX: Logical Relations and Pattern Matching

Pattern matching in Ariadne conceptually proceeds in two steps: first the specified events are found in the event trace and then the specified logical relations between those events are asserted. Thus, for example, to describe a pattern in which two p-chains a and b are logically parallel, we use [a b] which is matched as

find(a); find(b); assert(a || b)

During the matching process, events can be hierarchically grouped into abstract events as denoted by left and right brackets. Thus when

{ { ( {a b} c )*} d}

We use different forms of left and right brackets to specify the assertions of different logical relations. The set braces denote an abstract event without an asserted ordered (note: this does not mean unordered, it means ``don't care''); square brackets denote parallels and angular brackets denote precedes. Thus

< [a b] c >

find(a); find(b); find(c); assert(a || b, {a b} c)

**NOTE TO JAN** In the following definition, I'm trying to model a broadcast in which each process broadcasted-to either replies "ok" or "bad". I need to be able to talk about each broadcasted-to process individually, so I resurrected the old syntax in which each each from a broadcast is modeled individually, although I changed the model so that is follows message edges rather than "popping context". **END NOTE**

(that is, a triangulation in which no vertex from any triangle lies within the circumcircle of any other triangle)

. The triangles whose circumcircles are intersected by the new mesh point are flagged. The union of the flagged triangles forms a convex polygonal region. The mesh is modified by removing all of the edges in the interior of the polygon and adding edges from the new point to each of the vertices of the polygon. In the parallel version, each point is managed by its own process. When a new point is to be added a process is created for it. This process then sends messages to its surrounding processes, in a spreading activation pattern, looking for triangles that whose circumcircle contains the new point. These triangles are then ``locked" to prevent concurrent access by other insertion transactions. The polygonal region formed by the locked triangles is then modified as in Bowyer's sequential algorithm.

The points are ordered by the order in which they are removed from a shared queued for insertions. This number is used as an id for locking the triangles. An attempt to lock a triangle with a lower number aborts the current transaction. An attempt to lock a triangle with a higher humber aborts the transaction that locked the triangle.