Danny Hendler
email: hendlerd@bgu.ac.il

Adnane Khattabi
email: adnane.khattabi-riffi@u-bordeaux.fr

Alessia Milani
email: milani@labri.fr

Corentin Travers
email: travers@labri.fr

Upper and Lower Bounds for Deterministic Approximate Objects

Keywords: Distributed computing, distributed algorithms, shared memory, fault tolerance, concurrent data structures, relaxed specifications

Relaxing the sequential specification of shared objects has been proposed as a promising approach to obtain implementations with better complexity. In this paper, we study the step complexity of relaxed variants of two common shared objects: max registers and counters. In particular, we consider the k-multiplicative-accurate max register and the k-multiplicative-accurate counter, where read operations are allowed to err by a multiplicative factor of k (for some k ∈ N). More accurately, reads are allowed to return an approximate value x of the maximum value v previously written to the max register, or of the number v of increments previously applied to the counter, respectively, such that v/k ≤ x ≤ v • k. We provide upper and lower bounds on the complexity of implementing these objects in a wait-free manner in the shared memory model.

I. INTRODUCTION

With the ubiquitousness of multi-core and multi-processor systems, there is a growing need to gain better understanding of how to implement concurrent objects with improved complexity, while maintaining the natural correctness guarantee provided to programmers by linearizability. Relaxing the sequential specification of linearizable concurrent objects is one promising approach of achieving this [START_REF] Afek | Quasi-linearizability: Relaxed consistency for improved concurrency[END_REF], [START_REF] Henzinger | Quantitative relaxation of concurrent data structures[END_REF]. An object's sequential specification defines its correct behavior in sequential executions. Roughly speaking, linearizability [START_REF] Herlihy | Linearizability: A correctness condition for concurrent objects[END_REF] guarantees that any concurrent execution is equivalent to a sequential one.

There is empirical evidence that relaxing the sequential specification of some common objects, e.g. queues and counters, yields improved performance of linearizable implementations, e.g [START_REF] Henzinger | Quantitative relaxation of concurrent data structures[END_REF], [START_REF] Rukundo | Monotonically relaxing concurrent data-structure semantics for increasing performance: An efficient 2d design framework[END_REF]. However, the theoretical principles to implement concurrent objects more efficiently by relaxing their sequential specification are not yet clear.

In this paper, we study relaxed-semantics variants of two well-known concurrent objects -counters and max registers, in the classical shared memory model. In particular, we investigate the extent to which allowing wait-free linearizable implementations of these objects to return approximate values, rather than accurate ones, may improve their step complexity.

A counter is a linearizable object that supports a CounterIncrement operation and a CounterRead operation. The sequential specification of a counter requires that a CounterRead operation returns the number of CounterIncrement operations that precede it. A relaxed variant of the counter is the k-multiplicative-accurate counter, defined in [START_REF] Aspnes | Lower bounds for restricted-use objects[END_REF], where a CounterRead operation returns an approximate value x of the number v of CounterIncrement operations that precede it, such that v/k ≤ x ≤ v • k for some parameter k > 0.

A max register r supports a W rite(v) operation that writes a non-negative integer v to r and a Read operation that returns the maximum value previously written to r, [START_REF] Aspnes | Lower bounds for restricted-use objects[END_REF]. We define the k-multiplicative-accurate max register by allowing a Read operation to return an approximate value x of the largest value v written before it, such that v/k ≤ x ≤ v • k for some parameter k > 0.

A. Related Work

A well-known result by Jayanti, Tan and Toueg [START_REF] Jayanti | Time and space lower bounds for nonblocking implementations[END_REF] proved a linear lower bound in the number of processes n on the worst-case step complexity of obstruction-free implementations from historyless primitives (e.g. read,write, test&set) of a large class of shared objects that includes exact counters. A wait-free exact counter with optimal worst case step complexity can be constructed easily by using a waitfree atomic snapshot : to increment the counter, a process simply increments its component of the snapshot, and to read the counter's value, it invokes Scan and returns the sum of all components in the view it obtains. Since wait-free atomic snapshot can be implemented, using reads and writes only, with worst-case step complexity linear in n, e.g. [START_REF] Attiya | Adaptive and efficient algorithms for lattice agreement and renaming[END_REF], so can counters.

Aspnes, Attiya and Censor-Hillel [START_REF] Aspnes | Polylogarithmic concurrent data structures from monotone circuits[END_REF] show the possibility of implementing exact counting algorithms whose step complexity is sub-linear when the number of operations is bounded. In particular, they presented a wait-free exact counter for which the step complexities of CounterIncrement and CounterRead operations are O min(log n log v, n) and O min(log v, n) , respectively, where v is the object's current value. However, for executions in which the number of CounterIncrement operations is exponential in n, both the worst-case and the amortized step complexities of their constuction become linear in n.

In [START_REF] Baig | Longlived counters with polylogarithmic amortized step complexity[END_REF] Baig et al. present the first wait-free read/write exact counter whose amortized step complexity is polylogarithmic in n, O(log 2 n), in executions of arbitrary length and prove that their algorithm is optimal in terms of amortized step complexity up to a logarithmic factor.

Approximate counting has many applications (e.g.; [START_REF] Dice | Scalable statistics counters[END_REF], [START_REF] Afek | Cbtree: A practical concurrent self-adjusting search tree[END_REF]) and there is a large literature in approximate probabilistic counting, both in the sequential (e.g. [START_REF] Sr | Counting large numbers of events in small registers[END_REF], [START_REF] Flajolet | Approximate counting: A detailed analysis[END_REF]) and concurrent setting (e.g. [START_REF] Aspnes | Approximate shared-memory counting despite a strong adversary[END_REF], [START_REF] Bender | Mutual exclusion with o(logˆ2 log n) amortized work[END_REF]). In [START_REF] Aspnes | Approximate shared-memory counting despite a strong adversary[END_REF], Aspnes and Censor present a randomized algorithm to implement an approximate counter that requires sublinear step complexity, and where any CounterRead operation has a high probability of returning a value which is at most a fraction of δ less than the number of increments that have finished before the read started, and at most a fraction of δ more than the number of increments that have started before the read finished. Similarly to their counter, the k-multiplicative accurate counter we study in this paper, allows a multiplicative error of the exact value. However, we study approximate deterministic counting, where the value returned by CounterRead operations is always ensured to be within the given approximation range.

Aspnes et al. also study k-additive counters that allow some additive error for the value returned by CounterRead operations, [START_REF] Aspnes | Polylogarithmic concurrent data structures from monotone circuits[END_REF]. In particular they prove a lower bound of Ω(min(n -1, log m -log k)) on the worst-case step complexity of any deterministic asynchronous linearizable implementation of a k-additive counter, where m is the number of states of the counter and n is the number of processes. No matching upper bound is given.

The exact max register object has been proposed in [START_REF] Aspnes | Polylogarithmic concurrent data structures from monotone circuits[END_REF] where Aspnes et al. present a bounded variant of this object to beat the linear lower bound on the worst case step complexity by Jayanti et al. In particular, their algorithm has O(log m) worst case step complexity for both Read () and Write(v ) operations provided that the value written in the max register does not exceed the value m. Their algorithm is optimal [START_REF] Aspnes | Lower bounds for restricted-use objects[END_REF]. Baig et al. [START_REF] Baig | Longlived counters with polylogarithmic amortized step complexity[END_REF] presented an unbounded deterministic max register implementation with polylogarithmic amortized step complexity in executions of arbitrary length.

