A model that captures communication on asynchronous unidirectional rings is formalized. Our model incorporates both probabilistic and nondeterministic features and is strictly more powerful than a purely probabilistic model. Using this model, a collection of tools are developed that facilitate studying lower bounds on the expected communication complexity of Monte Carlo algorithms for language recognition problems on anonymous asynchronous unidirectional rings. The tools are used to establish tight lower bounds on the expected bit complexity of the Solitude Verification problem that asymptotically match upper bounds for this problem. The bounds demonstrate that, for this problem, the expected bit complexity depends subtly on the processors' knowledge of the size of the ring and on whether or not processor-detectable termination is required.

A time-space tradeoff is established in the branching program model for the problem of computing the product of two n*n matrices over a certain semiring. It is assumed that each element of each n*n input matrix is chosen independently to be 1 with probability n/sup -1/2/ and to be 0 with probability 1-n/sup -1/2/. Letting S and T denote expected space and time of a deterministic algorithm, the tradeoff is ST= Omega (n/sup 3.5/) for T0. The lower bounds are matched to within a logarithmic factor by upper bounds in the branching program model. Thus, the tradeoff possesses a sharp break at T= Theta (n/sup 2.5/). These expected case lower bounds are also the best known lower bounds for the worst case.>

The authors address the question of why some fixed-parameter problem families solvable in polynomial time seem to be harder than others with respect to fixed-parameter tractability: whether there is a constant alpha such that all problems in the family are solvable in time O(n/sup alpha /). The question is modeled by considering a class of polynomially indexed relations. The main results show that (1) this setting supports notions of completeness that can be used to explain the apparent hardness of certain problems with respect to fixed-parameter tractability, and (2) some natural problems are complete.>

The inherent bit complexity of leader election on asynchronous unidirectional rings of processors is examined under various assumptions about global knowledge of the ring. If processors have unique identities with a maximum of m bits, then the expected number of communication bits sufficient to elect a leader with probability 1, on a ring of (unknown) size n is $O(nm)$. If the ring size is known to within a multiple of 2, then the expected number of communication bits sufficient to elect a leader with probability 1 is $O(n\log n)$. These upper bounds are complemented by lower bounds on the communication complexity of a related problem called solitude verification that reduces to leader election in $O(n)$ bits. If processors have unique identities chosen from a sufficiently large universe of size s, then the average, overall choices of identities, of the communication complexity of verifying solitude is $\Omega (n\log s)$ bits. When the ring size is known only approximately, then $\Omega (n\log n)$ bits are required for solitude verification. The lower bounds address the complexity of certifying solitude. This is modelled by the best-case behaviour of nondeterministic solitude-verification algorithms.

Chor, Israeli and Li recently published three randomized algorithms for a version of the consensus problem for a shared memory model of distributed computing.Their model requires, as atomic instructions on the shared memory, reads and random writes (in which a random choice and a write are done together in a single atomic instruction).This paper develops randomized algorithms for a model in which the only atomic operations on the shared memory are reads and writes.

Given a pattern string of length n and an object string of length m, the string matching problem asks for the positions of all occurrences of the pattern in the object string. This paper investigates a generalization of string matching, in which the pattern is a sequence of pattern elements, each compatible with a set of symbols. The alphabet of symbols is infinite, with its members encoded in a finite alphabet. In contrast to standard string matching, which can be solved in simultaneous linear time and constant space, it is shown that generalized string matching requires a time-space product of $\Omega ({{n^2 } / {\log n}})$ on a powerful model of computation, when the alphabet is restricted to n symbols. Our proof uses a method of Borodin. The obvious algorithm for generalized string matching requires time $O(NM)$, where N is the length of the encoding of the pattern, and M is that of the object string. We describe an algorithm which solves generalized string matching in time $O(N + M + mN^{{1 / 2}} {\operatorname{polylog}} (n))$.

This paper establishes time-space tradeoffs for some algebraic problems in the branching program model. For a finite field F, convolution of n-vectors over F requires ST = Θ(n2 log |F|), where S is space and T is time, in good agreement with corresponding results for straightline programs. Our result for n × n matrix multiplication over F, ST2 = Θ(n6 log |F|), is stronger than the previously known bound ST = Ω(n3) for straight-line and branching programs. The problem of computing PAQ, where P and Q are n × n permutation matrices and A is a particular matrix, requires Ω(n3) ≤ ST ≤ O(n3logn) for branching programs, in contrast to ST = Ω(n4) for straight-line programs.

Article Probabilistic solitude verification on a ring Share on Authors: Karl Abrahamson Department of Computer Science, University of British Columbia, Vancouver, British Columbia Department of Computer Science, University of British Columbia, Vancouver, British ColumbiaView Profile , Andrew Adler Department of Mathematics, University of British Columbia, Vancouver, British Columbia Department of Mathematics, University of British Columbia, Vancouver, British ColumbiaView Profile , Lisa Higham View Profile , David Kirkpatrick View Profile Authors Info & Claims PODC '86: Proceedings of the fifth annual ACM symposium on Principles of distributed computingNovember 1986 Pages 161–173https://doi.org/10.1145/10590.10604Online:01 November 1986Publication History 17citation164DownloadsMetricsTotal Citations17Total Downloads164Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access