The F-Snapshot Problem

DOI10.1007/978-3-319-48314-6_11MaRDI QIDQ2835024zbMATH OpenOpenAlexFDO

Authors Gal Amram

Publication date 1 December 2016

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.02211

Mathematics Subject Classification ID

Distributed systems (68M14) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Abstract: 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(nlogn)$, which is also the time complexity of the fastest snapshot algorithm that uses only single-writer registers.

Recommendations

• On the time complexity of minimum and maximum global snapshot problems
• Towards a practical snapshot algorithm
• scientific article; zbMATH DE number 3940872
• scientific article; zbMATH DE number 1036790
• Revisiting Fryszkowski's problem
• scientific article; zbMATH DE number 3910473
• Generalizations of Fagnano's problem
• On Fryszkowski's problem
• The Instancy of Snapshots and Commuting Objects
• ABOUT THE CONP-COMPLETE “INJECTIVE KNAPSACK” PROBLEM

Cites work

• Atomic Snapshots in O (n log n) Operations
• Atomic snapshots of shared memory
• Bounded Concurrent Time-Stamping
• Bounded time-stamps
• Composite registers
• F-arrays, implementation and applications
• Linear-time snapshot implementations in unbalanced systems
• Model-checking of correctness conditions for concurrent objects
• On the signaling problem
• Proving the Correctness of Multiprocess Programs
• Simple and efficient bounded concurrent timestamping and the traceable use abstraction
• The mailbox problem
• The Mailbox Problem
• The time complexity of updating snapshot memories
• Time and Space Lower Bounds for Nonblocking Implementations

Cited in

(3)

• Space lower bounds for the signal detection problem
• Two-process synchronization
• On the signaling problem

This page was built for publication: The F-Snapshot Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835024)