B. Our Contribution k-multiplicative-accurate counter:

To the best of our knowledge we present the first deterministic approximate counter with constant amortized complexity. More precisely, we present a wait-free linearizable k-multiplicative-accurate counter for k ≥ √ n where n is the number of processes, with constant amortized step complexity for executions of arbitrary length. Then, by extension of the lower bound of Attiya and Hendler, [START_REF] Attiya | Time and space lower bounds for implementations using k-cas[END_REF], we prove that any n-process soloterminating implementation of a k-multiplicative-accurate counter from read/write and conditional primitive operations (including k-word compare-and-swap) has amortized step complexity of Ω(log(n/k 2 )), for k ≤ √ n/2. Our results together with the upper and lower bound on exact counting proved in [START_REF] Baig | Longlived counters with polylogarithmic amortized step complexity[END_REF] show that when the approximation parameter k does not depend on n, relaxing the counter semantics by allowing a multiplicative error cannot asymptotically reduce the amortized step complexity by more than a logarithmic factor.

We also prove that the worst-case step complexity of obstruction-free implementations of m-bounded kmultiplicative-accurate counters from historyless primitives is Ω(min(n, log 2 log k m)), where n is the number of processes and m is a bound on the number of CounterIncrement operation instances that can be performed on the counter. This implies that for unbounded kmultiplicative-accurate counters, the worst case step complexity is in Ω(n), and we fall back to the linear lower bound by Jayanti, Tan and Toueg [START_REF] Jayanti | Time and space lower bounds for nonblocking implementations[END_REF].

k-multiplicative-accurate max register: We prove that relaxing the semantics of the bounded max register by allowing inaccuracy of even a constant multiplicative factor yields an exponential improvement in the worst-case step complexity. In particular, we prove that the worst-case step complexity of obstruction-free read/write implementations of m-bounded k-multiplicative-accurate max registers is Ω(min(n, log 2 log k m)), where n is the number of processes. A max register is m-bounded, if it can only represent values in {0, . . . , m -1}. Then, we present a novel mbounded k-multiplicative-accurate max register algorithm whose worst-case step complexity matches this lower bound. We can easily "plug-in" our bounded k-multiplicativeaccurate max register into the construction proposed by Baig et al. [START_REF] Baig | Longlived counters with polylogarithmic amortized step complexity[END_REF] to obtain an unbounded k-multiplicative-accurate max register with sub-logarithmic amortized step complexity (omitted due to space constraints).

II. MODEL AND PRELIMINARIES

We consider an asynchronous shared memory system, where a set P of n crash-prone processes communicate by applying operations to shared objects. An object is an instance of an abstract data type. It is characterized by a domain of possible values and by a set of operations that provide the only means to manipulate it. An implementation of a shared object provides a specific data-representation for the object from a set of shared base objects, each of which is assigned an initial value; the implementation also provides algorithms for each process in P to apply each operation to the object being implemented. To avoid confusion, we call operations on the base objects primitives and reserve the term operations for the objects being implemented.

An execution fragment is a (finite or infinite) sequence of steps performed by processes as they follow their algorithms. In each step, a process applies at most a single primitive to a base object (possibly in addition to some local computation). We consider read, write and test&set primitives. An execution is an execution fragment that starts from the initial configuration. This is a configuration in which all base objects have their initial values and all processes are in their initial states.

A set of primitives is historyless if all the nontrivial primitives in the set overwrite each other; we also require that each such primitive overwrites itself. A primitive is nontrivial if it may change the value of the base object to which it is applied.

Operation op 1 precedes operation op 2 in an execution E, if op 1 's response appears in E before op 2 's invocation. We consider only deterministic implementations, in which the next step taken by a process depends only on its state and the response it receives from the event it applies.

Roughly speaking, an implementation is linearizable [START_REF] Herlihy | Linearizability: A correctness condition for concurrent objects[END_REF] if each operation appears to take effect atomically at some point between its invocation and response; it is wait-free [START_REF] Herlihy | Wait-free synchronization[END_REF] if each process completes its operation if it performs a sufficiently large number of steps; it is obstruction-free (also called solo-terminating) [START_REF] Herlihy | Obstruction-free synchronization: Double-ended queues as an example[END_REF] if each process completes its operation if it performs a sufficiently large number of steps when running solo.

The worst-case amortized step complexity (henceforth simply amortized step complexity) is defined as the worstcase (taken over all possible executions) average number of steps performed by operations. It measures the performance of an implementation as a whole rather than the performances of individual operations. More precisely, given a finite execution E, an operation Op appears in E if it is invoked in E. We denote by Nsteps(op, E) the number of steps performed by op in E and by Ops(E) the set of operations that appear in E. The amortized step complexity of an implementation A is then:

AmtSteps(A) = max E op∈Ops(E) Nsteps(op, E) |Ops(E)| III. UNBOUNDED APPROXIMATE k-MULTIPLICATIVE-ACCURATE COUNTER
We present a wait-free linearizable unbounded kmultiplicative-accurate counter with k ≥ √ n whose amortized step complexity is constant (Algorithm 1).

The algorithm uses an unbounded sequence of bits initially equal to 0, denoted switch 0 , switch 1 , . . . to approximately keep track of the number of increments that have been performed by the processes. For each i ≥ 0, switch i can be accessed by test&set and read operations. switch i .test&set() sets the value of switch i to 1 and returns its previous value. A read simply returns the value of switch i .

In a nutshell, each process locally keeps an accurate count of the number of CounterIncrement operations it performs and that are not yet known by the other processes. When this count reaches a certain threshold, the process tries to inform other processes of the number of increments it has performed locally, by attempting to set to 1 a switch in an appropriate bounded range. When a process succeeds in setting a switch to 1, it will restart the local count from 0. switch bits are set in increasing order with regards to their index, one after the other.

In particular, the initial value of the threshold is 1 and after their first call to CounterIncrement, each process will attempt to set switch 0 . Afterwards, the sequence of switch i with i ≥ 1 is partitioned into consecutive intervals of size k. For any such interval [qk + 1, (q + 1)k], where k is an integer, and for any j ∈ [qk + 1, (q + 1)k], switch j equals to 1 indicates that k q+1 instances of CounterIncrement have been performed by some process. In other words, a process p locally performs k q+1 instances of CounterIncrement before attempting to set a switch in the interval [qk+1, (q+1)k] and it increments its local threshold only if it knows that the last switch in this interval is set to 1 (i.e.; at least k • k q+1 instances of CounterIncrement have been performed). The threshold is incremented by a factor k. There is no guarantee that p will succeed in setting to 1 one of the switches. But in this case, sufficiently many increments have been performed by the processes so that a CounterRead operation can safely ignore the increments kept locally by p i and still returns a value within a bounded factor of the actual number of increments.

By using test&set to modify a switch from 0 to 1, we ensure that the CounterIncrement instances accounted for by switch j are distinct from those accounted for by switch j , for any j = j.

