Source author record

Gal Amram

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

3works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Simple Executions of Snapshot Implementations

The well known snapshot primitive in concurrent programming allows for n-asynchronous processes to write values to an array of single-writer registers and, for each process, to take a snapshot of these registers. In this paper we provide a formulation of the well known linearizability condition for snapshot algorithms in terms of the existence of certain mathematical functions. In addition, we identify a simplifying property of snapshot implementations we call "schedule-based algorithms". This property is natural to assume in the sense that as far as we know, every published snapshot algorithm is schedule-based. Based on this, we prove that when dealing with schedule-based algorithms, it suffices to consider only a small class of very simple executions to prove or disprove correctness in terms of linearizability. We believe that the ideas developed in this paper may help to design automatic verification of snapshot algorithms. Since verifying linearizability was recently proved to be EXPSPACE-complete, focusing on unique objects (snapshot in our case) can potentially lead to designing restricted, but feasible verification methods.

preprint2015arXiv

The F-snapshot Problem

Aguilera, Gafni and Lamport introduced the signaling problem in [5]. In this problem, two processes numbered 0 and 1 can call two procedures: update and Fscan. A parameter of the problem is a two- variable function $F(x_0,x_1)$ . Each process $p_i$ can assign values to variable $x_i$ by calling update(v) with some data value v, and compute the value: $F(x_0,x_1)$ by executing an Fscan procedure. The problem is interesting when the domain of $F$ is infinite and the range of $F$ is finite. In this case, some "access restrictions" are imposed that limit the size of the registers that the Fscan procedure can access. Aguilera et al. provided a non-blocking solution and asked whether a wait-free solution exists. A positive answer can be found in [7]. The natural generalization of the two-process signaling problem to an arbitrary number of processes turns out to yield an interesting generalization of the fundamental snapshot problem, which we call the F-snapshot problem. In this problem $n$ processes can write values to an $n$ -segment array (each process to its own segment), and can read and obtain the value of an n-variable function $F$ on the array of segments. In case that the range of $F$ is finite, it is required that only bounded registers are accessed when the processes apply the function $F$ to the array, although the data values written to the segments may be taken from an infinite set. We provide here an affirmative answer to the question of Aguilera et al. for an arbitrary number of processes. Our solution employs only single-writer atomic registers, and its time complexity is $O(n \log n)$ , which is also the time complexity of the fastest snapshot algorithm that uses only single-writer registers.

preprint2013arXiv

On the Mailbox Problem

The Mailbox Problem was described and solved by Aguilera, Gafni, and Lamport in their 2010 DC paper with an algorithm that uses two flag registers that carry 14 values each. An interesting problem that they ask is whether there is a mailbox algorithm with smaller flag values. We give a positive answer by describing a mailbox algorithm with 6 and 4 values in the two flag registers.

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.