Browsing by Author "Warpechowska-Gruca, Jolanta"
Now showing 1 - 3 of 3
Results Per Page
Sort Options
- ItemOpen AccessMEETING TIMES OF RANDOM WALKS ON GRAPHS(1994-02-01) Warpechowska-Gruca, JolantaWe derive techniques for proving exact values or bounds on the meeting time. These techniques are used to prove two upper bounds on the meeting time of an arbitrary number of random walks in any connected undirected graph. Both bounds express the meeting time of several random walks in terms of the meeting times of fewer random walks. One of the bounds is tight on rings, the other is a generalization of a bound suggested by Tetali and Winkler. The techniques yield exact expressions for the meeting times on rings and for two or three random walks in hitting-time-symmetric graphs. Additional results include case study of various meeting time games on rings, several counterexamples to "natural" conjectures concerning meeting times, and partial characterization of hitting-time-symmetric graphs.
- ItemOpen AccessMeeting times of random walks on graphs(1993) Warpechowska-Gruca, Jolanta; Higham, Lisa
- ItemOpen AccessNOTES ON ATOMIC BROADCAST(1995-04-01) Higham, Lisa; Warpechowska-Gruca, JolantaAtomic broadcast [1] is a powerful communication primitive, which is applied in a natural way in sequentially consistent implementations of various data structures (see [1]). Unfortunately the atomic broadcast algorithm as given in [1] is incorrect. Here some ways of correcting it are analyzed under assumptions of blocking versus nonblocking communication. Two atomic broadcast algorithms are proposed: one correct if it is used in a blocking manner, the other correct unconditionally. The latter algorithm, when used in the sequentially consistent implementations of data structures proposed in [1], has the same time complexity and a reduced message complexity compared to that claimed in the original application.