Performing an instance of a CounterRead operation op consists in traversing the sequence of switches until 0 is found. An approximation of the total number of CounterIncrement is then deduced from the index of the last switch j that op found equal to 1. The value returned is the sum of the CounterIncrement operations represented by each switch from switch 0 to switch j . In particular, switch 0 counts for one CounterIncrement, and each switch i in an interval [qk + 1, (q + 1)k] for some integer q ≤ q j counts for k q+1 CounterIncrement operations, where switch j belongs to the interval [q j k + 1, (q j + 1)k].

A. The CounterIncrement operation

Each process i is equipped with two persistent local variables, lcounter i and limit i . The former stores the number of CounterIncrement instances performed by process i not yet announced to the other processes; and the latter stores the treshold on the number of CounterIncrement that can be performed by process i without informing the other processes.

When a CounterIncrement operation is invoked by a process i, lcounter i is first incremented (line 11). To ensure that a CounterRead operation instance returns a value that is within a multiplicative factor k of the actual number of increments, when lcounter i reaches a certain threshold stored in limit i , process i tries to inform the other processes of the number of increments it has performed locally (lines 12). The value of limit i is initially 1 and is multiplied by k each time it is modified (line 21 and line 28). When lcount i = limit i = k q+1 for some integer q, process i tries to set to 1 one of the k switch j whose index j is in the corresponding range [qk + 1, (q + 1)k] (lines 15-23). If it succeeds, it resets the local counter lcounter i . The number of CounterIncrement instances it has performed locally has been announced to the other processes, and thus will be taken into account by future CounterRead operations.

Additionally, process i writes the index of the switch it sets together with a sequence number into a shared variable H[i] (lines 17 and 18). As explained later this pair is intended to help CounterRead operation instances to complete. Finally, the process will also update the value of the local persistant variable l 0 to indicate the index of the switch it managed to set within the interval (line 22). By doing so, we ensure that the process will avoid attempting to reset the same switches every time it reaches the treshold of limit i in the current interval by starting from the index qk + l 0 in the next attempt. If it does not succeed, every switch j , where j ∈ [qk + 1, (q + 1)k] is set. We show in the proof that for k ≥ √ n, this number is sufficiently large for allowing CounterRead operations to return values within a factor k of the total number of CounterIncrement instances (Section III-C). The threshold limit i is then incremented by a factor k (line 28) and the value of l 0 is reset to 1 (line 24).

B. The CounterRead operation

When a CounterRead operation is invoked, process i scans the first and last switch of each interval of k switches, looking for the first one that is not yet set to 1. When such a switch is found, the index h of the last switch read that was equal to 1 is stored in the persistent local variable last i to avoid scanning the sequence from the beginning each time. We compute the value ret returned by the CounterRead operation in the function ReturnValue(p, q) where h = q • k + p (line 30). First, we consider the required increments needed to set all the switches in the current interval [qk + 1, (q + 1)k] by adding to ret the value p • k q+1 (line 31). Next, we add 1 to ret to account for the first switch 0 (line 31), and then for each previous interval [(l -1)k + 1, lk] where 1 ≤ l ≤ q, we add k l+1 to ret (line 33). Finally, we return the computed value ret multiplied by a factor k to ensure ret falls in the approximation range of the k-multiplicative-accurate counter.

However, it may be the case that the condition at line 37 is never verified, as other processes may concurrently keep executing CounterIncrement operations. Thus, to ensure wait-freedom, we employ the following helping mechanism : a CounterIncrement operation by a process i that succeeds to set a switch j , writes the index j of this switch together with a sequence number in the shared register H[i] (lines 17 and 18). A CounterRead operation op that fails to find a switch to 0 after θ(n) steps, reads all the n shared registers H[i] with i ∈ 1, . . . , n. If a consistent value is found, then it returns at line 55. Otherwise, it executes another θ(n) steps. The first time op scan the array H, it stores the sequence number read in each H[j], denotes sn j . When scanning H again, op will select a pair whose timestamp is greater than or equal to sn j +2. This ensures, that the corresponding switch has been set by process j in the execution interval of op. Suppose by contradiction that op r does not terminate. Meaning that every bit switch it reads has been set to 1. Since the bits are initially 0, there is at least one process q that infinitely often performs a successful test&set operation on these bits. Note that each time this occurs, q increments its sequence number sn q and reports the new value in the helping array H (lines [START_REF] Herlihy | Wait-free synchronization[END_REF][START_REF] Herlihy | Obstruction-free synchronization: Double-ended queues as an example[END_REF]. As every n iterations of the while loop, op r scans the array H, it will eventually detect that the sequence number of q has been incremented at least twice, hence op r terminates via the helping mechanism (lines 50-55). Therefore, operations CounterIncrement and CounterRead are wait-free.

We continue with a few technical lemmas.

Lemma III.2. Switches are set to 1 in E in increasing order of their index, starting from switch 0 .

Proof: For each process p the initial value of limit p is 1 and of counter p is 0, thus the first CounterIncrement operation by process p applies a test&set primitive to switch 0 according to lines 11, 12, 13, and 27. We now prove that for any given process p and for any j ≥ 1, p applies a test&set primitive (if any) on each of the switches with indexes in the interval [(j -1) • k + 1, . . . j • k] in an increasing order of their index, starting from switch (j-1)•k+1 . First observe that for any process p, the initial value of l 0 is 1, and l 0 is set to 1 iff the value of limit p is multiplied by a factor k Algorithm 1: k-multiplicative-accurate unbounded counter, code for process i. (lines 24,28 and lines 21,22). This implies that when a new j is computed at line 13, the value of l 0 is 1.

lcounter i ← lcounter i + 1 if lcounter i = limit i then j ← log k (lcounter i ) if j > 0 then 15 for ← (j -1)k + l 0 , . . . , j • k do 16 if switch .test&set() = 0 then 17 sn i ← sn i + 1 18 H [i] ← ( , sn i ) 19 lcounter i ← 0 20 if = jk then 21 limit i ← k • limit i 22 l 0 ← 1 + mod k 23 return 24 l 0 ← 1 else 26 if switch 0 .test&set() = 0 then 27 lcounter i ← 0 limit i ← k • limit i return Function ReturnValue(p,q) ret ← 1 + p • k q+1 if q ≥ 1 then ret ← ret + q l=1 k l+1 return k • ret 35 Function CounterRead() 36 c ← 0 37 while switch lasti = 0 do 38 p ← last i mod k 39 q ← lasti k 40 if last i mod k = 0 then 41 last i ← last i + 1 42 else 43 last i ← last i + k -1 44 c ← c + 1 45 if c mod n = 0 then 46 if c = n then 47 for j ← 1, . . . , n do 48 help i [j] ← H[j].sn
Then the first iteration of the for loop at line 15 starts at l = (j-1)•k+1. Also, the value of l is incremented by one at each iteration of the for loop at line 15 unless p succesfully sets a switch (j-1)k+i with i ∈ {1, . . . , k}. In this latter case, the value of l 0 is modified at line 22 and takes the value i+1 if i < k, or 1 otherwise (we reach the end of the set). If l 0 takes a value different from 1, that is l = j • k, (otherwise the claim is proved), then the CounterIncrement operation returns at line 23 without modifying the value of limit p . Thus, in the execution of a successive CounterIncrement operation (if any), process p will apply the next test&set primitive (if any) to switch jk+i+1 (because of lines 12, 13, 15). The value of limit i is multiplied by k (and than the value of j is incremented by one) only after a process has applied a test&set primitive (both successfully or not) to the last switch in the current interval [(j -1) • k + 1, . . . , j • k] with log k (limit i ) = j (lines 21, 28). This completes the proof.

Lemma III.3. For any given execution E, if a CounterRead operation op returns the value computed in ReturnValue(p, q) at line 55, then switch q•k+p was equal to 0 before the invocation of op and the test&set primitive that sets switch q•k+p to 1 is applied during the execution interval of op.

Proof: At line 51, op reads a pair (val, σ) from an entry H[p ] of the helping array H where val = q•k+p. According to lines 16, 17, and 18, a unique process p sets to 1 the switch val and associates with val the sequence number σ computed at line 17, before writing the pair (v, σ) to H[p ] in the execution of a CounterIncrement operation op .

Let p be the process that executes the CounterRead operation op. Denote by σ the value of H[p ].sn read by p at line 48 in the execution of op. According to line 52, σ -σ ≥ 2. This means that process p executes line 17 at least twice during the execution interval of op. In particular p executes the step that set switch val to 1 after op was invoked by p. This proves the claim.

2) Linearizability: We next define the linearization L of the operations in E by first removing any CounterRead operation that did not complete and any incomplete CounterIncrement operation that has not successfully executed line [START_REF] Attiya | Time and space lower bounds for implementations using k-cas[END_REF].

