BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Lisa Higham

Lisa Higham contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Distributed, Parallel, and Cluster Computing

Trust snapshot

Quick read

Trust 15 - UnverifiedVerification L1Unclaimed author
3works
0followers
1topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

3 published item(s)

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