BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Lisa Higham

Lisa Higham appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Distributed, Parallel, and Cluster Computing

Catalog footprint

What is connected

5works
1topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

5 published item(s)

preprint2016arXiv

Deterministic and Fast Randomized Test-and-Set in Optimal Space

The test-and-set object is a fundamental synchronization primitive for shared memory systems. A test-and-set object stores a bit, initialized to 0, and supports one operation, test&set(), which sets the bit's value to 1 and returns its previous value. This paper studies the number of atomic registers required to implement a test-and-set object in the standard asynchronous shared memory model with n processes. The best lower bound is log(n)-1 for obstruction-free (Giakkoupis and Woelfel, 2012) and deadlock-free (Styer and Peterson, 1989) implementations. Recently a deterministic obstruction-free implementation using O(sqrt(n)) registers was presented (Giakkoupis, Helmi, Higham, and Woelfel, 2013). This paper closes the gap between these known upper and lower bounds by presenting a deterministic obstruction-free implementation of a test-and-set object from Theta(log n) registers of size Theta(log n) bits. We also provide a technique to transform any deterministic obstruction-free algorithm, in which, from any configuration, any process can finish if it runs for b steps without interference, into a randomized wait-free algorithm for the oblivious adversary, in which the expected step complexity is polynomial in n and b. This transformation allows us to combine our obstruction-free algorithm with the randomized test-and-set algorithm by Giakkoupis and Woelfel (2012), to obtain a randomized wait-free test-and-set algorithm from Theta(log n) registers, with expected step-complexity Theta(log* n) against the oblivious adversary.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Space Bounds for Adaptive Renaming

We study the space complexity of implementing long-lived and one-shot adaptive renaming from multi-reader multi-writer registers, in an asynchronous distributed system with $n$ processes. As a result of an $f$-adaptive renaming algorithm each participating process gets a distinct name in the range $\{1,\dots,f(k)\}$ provided $k$ processes participate. Let $f: \{1,\dots,n\} \rightarrow \mathbb{N}$ be a non-decreasing function satisfying $f(1) \leq n-1$ and let $d = \max\{x ~|~ f(x) \leq n-1\}$. We show that any non-deterministic solo-terminating long-lived $f$-adaptive renaming object requires $d + 1$ registers. This implies a lower bound of $n-c$ registers for long-lived $(k+c)$-adaptive renaming, which we observe is tight. We also prove a lower bound of $\lfloor \frac{2(n - c)}{c+2} \rfloor$ registers for implementing any non-deterministic solo-terminating one-shot $(k+c)$-adaptive renaming. We provide two one-shot renaming algorithms: a wait-free algorithm and an obstruction-free algorithm. Each algorithm employs a parameter to depict the tradeoff between space and adaptivity. When these parameters are chosen appropriately, this results in a wait-free one-shot $(\frac{3k^2}{2})$-adaptive renaming algorithm from $\lceil \sqrt{n} \rceil + 1$ registers, and an obstruction-free one-shot $f$-adaptive renaming algorithm from only $\min\{n, x ~|~ f(x) \geq 2n\} + 1$ registers.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Partition Consistency: A Case Study in Modeling Systems with Weak Memory Consistency and Proving Correctness of their Implementations

Multiprocess systems, including grid systems, multiprocessors and multicore computers, incorporate a variety of specialized hardware and software mechanisms, which speed computation, but result in complex memory behavior. As a consequence, the possible outcomes of a concurrent program can be unexpected. A memory consistency model is a description of the behaviour of such a system. Abstract memory consistency models aim to capture the concrete implementations and architectures. Therefore, formal specification of the implementation or architecture is necessary, and proofs of correspondence between the abstract and the concrete models are required. This paper provides a case study of this process. We specify a new model, partition consistency, that generalizes many existing consistency models. A concrete message-passing network model is also specified. Implementations of partition consistency on this network model are then presented and proved correct. A middle level of abstraction is utilized to facilitate the proofs. All three levels of abstraction are specified using the same framework. The paper aims to illustrate a general methodology and techniques for specifying memory consistency models and proving the correctness of their implementations.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Linearizable Implementations Do Not Suffice for Randomized Distributed Computation

Linearizability is the gold standard among algorithm designers for deducing the correctness of a distributed algorithm using implemented shared objects from the correctness of the corresponding algorithm using atomic versions of the same objects. We show that linearizability does not suffice for this purpose when processes can exploit randomization, and we discuss the existence of alternative correctness conditions.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Space Complexity of Long-lived and One-Shot Timestamp Implementations

This paper is concerned with the problem of implementing an unbounded timestamp object from multi-writer atomic registers, in an asynchronous distributed system of n processors with distinct identifiers where timestamps are taken from an arbitrary universe. Ellen, Fatourou and Ruppert (2008) showed that sqrt{n}/2-O(1) registers are required for any obstruction-free implementation of long-lived timestamp systems from atomic registers (meaning processors can repeatedly get timestamps). We improve this existing lower bound in two ways. First we establish a lower bound of n/6 - O(1) registers for the obstruction-free long-lived timestamp problem. Previous such linear lower bounds were only known for constrained versions of the timestamp problem. This bound is asymptotically tight; Ellen, Fatourou and Ruppert (2008) constructed a wait-free algorithm that uses n-1 registers. Second we show that sqrt{n} - O(1) registers are required for any obstruction-free implementation of one-shot timestamp systems(meaning each processor can get a timestamp at most once). We show that this bound is also asymptotically tight by providing a wait-free one-shot timestamp system that uses fewer than 2 sqrt{n} registers, thus establishing a space complexity gap between one-shot and long-lived timestamp systems.

0 citations0 reviewsNo code linkedOpen access