Let OP W be the set of (complete and incomplete) CounterIncrement operations that sucessfully set a switch while executing line 16. Let OP LO be the remaining complete CounterIncrement operations in E and OP R be the set of complete CounterRead operations in E. Observe that each CounterIncrement operation succesfully sets at most one switch, and each switch is succesfully set by at most one process. Thus we can univocally associate each operation in OP W with the switch it sets. We order the operations in OP W ∪ OP LO ∪ OP R , according to the following rules :

1) We linearize each operation in OP W at the step where it sets its corresponding switch. By claim III.2, operations in OP W are totally ordered and this order respect the real-time order. In the following we denote opw i the i-th operation in OP W according to our linearization order with i ≥ 0. 2) We linearize a CounterRead operation opr according to whether it returns normally or through the helping mechanism: a) If opr returns ReturnValue(p, q) normally at line 58, then it is linearized at the step where it reads the value 1 of switch q•k+p at line 37 . This is well-defined because this read primitive exists and it is unique (it is easy to check from the pseudo-code). b) If opr returns ReturnValue(p, q) via the helping mechanism at line 55, then the operation is linearized immediately after opw q•k+p . 3) Let L W R denote the linearization of all operations in OP W ∪ OP R according to rule 1 and 2, we linearize an operation op in OP LO immediately before the first operation op in L W R that follows op in the real-time order or at the end of L W R if op does not exist. CounterRead operations that returns 0 after reading switch 0 = 0 are linearized before opw 0 . If several operations are ordered at the same position, they are ordered respecting their real time order. Linearization rule 2 and Lemma III.3 implies the following claim.

Claim III.4. Let opr be a CounterRead operation. We have that opr is linearized at some point after its invocation.

Lemma III.5 (Linearizability). Algorithm 1 is a linearizable implementation of a k-multiplicative-accurate unbounded counter.

Proof: Let op 1 and op 2 be two operations in E such as op 1 ends before op 2 is invoked. We prove that the linearization order L respects the real-time order, thus op 1 precedes op 2 in L. First, we have the following claim:

• Let op 1 and op 2 be two CounterIncrement operations.

If at least one of these operations is in OP LO , the claim trivially follows from rule 3. Otherwise it is already proved in rule 1. CounterRead operation. The claim follows from rules 1 and 2 and claim III.4 (the reverse follows a similar reasoning). Next claim will be useful for proving that the ordering L is consistent with the sequential specification of the kmultiplicative-accurate counter.

Claim III.6. Let op be a CounterRead operation invoked by a process p i that returns ReturnValue(p, q). Then, the number of CounterIncrement operations linearized before op in L, denoted v, is at least

u min = 1 + q l=1 k l+1 + p • k q+1 and at most u max = 1 + q l=1 k l+1 + p(k -1)k q+1 + n(k q+1 -1)
where n is the number of processes.

Proof: Let op be a CounterRead operation invoked by a process p i that returns ReturnValue(p, q) and let h = q • k+p with p ≥ 0. Consider the CounterIncrement operation by p j that set to 1 the switch h , denoted opw h .

op is linearized at the step where it reads switch h if it returns normally, or immediately after opw h . Thus, from our linearization rules, the minimal number of CounterIncrement operations that are linearized before op includes each opw i in OP W with 0 ≤ i ≤ h, and every CounterIncrement in OP LO linearized before op.

We have by construction that each switch s in the (l + 1)th set of k switches indexed in the interval [l • k + 1 . . . (l + 1)k] with l ≥ 0, requires a process to perform k l+1 CounterIncrement operation instances before attempting to set switch s to 1. In other words a process p i needs its local variable lcounter i to be equal to k l+1 before it can attempt to set any switch s in [l • k + 1 . . . (l + 1)k] (line 12). Since the value of lcounter i is reset to 0 after a succesful test&set primitive is applied on a switch (line 19), the sets of CounterIncrement operation instances associated with any pair of succesful test&set primitives are disjoint. Thus,

u min = 1+k q-1 l=0 k l+1 +p•k q+1 = 1+k q l=1 k l +p•k q+1
since we account for, in addition to the p switches in the (q + 1)-th set and switch 0 , all k switches in each of the sets indexed from 1 to q.

Similarily, we compute an upper bound u max on the maximum number of CounterIncrement linearized before op. First suppose that op returns normally. As already said, op is linearized at the step where it reads switch h with h = qk + p. We have two possible cases either p is equal to 0 or it is equal to 1 because the process checks the first and last switch of each set during the CounterRead () instance. These two cases are depicted in Figure 1 a) and b) respectively. If p is equal to 0, then process p i read switch kq+1 = 0 in the execution of op, and according to our linearization rules opw kq+1 is linearized after op. In a similar way, if p is 1 p i read switch (q+1)k = 0 and opw (q+1)k is linearized after op. However, in this second case, all the k-1 switches j with j ∈ [q • k + 2 . . . (q + 1)k -1] may have been set to 1 before op applied its read to switch qk+1 , and all the corresponding opw j may be linearized before op. Thus, the number of opw linearized before op is smaller than or equal to 1 + q l=1 k l+1 + p(k -1)k q+1 . It remains to count the number of CounterIncrement in OP LO linearized before op. For every process p i the value of lcounter i is smaller than k q+1 immediately before p read either switch kq+1 = 0 or switch (q+1)k = 0 in the execution of op. Since a process resets the value of its local counter only when it succeeds to set a switch to 1 (line 19), lcounter i defines the number of CounterIncrement by p i in OP LO that are linearized before op. Therefore,

u max = 1 + q l=1 k l+1 + p(k - 1)k q+1 + n(k q+1 -1)
where n is the number of processes. If op returns via the helping mechanism, then according to rule 2b, it is linearized immediately after opw q•k+p with 0 ≤ p < k. Thus, 1 + q l=1 k l+1 + pk q+1 is the number of CounterIncrement in OP W linearized before op. Since p < k the local counter of every process immediately after opw q•k+p sets the corresponding switch is smaller than k q+1 . Since k > 1, the claim follows.

