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

Sam Toueg

Sam Toueg contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Distributed, Parallel, and Cluster ComputingData Structures and Algorithms

Trust snapshot

Quick read

Trust 15 - UnverifiedVerification L1Unclaimed author
3works
0followers
2topics
3close 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)

preprint2022arXiv

Parameterized algorithm for replicated objects with local reads

We consider the problem of implementing linearizable objects that support both read and read-modify-write (RMW) operations in message-passing systems with process crashes. Since in many systems read operations vastly outnumber RMW operations, we are interested in implementations that emphasize the efficiency of read operations. We present a parametrized algorithm for partially synchronous systems where processes have access to external clocks that are synchronized within $ε$. With this algorithm, every read operation is local (intuitively, it does not trigger messages). If a read is not concurrent with a conflicting RMW, it is performed immediately with no waiting; furthermore, even with a concurrent conflicting RMW, a read experiences very little delay in the worst-case. For example, the algorithm's parameters can be set to ensure that every read takes $ε$ time in the worst-case. To the best of our knowledge this is the first algorithm to achieve this bound in the partially synchronous systems that we assume here. Our parametrized algorithm generalizes the (non-parameterized) lease-based algorithm of Chandra et al. [6] where the worst-case time for reads is $3δ$, where $δ$ is the maximum message delay. The algorithm's parameters can be used to trade-off the worst-case times for read and RMW operations. They can also be used to take advantage of the fact that in many message-passing systems the delay of most messages is order of magnitudes smaller than the maximum message delay~$δ$: for example, the parameters can be set so that, in "nice" periods where message delays are $δ^* \ll δ$, reads take at most $ε$ time while RMWs take at most $3 δ^*$ time.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

On Register Linearizability and Termination

In a seminal work, Golab et al. showed that a randomized algorithm that works with atomic objects may lose some of its properties if we replace the atomic objects that it uses with linearizable objects. It was not known whether the properties that can be lost include the important property of termination (with probability 1). In this paper, we first show that, for randomized algorithms, termination can indeed be lost. Golab et al. also introduced strong linearizability, and proved that strongly linearizable objects can be used as if they were atomic objects, even for randomized algorithms: they preserve the algorithm's correctness properties, including termination. Unfortunately, there are important cases where strong linearizability is impossible to achieve. In particular, Helmi et al. MWMR registers do not have strongly linearizable implementations from SWMR registers. So we propose a new type of register linearizability, called write strong-linearizability, that is strictly stronger than linearizability but strictly weaker than strong linearizability. We prove that some randomized algorithms that fail to terminate with linearizable registers, work with write strongly-linearizable ones. In other words, there are cases where linearizability is not sufficient but write strong-linearizability is. In contrast to the impossibility result mentioned above, we prove that write strongly-linearizable MWMR registers are implementable from SWMR registers. Achieving write strong-linearizability, however, is harder than achieving just linearizability: we give a simple implementation of MWMR registers from SWMR registers and we prove that this implementation is linearizable but not write strongly-linearizable. Finally, we prove that any linearizable implementation of SWMR registers is necessarily write strongly-linearizable; this holds for shared-memory, message-passing, and hybrid systems.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Randomized Consensus with Regular Registers

The well-known randomized consensus algorithm by Aspnes and Herlihy for asynchronous shared-memory systems was proved to work, even against a strong adversary, under the assumption that the registers that it uses are atomic registers. With atomic registers, every read or write operation is instantaneous (and thus indivisible). As pointed out by Golab et al. (2011), however, a randomized algorithm that works with atomic registers does not necessarily work if we replace the atomic registers that it uses with linearizable implementations of registers. This raises the following question: does the randomized consensus algorithm by Aspnes and Herlihy still work against a strong adversary if we replace its atomic registers with linearizable registers? We show that the answer is affirmative, in fact, we show that even linearizable registers are not necessary. More precisely, we prove that the algorithm by Aspnes and Herlihy works against a strong adversary even if the algorithm uses only regular registers.

0 citations0 reviewsNo code linkedOpen access