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

Ali Sezgin

Ali Sezgin contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsDistributed, Parallel, and Cluster ComputingProgramming LanguagesLogic in Computer Science

Trust snapshot

Quick read

Trust 15 - Baseline
3works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

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)

preprint2016arXiv

Local Linearizability

The semantics of concurrent data structures is usually given by a sequential specification and a consistency condition. Linearizability is the most popular consistency condition due to its simplicity and general applicability. Nevertheless, for applications that do not require all guarantees offered by linearizability, recent research has focused on improving performance and scalability of concurrent data structures by relaxing their semantics. In this paper, we present local linearizability, a relaxed consistency condition that is applicable to container-type concurrent data structures like pools, queues, and stacks. While linearizability requires that the effect of each operation is observed by all threads at the same time, local linearizability only requires that for each thread T, the effects of its local insertion operations and the effects of those removal operations that remove values inserted by T are observed by all threads at the same time. We investigate theoretical and practical properties of local linearizability and its relationship to many existing consistency conditions. We present a generic implementation method for locally linearizable data structures that uses existing linearizable data structures as building blocks. Our implementations show performance and scalability improvements over the original building blocks and outperform the fastest existing container-type implementations.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Aspect-oriented linearizability proofs

Linearizability of concurrent data structures is usually proved by monolithic simulation arguments relying on the identification of the so-called linearization points. Regrettably, such proofs, whether manual or automatic, are often complicated and scale poorly to advanced non-blocking concurrency patterns, such as helping and optimistic updates. In response, we propose a more modular way of checking linearizability of concurrent queue algorithms that does not involve identifying linearization points. We reduce the task of proving linearizability with respect to the queue specification to establishing four basic properties, each of which can be proved independently by simpler arguments. As a demonstration of our approach, we verify the Herlihy and Wing queue, an algorithm that is challenging to verify by a simulation proof.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Sequential Consistency and Concurrent Data Structures

Linearizability, the de facto correctness condition for concurrent data structure implementations, despite its intuitive appeal is known to lead to poor scalability. This disadvantage has led researchers to design scalable data structures satisfying consistency conditions weaker than linearizability. Despite this recent trend, sequential consistency as a strictly weaker consistency condition than linearizability has received no interest. In this paper, we investigate the applicability of sequential consistency as an alternative correctness criterion for concurrent data structure implementations. Our first finding formally justifies the reluctance in moving towards sequentially consistent data structures: Implementations in which each thread modifies only its thread-local variables are sequentially consistent for various standard data structures such as pools, queues and stacks. We also show that for almost all data structures, and the data structures we consider in this paper, it is possible to have sequentially consistent behaviors in which a designated thread does not synchronize at all. As a potential remedy, we define a hierarchy of quantitatively strengthened variants of sequential consistency such that the stronger the variant the more synchronization it enforces which at the limit is equal to that enforced by linearizability.

0 citations0 reviewsNo code linkedOpen access