Let op be a CounterRead operation and let v op = ReturnValue(p, q) be the value it returns. According to lines 31, 33 and 34 of Algorithm 1, v op = k(1+ q l=1 k l+1 + p•k q+1 ); that is v op = k •u min . According to claim III.6, the number of CounterIncrement operations linearized before op in L, denoted u, is at least u min = 1 + q l=1 k l+1 + p • k q+1 and at most u max = 1 + q l=1 k l+1 + p(k -1)k q+1 + n(k q+1 -1) (where n is the number of processes). And we have:

u max k = 1 k + q l=1 k l + p k -1 k k q+1 + n k (k q+1 -1) u max k ≤ q l=1 k l + p • k q+1 + n • k q And v op = k(1 + k q l=1 k l + p • k q+1 ) = k(1 + k q-1 l=1 k l + k q+1 + p • k q+1 ) = k + k q l=2 k l + p • k q+2 + k q+2 Thus, for k ≥ √ n, umax k ≤ v op . Therefore, since p < k, we have u k ≤ umax k ≤ v op ≤ k • u min ≤ k • u.
This completes the proof. 3) Complexity analysis: Lemma III.7. If process p applies a test&set() primitive to a switch α with i•k+1 ≤ α ≤ (i+1)•k for some integer i ≥ 0, then p has performed at least k i+1 CounterIncrement() operations.

Proof: Suppose that p has executed a test&set() primitive to a switch α with i•k+1 ≤ α ≤ (i+1)•k in the execution of a CounterIncrement() operation op. According to line 15, j was equal to i + 1 when computed at line 13, meaning that lcounter p was equal to k i+1 . The claim holds because lcounter p is incremented only at line 11, that is once for each CounterIncrement() operation performed by p.

Lemma III.8 (Amortized complexity). For k ≥ √ n, the amortized complexity of Algorithm 1 is constant.

Proof: Let E be a finite execution of the unbounded k-multiplicative-accurate counter object implemented in Algorithm 1. Let r denote the number of CounterRead () instances in E and s be the number of CounterIncrement() instances in E. We additionally denote Ops W (E) the set of CounterIncrement() operations that execute at least one step in E, and Ops R (E) the set of CounterRead () operations in E. We want to compute AmtSteps(E) = op∈Ops W (E)∪Ops R (E) N steps(op, E) r + s where N steps(op, E) is the number of steps executed by op in E.

Let Ops Wp (E) denote the CounterIncrement() operations in Ops W (E) executed by process p and s p denote the total number of CounterIncrement() operations executed by process p. Let α p be the index of the furthest switch accessed by a process p when executing any of the CounterIncrement() operations in Ops Wp (E). We have that i p • k + 1 ≤ α p ≤ (i p + 1) • k for some integer i p ≥ 0 (the case where α p = 0 is trivial).

In the worst case, process p applies a test&set() primitive to switch h for every h ∈ [0, . . . α p ] and one additional step to write into H[p] (line 18) each time p successfully set one of those switches. On the other hand, by Lemma III.7 if process p applies a test&set() primitive to the switch αp , then it has performed at least k ip+1 CounterIncrement() operations. Therefore,

op ∈ Ops Wp (E) N steps(op) ≤ 2 • (i p + 1)k + 1 And s p ≥ k ip+1
Thus, the total number of steps executed by the set of all processes P in order to perform the CounterIncrement() operations in E is :

op∈Ops W (E) N steps(op) = p ∈ P op ∈ Ops Wp (E)
N steps(op)

≤ p ∈ P 2 • (i p + 1)k + 1 And s = p ∈ P s p ≥ p ∈ P k ip+1
Now we consider the number of steps applied by each process to perform CounterRead operations. Let α be the index of the furthest switch set to 1 by any process in P. If α = 0 then the claim follows. Then suppose i•k+1 ≤ α ≤ (i+1)•k for some integer i ≥ 0. For any sequence of switches with the index in [j •k+1, . . . , (j +1)•k] with 0 ≤ j ≤ i a process p only reads the first and the last switch in such interval (i.e., switch j•k+1 and switch (j+1)•k ). This is because at the beginning last p is equal to 0 and it is incremented by 1 if it is a multiple of k (at line 41), by k -1 otherwise (line 43). Also, last p is a persistent variable, thus a process p reads a given switch that has been set to 1 at most once. This implies that the total number (in all its CounterRead operations) of read primitives applied by a process p to the switches is less or equal to 2(i + 2) (2 per each of the i + 1 intervals, plus switch 0 and switch α+1 ). Furthermore, any CounterRead () operation executes O(n) steps of the for loop at line 47 or line 50 once every n iterations of the while loop (when the condition of line 45 is satisfied). This means that the total number of steps executed by a process p when performing its CounterRead () operations is less or equal to 4(i + 2). Thus,

op ∈ Ops R (E) N steps(op) ≤ p ∈ P r 4(i + 2) ≤ 4(i + 2) • n r
where P r is the set of processes who have invoked at least one CounterRead () operation and n r is the cardinality of P r . Consider n r > 0, the other case is trivial. Therefore:

AmtSteps(E) ≤ p ∈ P 2(i p + 1)k + 1 p ∈ P k ip+1 + r + 4(i + 2) • n r s + r
Furthermore, by lemma III.7 the minimum number of instances of the CounterIncrement() operation executed to set the switch α is k i+1 . Thus,

AmtSteps(E) ≤ p ∈ P 2(i p + 1) + 1 k p ∈ P k ip + r k + 4(i + 2) • n r k i+1 + r
We have k x ≥ x + 1 for k ≥ e and ∀x ∈ R, it follows:

p ∈ P 2(i p + 1) + 1 k p ∈ P k ip + r k ≤ p ∈ P 2(i p + 1) + 1 k p ∈ P (i p + 1)
If i = 0, and since r ≥ n r we have:

4(i + 2) • n r k i+1 + r ≤ 8 • n r k + r ≤ 8
If i ≥ 1, because n r ≤ n and k i+1 ≥ i • k 2 we have:

4(i + 2) • n r k i+1 + r ≤ 4(i + 2) • n i • k 2 + r
Resulting in an amortized complexity of O(1) for k ≥ √ n.

From Lemma III.1, III.5 and III.8 we conclude:

Theorem III.9. Algorithm 1 is a wait-free linearizable implementation of a k-multiplicative-accurate unbounded counter with a constant amortized complexity for k ≥ √ n.

D. An Amortized Step Complexity Lower bound for kmultiplicative accurate Counters

In this section, we prove that the amortized step complexity of solo-terminating implementations of k-multiplicative accurate counters is Ω(log q+1 n k 2 ) for k ≤ n/2, assuming the implementation uses base objects that support only read, write and either reading or regular conditional primitives of arity q or less. A primitive has arity q if it is applied atomically to a vector of q base objects. In all the paper but this section, we consider q = 1. Definitions and most of the technical lemmata hold from [START_REF] Attiya | Time and space lower bounds for implementations using k-cas[END_REF]. In the following we provide the main idea of the lower bound and the Lemma that most differs from the original work. To this aim, in the following we remember some of the definitions formalized in [START_REF] Attiya | Time and space lower bounds for implementations using k-cas[END_REF].

Processes communicate with one another by issuing events that apply read-modify-write (RMW) primitives to vectors of base objects. We assume that a primitive is always applied to vectors of the same size and that all the base objects to which a primitive is applied are over the same domain. A RMW primitive, applied to a vector of k base objects over some domain D, is characterized by a pair of functions, g, h , where g is the primitive's update function and h is the primitive's response function. The update function g : D k × W → D k , for some inputvalues domain W , determines how the primitive updates the values of the base objects to which it is applied.

Let e be an event, issued by process p after execution E, which applies the primitive g, h to a vector of base objects o 1 , . . . , o k . Then e atomically does the following: it updates the values of objects o 1 , . . . , o k to the values of the components of the vector g( v 1 , . . . , v k , w), respectively, where -→ v = v 1 , . . . , v k is the vector of values of the base objects after E, and w ∈ W is an input parameter to the primitive. We call -→ v the object-values vector of e after E.

The RMW primitive returns a response value, h( -→ v , w), to process p. If W is empty, we say that the primitive takes no input.

Next, we revise the concept of conditional synchronization primitives.

Definition III.1. A RMW primitive g, h is conditional if, for every possible input w, - → v |g( - → v , w) = - → v ≤ 1.
Let e be an event that applies the primitive g, h with input w. The change point of e is the unique vector -→ c w such that g( -→ c w , w) = -→ c w ; any other vector is a fixed point of e.

For example, k-CAS is a conditional primitive for any integer k ≥ 1. The single change point of a k-CAS event with input old 1 , . . . , old k , new 1 , . . . , new k is the vector old 1 , . . . , old k . Read is also a conditional primitive, since read events have no change points.

A RMW event is invisible if its object-values vector is a fixed point of the event when it is issued. A RMW event e that is applied by process p to an object vector is also invisible if, before p applies another event, a write event is applied to each object o i that is changed by e before another RMW event is applied to o i . If a RMW event e is not invisible in an execution E on some object o, we say that e is visible in E on o. If e is not invisible in E, we say that e is a visible event in E.

Lower bound: The key intuitions behind the following lower bound is that first, in any n-process execution of a kmultiplicative accurate counter implementation, 'many' processes need to be aware of the participation of 'many' other processes in the execution, and second, if processes only use read, write and conditional primitives, then a scheduling adversary can order events so that information about the participation of processes in the computation accumulates 'slowly'.

We formalize the first key intuition by proving Lemma III.10. The rest is straightforward from the lower bound in the original work [START_REF] Attiya | Time and space lower bounds for implementations using k-cas[END_REF].

The next definition captures the extent to which processes are aware of the participation of other processes in an execution. Intuitively, a process p is aware of the participation of another process q if p reads a shared-memory value that was either directly written by q or indirectly influenced by a value written by q. The following definitions formalize this notion.

Definition III.2. Let e q be an event by process q in an execution E, which applies a non-trivial primitive to a vector v of base objects. We say that an event e p in E by process p is aware of e q if e p accesses a base object o such that at least one of the following holds:

• There is a prefix E of E such that e q is visible on o in E and e p is a RMW event that applies a primitive other than write to o, and it follows e q in E , or • there is an event e r that is aware of e q in E and e p is aware of e r in E.

If an event e p of process p is aware of an event e q of process q in E, we say that p is aware of e q and that e p is aware of q in E.

The following definition quantifies the extent to which a process is aware of the participation of other processes in an execution.

Definition III.3. Process p is aware of process q after an execution E if either p = q or p is aware of an event of q in E. The awareness set of p after E, denoted AW (E, p), is the set of processes that p is aware of after E.

The following lemma proves a relation between the value returned by a CounterRead operation instance of a process in some execution and the size of that process' awareness set after that execution. This is our main technical contribution to the lower bound.

Lemma III.10. Let E be an execution of a soloterminating k-multiplicative accurate counter object implementation where each process executes one instance of the CounterIncrement() operation followed by one instance of the CounterRead () operation. If the CounterRead () instance by a process p returns i in E then |AW (E, p)| ≥ i k . Proof: Assume, by way of contradiction, that there is an execution E where each process executes one instance of the CounterIncrement() operation followed by one instance of the CounterRead () operation, and a process p such that a CounterRead () instance by p, namely op, returns i and |AW (E, p)| < i k . We construct a new execution E as follows: for any process q / ∈ AW (E, p), we first remove all the events of q from E; then, for any process q , we remove all the events of q that are aware of q. Note that if an event e q of q is aware of q, then all following events by q are also aware of q and are removed. Also, no events of p are removed since p is aware only of processes in AW (E, p).

We prove that E is an execution, and that it is indistinguishable from E. We consider events in the order they appear in E . Let e q be an event by process q that appears in E , namely E = E 1 e q E 2 . Since e q is also in E, we can also write E = E 1 e q E 2 . For the induction, assume that E 1 is an execution and that it is indistinguishable to every process that appears in it from E 1 . In particular, q does not distinguish between E 1 and E 1 and takes the same step after both of them. To see why q obtains the same response in e q after E 1 and after E 1 , note that it can return a different response only if in E, e q is aware of an event e that was removed from E 1 . This happens only if e is aware of some process q / ∈ AW (E, p), meaning that in E, e q is also aware of q, contradicting the fact that e q was not removed. Hence E 1 e q is an execution and q does not distinguish between E 1 e q and E 1 e q .

This implies that the CounterRead () instance by p returns i also in E ; on the other hand, less than i k processes participate in E . Let E" be the extension of E in which the processes that participate in E complete their operation instances, one at a time. This execution exists by solotermination, and results in a quiescent execution. However, less than i k instances of CounterIncrement() operations completed in E", and we have that p returns i when invoking op. Thus, the response of the op is not linearizable. In particular, consider any linearization L of E" and let v be the number of CounterIncrement() instances linearized before op in L, we have that

v k ≤ i ≤ k • v < k • i k = i.
Corollary III.10.1. Let E be a quiescent n-process execution of a solo-terminating k-multiplicative counter implementation, where each process executes one instance of the CounterIncrement() operation followed by one instance of a CounterRead () operation. Then, the awareness sets of n 2 processes contain at least n 2k 2 other processes after E. Proof: Let L denote any linearization of E, and let op be the i-th CounterRead () instance in L. Since op is the i-th instance of CounterRead () in L, it returns v such that v ≥ i k . By considering the last n 2 processes linearized and by Lemma III.10, the claim follows.

Information about processes that participate in an execution is transferred through base objects. To complete the proof, we need to show that each of the n 2 processes has to apply Ω(log q+1 (n/k 2 )) events to build its awareness set (proved in the Appendix).

The following theorem formalize our step complexity lower bound.

Theorem III.11. Let A be an n-process solo-terminating implementation of a k-multiplicative counter from base objects that support only read, write and either reading or regular conditional primitives of arity q or less. Then A has an execution E that contains Ω(n log q+1 (n/k 2 )) events for k ≤ n/2, in which every process performs a single CounterIncrement() instance and a single CounterRead () instance.

IV. A k-MULTIPLICATIVE-ACCURATE BOUNDED MAX REGISTER

In this section, we present an implementation of a kmultiplicative-accurate max register. The algorithm is waitfree, and has asymptotically optimal worst-case step complexity. Indeed, we present in the next section a matching lower bound.

The key idea of our algorithm is to consider the kbase representation of values written to the register and have Write operations store only the index of the bit preceding (i.e., to the left of) the most significant bit (MSB) of their arguments. These indices are stored in an (accurate)

( log k (m-1) )+1 -bounded max register implemented in a wait-free manner [START_REF] Aspnes | Polylogarithmic concurrent data structures from monotone circuits[END_REF]. A Read operation R reads the value p of the accurate max register. If it equals 0 (implying that it was not written to yet), R returns 0. Otherwise, p is the largest index written so far to the accurate max register and R returns k p . The pseudocode is presented by Algorithm 2. We now prove that Algorithm 2 is a correct wait-free implementation of a k-multiplicative-accurate max register. Observation 1. Algorithm 2 is a wait-free implementation of a k-multiplicative-accurate m-bounded max register.

Proof: Follows directly from the wait-freedom of the max register algorithm of [START_REF] Aspnes | Polylogarithmic concurrent data structures from monotone circuits[END_REF].

Lemma IV.1. Algorithm 2 is a linearizable implementation of a k-multiplicative-accurate m-bounded max register.

Proof: Let M k m denote a k-multiplicative-accurate mbounded max register implemented by Algorithm 2 and let E be an execution of M k m . We now specify how operation instances on M k m in E are linearized. First, all the instances of Read that did not execute line 3 in E and all the instances of Write operations did not execute line 9 in E do not appear in the linearization. We say these are removed operations. Note that none of the removed operations has completed in E. For all remaining instances, we define the linearization point of a Read operation on M k m to be the linearization point of the read operation it invoked on M in E (in line 3) and the linearization point of a Write operation on M k m as the linearization point of the write operation it invokes on M (in line 9). Since each nonremoved operation instance on M k m in E is linearized at a step it performs (hence during its execution interval), the linearization order we have define, denoted by L, respects the real-time order of the operation instances in E.

It remains to show that L satisfies the sequential specification of a k-multiplicative-accurate m-bounded max register. First note that since values written to M k m are from {1, ..., m -1} and from lines 8-9, only values from {1, ..., log k (m -1) + 1} are written to M. Let R denote a Read instance in L that returns 0 in line 4. Since only positive values are ever written to M, it follows that R is not preceded in L by any Write instance, hence the value of M k m when R is linearized is its initial value 0, so R returns the exact value of M k m . Assume, then, that R is preceded in L by one or more Write instances and returns a positive value x = k p for some p ≥ 1. We need to prove that v/k ≤ x ≤ vk holds, where v is the maximum value written by any Write() instance linearized before R in L. Since M is linearizable and since we have linearized all non-removed instances applied to M k m in E according the order of the operations they applied to M (in line 3 or in line 9), there exists a Write operation that writes some value w and appears before R in L, such that log k w = p -1 and p is the maximum value written to M by any Write instance that precedes R in L. Let V = {w log k (w) = p -1} be the set of all the values written to

M k m in L before R whose MSB equals p -1. Let v = max(V ). It follows that v is the maximum value written to M k m by any Write() instance linearized in L before R. We have v ∈ [k p-1 , k p -1] and x = k p . Consequently, v ≤ x ≤ v • k
and the sequential specification of the k-multiplicative m-bounded max register is satisfied.

Theorem IV.2. Algorithm 2 is a wait-free linearizable implementation of a k-multiplicative-accurate m-bounded max register with worst case operation step complexity O min log 2 (log k m), n .

Proof: Wait-freedom and linearizability follow from Observation 1 and Lemma IV.1, respectively. As for step complexity -the worst case operation step complexity of the wait-free implementation of an m-bounded max register of [START_REF] Aspnes | Polylogarithmic concurrent data structures from monotone circuits[END_REF] is O min(log m, n) for both Read and W rite operations. Each operation of Algorithm 2 applies a single operation on a ( log k (m -1) ) + 1 -bounded max register and a constant number of additional steps. The theorem follows.

V. A LOWER BOUND ON THE WORST CASE STEP COMPLEXITY OF K-MULTIPLICATIVE M-BOUNDED MAX REGISTER AND COUNTER Aspnes et al. [START_REF] Aspnes | Lower bounds for restricted-use objects[END_REF] proved a worst-case step complexity on the lower bound of a class of concurrent objects called L-perturbable, that includes objects such as max registers, counters and snapshots. L is called the perturbation bound. Roughly speaking, an object is L-perturbable if, for every implementation of the object, there exists an operation Op and an execution E, in the course of which Op is "perturbed" L times. An outstanding operation Op by process p is said to be perturbed by a process q, if a solo execution by q can change the response of a solo execution by p. They prove [5, Theorem 1] that any obstruction-free implementation of an L-perturbable object O from historyless primitives has an execution in which some process accesses Ω min(log 2 L, n) distinct base objects during a single operation instance. Specifically, this implies that the worst-case step complexity of such implementations is Ω min(log 2 L, n) .

For the sake of presentation completeness, we restate the definition of an L-perturbable object from [START_REF] Aspnes | Lower bounds for restricted-use objects[END_REF].

[5], Definition 2. Let I be an obstruction-free implementation of an object. The set S k of k-perturbing executions with respect to an operation instance op n by process p n is defined inductively as follows:

1) S 0 is the singleton set containing the empty sequence.

2)

If α k-1 λ k-1 is in S k-1
, where λ k-1 consists of n -1 events, one by each of the processes p 1 , . . . , p n-1 , then

α k-1 λ k-1 is in S k . In this case, we say that α k-1 λ k-1 is saturated. 3) Suppose α k-1 λ k-1 is in S k-1
, no process has more than one event in λ k-1 , and there is a sequence γ of events by a process p l different from p n and the processes that have events in λ k-1 , such that the sequences of events by p n as it performs op n after α k-1 λ k-1 and α k-1 γλ k-1 differ. Let γ = γ eγ , where e is the first event of γ such that the sequences of events taken by p n as it performs op n by itself after α k-1 λ k-1 and after α k-1 γ eλ k-1 differ. Let λ be some permutation of the event e together with the events in λ k-1 , and let λ , λ be any two sequences of events such that λ = λ λ . Then the execution α k λ k is in S k , where α k = α k-1 γ λ and λ k = λ .

[5], Definition 3. An obstruction-free implementation of an object is L-perturbable if there is an operation instance op n such that the set S L of L-perturbing executions with respect to op n by p n is nonempty.

An object O is perturbable if all its obstruction-free implementations are perturbable.

[5], Theorem 1. Let A be an n-process obstruction-free implementation of an L-perturbable object O from historyless primitives. Then A has an execution in which some process accesses Ω(min(log 2 L, n)) distinct base objects during a single operation instance. Lemma V.1. A k-multiplicative-accurate m-bounded max register is Θ(log k m)-perturbable for k > 1.

Proof: Let O be a k-multiplicative-accurate m-bounded max register and consider an obstruction-free implementation of O. We show that O is (1 2 log k (m -1))-perturbable for a Read() operation instance op n by process p n . We proceed by induction where the base case for r = 0 is immediate. Let r < 1 2 log k (m -1) and let α r-1 λ r-1 be an (r -1)-perturbing execution of O. If α r-1 λ r-1 is saturated, then it is also an r-perturbing execution. Otherwise, denote by v r-1 the maximum input to the write() operations linearized before op n in the execution sequence α r-1 λ r-1 . Since α r-1 λ r-1 is not saturated, there exists a process p l = p n that does not take steps in λ r-1 . Let γ be the execution fragment by p l where it finishes any incomplete operation in α and then performs a write() operation to the max register with the value v r = k 2 v r-1 + 1. Then op n must return a value x such that kv r-1 < v r /k ≤ x ≤ kv r when run after α r-1 γλ r-1 . It follows that an r-perturbing execution can be constructed from α r-1 λ r-1 and γ as specified by [START_REF] Aspnes | Lower bounds for restricted-use objects[END_REF], Definition 2. Because O is an m-bounded max register, during the rth step of the induction, the value written to the max register must satisfy v r ≤ m -1. Consequently it suffices to have: Proof: Let O be a k-multiplicative m-bounded counter and consider an obstruction-free implementation of O. We show that O is ( 1 2 log k (m -1))-perturbable for a CounterRead () operation instance op n by the process p n . We proceed by induction where the base case for r = 0 is immediate. Let α r-1 λ r-1 be an (r-1)-perturbing execution of O. If α r-1 λ r-1 is saturated, then it is also an rperturbing execution. Otherwise, let I r denote the number of CounterIncrement() operation instances performed by the perturbing process in iteration r. We have that I 1 = 1 in order for op n to return a value greater than 0. For r > 1, if op n runs after a r-1 λ r-1 it can return a value that is as large as k • r-1 j=1 I j . Therefore, we need the number of complete CounterIncrement() operation instances after a r-1 γλ r-1 to be at least k 2 • r-1 j=1 I j + 1 for op n to return a value greater than k •

v r ≤ (k+1) 2r ≤ m-1 =⇒ r ≤
I r = r-1 i=0 (r -i)(k 2 -1) i = r i=1 i • (k 2 -1) r-i = (k 2 -1) r r i=1 i (k 2 -1) i = (k 2 -1)((k 2 -1) r -1) + r(2 -k 2 ) (k 2 -2) 2 ≤ k 2r ≤ m =⇒ r ≤ 1 2 log k (m) = Θ(log k m)
From Lemma V.

VI. DISCUSSION

We have presented upper and lower bounds on the step complexity of a variant of deterministic approximate counters and max-registers. We have proved the possibly counterintuitive 1 result that when the accuracy parameter k does not depend on n, relaxing counter semantics by allowing inaccuracy of a multiplicative factor cannot asymptotically reduce the step complexity of unbounded counters by more than a logarithmic factor. Then, we present a wait-free linearizable k-multiplicative-accurate counter for k ≥ √ n with constant amortized step complexity.

The maximum improvement in the worst case step complexity of the bounded variant of k-multiplicative-accurate counters remains an open question. Also, when k is constant, it is unclear whether there exists a deterministic waitfree k-multiplicative-accurate counter implementation with o(log 2 n) amortized step complexity.

We also show that relaxing the semantics of max registers by allowing inaccuracy of even a constant multiplicative factor yields an exponential improvement in the worstcase step complexity of the bounded variant and in the amortized step complexity of the unbounded one. Overall we provide theoretical evidence that worst-case time complexity does not indicate benefit from some common relaxation of unbounded counters and max-register while average complexity does. It is interesting to note that a similar result has been proved for relaxed queues in the message passing systems by Talmage and Welch [START_REF] Talmage | Improving average performance by relaxing distributed data structures[END_REF].

C. Proof 1 )

 1 Wait-freedom and technical lemmas: Let E be an execution of the k-multiplicative-accurate unbounded counter implemented in Algorithms 1. Lemma III.1. Operations CounterIncrement() and CounterRead () are wait-free. Proof: Let op r and op w denote a CounterRead and CounterIncrement instance respectively in E. The number of steps taken during op w is bounded since at most the process will attempt to set k switches during a call to CounterIncrement and there are no other loops or function calls in the CounterIncrement operation.

1 3 H

 13 Shared variables 2 switch j ∈ {0, 1} : for each j ∈ N, a 1-bit register that supports test&set and read primitives, initially all 0 [n] : an array of n integer pairs (val, sn) 4 Persistent local variables 5 last i ∈ N 0 : largest index of a switch accessed by i, initially 0 6 lcounter i : number of unannounced CounterIncrement by process i, initially 0 7 limit i : number of CounterIncrement that process i can perform locally, initially 1 8 sn i : number of switches set to 1 by process i, initially 0 9 l 0 : index of last switch accessed by the process i in the current set of switches, initially 1 Function CounterIncrement()

  j ← 1, . . . , n do 51 (val, sn) ← H[j] 52 if snhelp i [j] ≥ 2 then 53 p ← val mod k 54 q ← val k 55 return ReturnValue(p, q) 56 if last i = 0 then 57 return 0 58 return ReturnValue(p, q)

Figure 1 .

 1 Figure 1. Switches state for the proof of claim III.6. The dotted line indicate the q + 1th interval of consecutive switches.When p = 1, op does not distinguish between cases b.1) and b.2)

Algorithm 2 : 4 if p=0 then return 0; 5 else return k p ; 6 end 7 Function 9 M

 24579 A k-multiplicative-accurate mbounded max register 1 Shared variables M : ( log k (m -1) ) + 1 -bounded max register initially 0 2 Function Read() 3 p ←-M.read() Write(v) 8 p ←-log k v + 1; .write(p); 10 end

1 2 Theorem V. 2 .

 22 log k+1 (m-1) = Θ(log k m) from Lemma V.1 and[START_REF] Aspnes | Lower bounds for restricted-use objects[END_REF], Theorem 1 we have the following theorem: The worst-case step complexity of a k-multiplicative m-bounded max register isΩ min(log 2 (log k m), n) Lemma V.3. A k-multiplicative-accurate m-bounded counter is Θ(log k (m))-perturbable for k > 1.

r- 1 j=1 1 j=1 I j + 1 )

 111 I j . Besides the CounterIncrement() operation instances in γ, at least r-1 j=1 I j -(r -1) have finished, therefore setting I r = (k 2 -1) • r-1 j=1 I j + r implies that op n returns at least 1 k ( r-1 j=1 I j -(r -1) + I r ) = 1 k ( r-1 j=1 I j -(r -1) + (k 2 -1) • r-1 j=1 I j + r) = 1 k (k 2 •rwhich is greater tha k • r-1 j=1 I j as needed.

4 .

 4 3 and [5], Theorem 1, we prove the following TheoremTheoremV.The worst-case step complexity of a k-multiplicative m-bounded counter is Ω min(log 2 (log k m), n)

•

  Let op 1 and op 2 be two CounterRead operations. If both op 1 return normally the claim trivially holds from rule 2a and claim III.4. So consider that op 1 returns through the helping mechanism and let h 1 = q • k + p be the index of the switch read by op 1 at line 54, the last time before returning. According to rule 2b, op 1 is linearized immediately after opw h1 . Also, by Lemma III.3 and rule 2, op 2 is linearized after opw h1 . The claim follows since according our linearization rules, If several operations are ordered at the same position, they are ordered respecting their real time order.

• Consider that op 1 is a CounterIncrement and op 2 is a

Pun unintended.

ACKNOWLEDGMENT Alessia Milani and Corentin Travers are supported by ANR projects Descartes and FREDDA. Adnane Khattabi is supported by UMI Relax. Danny Hendler is supported in part by ISF grant 380/18.