Gaoang Liu
email: gaoang@ios.ac.cn

Xiuying Liu
email: liuxiuying@66nao.com

The Complexity of Weak Consistency

Weak consistency is a memory model that is frequently considered for shared memory systems. Its most distinguishable feature lies in a category of operations in two types: data operations and synchronization operations. For highly parallel shared memory systems, this model offers greater performance potential than strong models such as sequential consistency by permitting unconstrained optimization on updates propagation before synchronization is invoked. It captures the intuition that delaying updates produced by data operations before triggering a synchronization operation does not typically affect the program correctness. To formalize the connection between concrete executions and the corresponding specification, we propose in this work a new approach to define weak consistency. This formalization, defined in terms of distributed histories abstracted from concrete executions, provides an additional perception of the concept and facilitates automatic analysis of system behaviors. We then investigate the problems on verifying whether implementations have correctly implemented weak consistency. Specifically, we consider two problems: (1) the testing problem that checks whether one single execution is weakly consistent, a critical problem for designing efficient testing and bug hunting algorithms, and (2) the model checking problem that determines whether all executions of an implementation are weakly consistent. We show that the testing problem is NP-complete, even for finite processes and short programs. The model checking problem is proven to be undecidable.

Introduction

Many modern computer architectures and multi-core processors support shared memory in hardware, a design that facilitates fast access and provides user-friendly programming perspective to memory. A shared memory system permits concurrent accesses from multiple processes to a single shared address space. To avoid undesirable behaviors, memory consistency must be properly maintained. Informally, a memory consistency specifies the guarantees that a system makes on the value of read operations from the shared memory. Strong models such as atomic consistency (also known as linearizability) [START_REF] Herlihy | Linearizability -a correctness condition for concurrent objects[END_REF] and sequential consistency (SC) [START_REF] Lamport | How to make a multiprocessor computer that correctly executes multiprocess programs[END_REF] are intuitively composed but restrictive in performance as they would severely restrict the set of possible optimization, such as pipelining write accesses and caching write operations. Also, implementing these strong consistency criteria in message-passing system is very expensive. For better performance, in the past several decades many weaker consistency models, for example weak consistency (WC) [START_REF] Dubois | Memory access buffering in multiprocessors[END_REF], causal consistency (CC) [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF] and PRAM consistency [START_REF] Lipton | PRAM: A scalable shared memory[END_REF], have been proposed, explored and revised as various attempts.

Weak consistency was first proposed by Dubois et al. as weak ordering [START_REF] Dubois | Memory access buffering in multiprocessors[END_REF]. The motivation for designing this model is to tackle with the logical problems of memory accesses buffering stemmed from multiprocessor systems, especially in the cache-based systems or systems with a distributed global memory. Adve and Hill generalized weak consistency to the order strictly necessary for programmers with "SC for DRF" [START_REF] Adve | Weak ordering -a new definition[END_REF], which was re-specified and served as the cornerstone for Java memory model [START_REF] Manson | The Java memory model[END_REF] and C++ [START_REF] Boehm | Foundations of the c++ concurrency memory model[END_REF]. A weak consistent system distinguishes two types of variables: shared program variables that are visible to all processes; and synchronizing variables for concurrent executions synchronization. The latter can be recognized by instructions such as TEST AND SET (TAS), COMPARE AND SWAP (CAS), or special LOAD and STORE instructions. In the Java memory model, for example, to allow synchronization races but not data races, variables having potential to race must be tagged as synchronization, using keywords such as volatile or atomic. Programmers can also create synchronization locks implicitly with Java's monitor-like synchronized methods.

Based on the type of variable it accesses, an operation in a weakly consistent system is either a data operation and a synchronization operation. The latter works in a way similar to fence instructions, whose initiation suggests all previous references to the shared variables have completed and all future references have to wait. The idea of exploiting fence operations to achieve synchronized concurrency is also widely adopted by many commercial models. For example, the Power model [9] implemented by IBM PowerPC is similar in spirit to weak consistency by utilizing varieties of fences to synchronize concurrently executing processes. PowerPC uses an instruction called Hwsync to keep all writes in a consistent total order, it can also achieve sequentially consistent behaviors if Hwsync is used together with address dependencies and message passing [START_REF] Sarkar | Understanding power multiprocessors[END_REF]. In addition to PowerPC, another commercial example implementing a model that relies heavily on proper synchronization is ARM multiprocessor [START_REF] Alglave | The semantics of power and arm multiprocessor machine code[END_REF]. Similarly, ARM has multiple flavors of fences, including one data memory barrier that can order all memory accesses.

Generally, developing distributed implementations to satisfy a relaxed consistency model is very challenging because of the complicated issues related to communication. At different stages of development, the developers need to exploit different testing and verification techniques to validate the system they have built so far. This highlights the need for more research on the feasibility and efficiency of algorithms that are utilized during the development. We thus investigate in this paper two fundamental problems: (1) the testing problem that asks whether one given execution of an implementation is weakly consistent, and (2) the model checking problem (or verifying problem) that asks whether all the executions of an implementation are weakly consistent. The behaviors of implementations we consider in this study are restricted to the setting of read/write memory (RWM) abstraction, which is at the base of many distributed data structures used in practice.

We start by presenting in this work a new approach to formalize weak consistency in terms of distributed histories. This formalization associates a concrete execution of an implementation with its abstract description -a sequence that conforms to the specification for RWM, in our case. A specification is simply a characterization of admissible behaviors in the sequential setting. For a consistency model, a good characterization should, first of all, precisely captures the subtle behaviors of programs running under the model, and also be formal and convenient for developers to automatically analyze and verify their codes. Previous work [START_REF] Dubois | Memory access buffering in multiprocessors[END_REF][START_REF] Adve | Weak ordering -a new definition[END_REF] on weak consistency elaborated on the concept with great details, but the definitions presented in both work are either too informal or excessively convoluted to be directly applied to automatic verification. This makes our new formalization a necessity, with which we show the complexity of the testing problem is NP-complete. The result is achieved by reducing the serialization problem, a NP-complete problem for database transactions to a restricted version of the testing problem, TWC-read problem. We also investigate the problems with limited accesses per process and limited processes in an instance. Both problems are proven to be NP-complete, even when the access number is limited to two and the process number to three. For the TWC-read problem restricted to two processes, we prove there exists a polynomial algorithm. We then prove that the model checking problem is undecidable by a reduction from the Post Corresponding Problem (PCP). The idea is to relate each PCP instance to a WC implementation, such that the instance has a valid witness exactly when the implementation is weakly consistent.

The remainder of this paper is organized as follows. Section 2 presents the notion of distributed history and the specification for read/write memory. Section 3 briefly reviews the intuition behind WC and then shows how to formalize this concept. We present in section 4 and section 5 the complexity results for the testing problem. The decidability result of the model checking problem is proved in Section 6. Section 7 discusses the related work. Finally, section 8 concludes the paper.

Preliminaries

2.1 Sets, Relations and Labeled Posts.

Given a set E and a relation R ⊆ E × E, we denote by e 1 ≺ R e 2 the fact that (e 1 , e 2 ) ∈ R. We write (R) + to denote the transitive closure of R. A relation is a strict partial order if it is transitive and irreflexive.

A poset is a pair (E, ≺) where ≺ is a strict partial order. Given a set Σ, a Σ labeled poset ρ is a tuple (E, ≺, ι) where (E, ≺) is a poset and ι : E → Σ is the labeling function.

We introduce a relation on labeled posets, denoted . Let σ = (E, ≺, ι), σ = (E, ≺ , ι ) be two posets labeled by the same set Σ. We denote by σ σ the fact that σ imposes less constraints on operations in E. Formally, σ σ if ≺⊆≺ and ι = ι , i.e., for all operation e ∈ E, ι(e) = ι (e).

Histories and Specifications

A distributed system is a composition of a set of processes/participants invoking methods on shared objects (registers, queues, etc.). An object implements a programming interface (API) defined by a set of methods M with input and output from a data domain D. The behaviors of a system can be characterized by a set of executions. Each execution is a labeled poset consist of a collection of events, representing operation invocations by different participants, and a relation on events, describing abstractly how the system processes the corresponding operations. The characterization of distributed executions are what we call distributed histories. Formally, Definition 1. A distributed history is a poset H = {E, ≺ PO , ι} labeled by M × D × D, where E is a countable set of events; ≺ PO ⊂ (E × E) is a strict partial order called program order; and ι : E → (M × D × D) is a labeling function.

The labeling function ι maps each event to its corresponding operation that invoke a method from M. To model events that return no value, we use a value ⊥∈ D, which is often omitted for better readability.

Example 1. For the read/write memory, M = {r, w} is the set of operations reading and writing variables. Let the variables set be V, the domain D is therefore (V × (N {⊥})) V N {⊥}. A labeling function ι maps each write event e w to a tuple w, (v, n), ⊥ (abbreviated as w(v, n)) and each read e r to r, (v, ⊥), n (r(v)/n).

The consistency of shared objects is a criterion that links the distributed executions to a particular specification, which characterizes the admissible behaviors for a program that uses the objects. For an object defined by a method set M and data domain D, the specification S can be specified by a set of sequences labeled by M × D × D.

Generally, specifications can be defined with posets of events (as in a way used in [START_REF] Bouajjani | Verifying eventual consistency of optimistic replication systems[END_REF] instead of sequences of events that are total ordered. The former provides a more general and precise way to model conflict resolution policies. In this work, however, we focus on the read/write memory, as illustrated in Example 1. A sequential specification is enough to meet our needs for the modeling purpose. We define the specification S r/w as a set of sequences where each value read matches the most recent write. Formally, it is the smallest set of sequences by inductively adopting the following rules:

-∈ S r/w , -σ • w(v, d) ∈ S r/w if σ ∈ S r/w , -σ • r(v, 0) ∈ S r/w if σ ∈ S r/w and σ contains no write on v, -σ • r(v, d) ∈ S r/w if σ ∈ S r/w and the last write on v in σ is w(v, d),
where v ∈ V, d ∈ D and is the empty sequence.

3 Weak Consistency

Weak Consistency: Informal Description

Many consistency models have been proposed to specify shared memory. Strong consistency models such as SC [START_REF] Lamport | How to make a multiprocessor computer that correctly executes multiprocess programs[END_REF] and linearizability [START_REF] Herlihy | Linearizability -a correctness condition for concurrent objects[END_REF] are intuitively composed but restrictive in performance as they would severely restrict possible optimization such as pipelining write accesses. Besides, implementing strong consistency criteria in message-passing systems are strikingly expensive. For example, the duration of reads or writes in SC systems has to be linear with the latency of the network [START_REF] Lipton | PRAM: A scalable shared memory[END_REF]. To increase efficiency, researchers explored a variety of weak consistency criteria [START_REF] Dubois | Memory access buffering in multiprocessors[END_REF][START_REF] Goodman | Cache consistency and sequential consistency[END_REF][START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF][START_REF] Lipton | PRAM: A scalable shared memory[END_REF].

Among these consistency models, WC is distinguishable from many of its counterparts by its category of memory accesses. Based on the type of accesses, it imposes different ordering constraints. For example, in the case of data operations, buffered requests (to memory) may be allowed to pass each other in the buffer. This is referred to as jockeying [START_REF] Dubois | Memory access buffering in multiprocessors[END_REF], which is often permitted between requests for different memory locations. On the other hand, the synchronization operations are requested to be strongly ordered [START_REF] Dubois | Memory access buffering in multiprocessors[END_REF], and the jockeying with data operations is forbidden. The purpose of synchronization operations is, as the name suggests, to sync updates between different processes by propagating local updates outward and bring in all updates from other processes. Before a subsequent synchronization is initiated, the propagation of local updates can be arbitrarily postponed. Informally, weak consistency ensures that reordering memory operations to shared data between synchronization operations does not typically affect program correctness.

Dubois et al. presented in [START_REF] Dubois | Memory access buffering in multiprocessors[END_REF] the first description of WC by enforcing on storage accesses the following constraints : Definition 2. In a multiprocessor system, storage accesses are weakly ordered if (1) accesses to synchronizing variables are strongly ordered, (2) no access to a synchronizing variable is allowed to be performed until all previous writes have completed everywhere, and (3) no data access (read or write operation) is allowed to be performed until all previous accesses to synchronizing variables have been performed everywhere.

The idea of supporting jockeying to add efficiency has also been exploited by many other models, such as the "write to read" relaxation, which corresponds to the Total Store Order (TSO) model. Apart from jockeying, another important feature of WC is that it enforces consistency on a group of operations, rather than on individual reads or writes. For memory accesses to different locations, absent of any barriers or dependencies, the behavior can be unconstrained. This is best illustrated by the following example.

Example 2. History (a) in Figure 3.1 is weakly consistent while (b) is not. Because of jockeying, it is possible for P 3 in (a) to read the initial value of x even when a previous read on y returns the latest value. In (b), however, the sync operation forces out all previous updates to P 2 , making the read r(x, 0) impossible.

Weak Consistency: A Formal Definition

We now present an approach to characterize concrete executions of concurrent systems employing a weakly consistent model. This characterization links each execution to a set of sequences, among which there is at least one can provide a reasonable explanation as to why the execution is weakly consistent.

Given a history H with an event set E, we denote by E S the set of synchronization events and E D the set of data events. Two events from different processes can be ordered only if there exists an intervening synchronization between them. To capture this property, we introduce happen-before relations for events in any history. Two types of relation are considered: program order ≺ PO , and synchronization order ≺ SO . Formally, let e u and e v be any two operations occurring in H. Then:

e u ≺ PO e v iff e u occurs before e v in the same process.

e u ≺ SO e v iff e u , e v ∈ E S ∧ var(e u ) = var(e v ) and e u is performed before e v , where var(e) ∈ V is the variable accessed by e. The concept of performed is borrowed from [START_REF] Adve | Weak ordering -a new definition[END_REF], where a read is said to be performed at a point in time when no subsequent write, from the same or another process, can affect the value returned. Similarly, a write is said to be performed when all subsequent reads return the written value until another write to the same memory location is performed. For a synchronization operation, it is performed also means all preceding updates of data operations are propagated outward.

Definition 3 (Weak Order).

A weak order ≺ WO of a history H is the irreflexive transitive closure of program order and synchronization order, that is ≺ WO = (≺ PO ∪ ≺ SO ) + . The set of events happening before e w.r.t. the ≺ WO is denoted by e = {e ∈ E : e ≺ WO e}.

Intuitively, e is the weak past of e, i.e., the set of operations whose effects are visible to e. To associate any weakly consistent history to the sequential specification, we need to define a way to explain how events on a history are generated. For example, it should explain which write is responsible for a read that is accessing the same variable. This is achieved by defining a function, called observation function below, that links each event to an event set, which, if considered together with ≺ WO , will be sufficient to explain why the history is admissible by the specification S r/w . Definition 4. Given a history H, a function τ : E → 2 E is an observation function on E, if ∀e ∈ E, τ (e) = {e} ∪ e ∪ C e for some set C e ⊆ E whose elements are concurrent events of e. The set τ (e) is called an observation set of e.

The observation set τ (e) is acctually a snapshot of updates observed by e and, hence, should not deviate from the constraints imposed by WC. Apart from the constraints required by ≺ WO , it should also respect what we call update inheritance -updates observed by one event are inherited to its successors. Specifically, if an event e observes updates happened before a synchronization, then all events observed e should too have observed those updates. Formally, for two events e u , e v ∈ E, if Definition 5. A history H is weakly consistent with respect to S r/w if there exists an OCF τ such that for any e ∈ E, there exists a sequence σ e ∈ S r/w such that (τ (e), ≺ WO , ι) σ e .

Example 3. To illustrate, the history in Figure 3.1(b) has no OCF τ for its event set. For otherwise we have e w(x,1) ∈ τ (e SYNC ) and τ (e SYNC ) ⊆ τ (e r(x,1) ), and by the condition (*) the observation set τ (e r(x,0) ) will contain e w(x,1) , implying the update on x is observable to e r(x,0) , whose return value should thus be 1 instead of 0.

The Testing Problem of Weak Consistency

We first investigate the testing problem of weak consistency (TWC), which is relevant for instance in the context of testing a given distributed object. We prove that this problem is NP-complete. This is achieved by a reduction from the serializability problem for database histories. The membership in NP can be easily proved, following from the fact that, for any given instance (history) H, one can guess an observation function τ , and a sequence σ e ∈ S r/w for each event e, and then check in polynomial time whether τ is an OCF and the relation in Definition 5 holds.

To prove the NP-hardness, we first define a restricted version of the TWC problem and reduce the restricted problem to the serializability problem. We consider the case in which for each read, it is known precisely which write was responsible for the value read. We call this the TWC-read problem. The function mapping each read to the responsible write is called a read-mapping.

The serializability problem for database transactions is one exploring the existence of a schedule that is equivalent to one that executes the transactions serially in some order. One major type of the problem is view serializability [START_REF] Papadimitriou | The theory of database concurrency control[END_REF], in which we are given a history, a total order on a set of reads and writes, where each read or write is associated with a particular transaction. The problem asks if there is a total order on the transactions that preserves the reads-from mapping of the original history. The view serializability problem is NP-complete [START_REF] Papadimitriou | The theory of database concurrency control[END_REF]. TWC-read is a problem more general than view serializability by permitting solutions in which the accesses for a processor (transaction) are in order but may not be consecutive. To illustrate, the instance in Figure 4.1 is a "yes" instance for TWC-read problem, but a "no" instance for view serializability, because both P = P 1 P 2 and P = P 2 P 1 have reads-from violations.

Lemma 1. The TWC-read problem is NP-complete.

P1 : w(x, 0), w(y, 1), r(x, 1) P2 : r(y, 1), w(x, 1) Fig. 4.1. A "yes" instance of the TWC-read problem Proof. Given H, an instance of a view serializability problem, we construct an instance of TWCread as follows. Let v be a variable not accessed by any operation in H, and # α a synchronization operation on a variable α. Let P i be the sequence of operations in H for transaction i (i ∈ {1, .., n}), where each write in a transaction is assigned a unique value to write, and each read is assigned the value of the closest previous write to the same address in H.

For all transactions i, let

P i = w(v, i)# α P i # α r(v, i).
Our TWC-read instance is H = i∈{1,..,n} P i . The intervening # α guarantees the update to v is observed by other transactions before P i initiates and updates from other transactions were brought in before reading v. This construction ensures that for each P i once the write w(v, i) starts, the remainder (i.e. # α P i # α r(v, i)) must be scheduled consecutively. If two transactions P i , P j interleaves, then at least one of them, say P i , will return for its last read a value other than i, and thus violates the read-from relation. It follows that H is in TWC-read if and only if H is view serializable.

The above result on TWC-read implies that the general TWC problem is at least NP-hard, since the problem is also in P, we have the following theory.

Theorem 1. Checking whether a distributed history H is weakly consistent with respect to S r/w is NP-complete.

Restricted TWC Problems

The previous section shows that the TWC problem is generally NP-complete. In this section, we investigate two restricted versions of TWC that consider only instances with limited number of accesses or processes. Such problems are interesting because many multiprocessors have only a small number of processors, e.g., 8, 16 or 32; and when it comes to testing, the size of instances are usually small.

We show that these restricted problems remain NP-complete, even when the number of accesses per process is limited to two and the number of processes to three. These results imply the testing problem of weak consistency is intrinsically hard. For a very rare case of this problem, in which only two processes are involved and a read-mapping is provided, we prove there exists a polynomial algorithm.

Restricting the number of accesses

We now investigate the restricted problem in which each process has at most two data operations and each data variable is written to at most twice. We show this problem is NP-complete.

The result is generated from a reduction from 3SAT. Let F denote a 3SAT instance. For a literal l i in a clause, we use the notation B(l i ) to represent T (True) if l i is a positive literal (i.e., a variable), and F (False) otherwise. We need to simulate the logical connectives (i.e., an OR and an AND), as well as an assignment of variables that remains in effect until the formula is evaluated. We observe that (1) a read must wait for its responsible write to occur, (2) the second access at a process must wait for the first. Then the assignment to v i can be simulated as follows (each column represents a sequence):

w(v i , T ) r(x, 1) w(v i , F ) r(x, 1) # α # α r(v i , T ) r(v i , F ),
where x is initially 0 and # α represents a synchronization operation on variable α. A single write w(x, 1) (shown below) occurs only after the satisfiability of F has been simulated. Then one and only one write to v i occurs before w(x, 1), ensuring that the initial assignment to each v i must remain in effect until the satisfiability of F has been simulated. An OR is simulated by separating the literals of a clause into three reads, whose executions determine the truth value of that clause. For each clause, C i = l p ∨ l q ∨ l r , we have four sequences:

r(l p , B(l p )) r(l q , B(l q )) r(l r , B(l r )) r(d i , T ) w(d i , T ) w(d i , T ) w(c i , T ) w(c i , T )
By the two observations above, this ensures that C i is not set to T unless clause i is satisfied by the guessed truth assignment.

The AND of the clauses can be easily simulated by a sequence r(c 1 , T ), r(c 2 , T ), ..., r(c m , T ), w(x, 1). But this sequence involves m + 1 > 2 data operations. In order to have only two accesses per process, we separate this sequence into m + 1 sequence: a single write w(x, 1) and m sequences ending with a read r(x, 0):

w(x, 1) r(c 1 , T ) r(c 2 , T ) ... r(c m , T ) # α # α ... # α r(x, 0) r(x, 0) ... r(x, 0)
This ensures that x is not set to 1 unless all clauses have been satisfied by the guessed assignment.

Lemma 2. Let F be an instance of 3SAT, and W the instance of the TWC problem constructed as described above. Then W is weakly consistent if and only if F is satisfiable.

Proof (sketch). Assume there is a satisfying assignment for F. We can construct a corresponding schedule for W such that it can be sequentially ordered by that schedule. That is W is sequentially consistent and, hence, weakly consistent. Conversely, if W is weakly consistent, the first value written to each variable v i forms the satisfying assignment. (A full proof is deferred to Appendix A.1). By this result, the following theory is straightforward.

Theorem 2. The TWC problem, restricted to instance in which each sequence contains at most two data operations and each data variable occurs in at most two write operations, is NP-complete.

Restricting the number of processes

We have shown that the TWC problem is NP-complete with O(n) processes (n is the number of data variables). In this problem, the number of processes per instance grows proportionally with the number of variables, this raises another question: what is the complexity for TWC problems with a fixed small number of processes. This question is answered by the theory below, showing that the problem remains NP-complete even when the number of processes per instance is limited to three.

To simulate an instance of 3SAT, the proof of Lemma 2 constructs a disjoint set of processes for each variable. This strategy can not be transferred here as the number of processes is limited.

We consider to analyze the problem with a reduction from one-in-three 3SAT problem, a variant of 3SAT where the input instance is the same, but the question is to determine whether there exists a satisfying assignment so that exactly one literal in each clause is set to true. This problem is known to be NP-complete. A monotone version of this problem, positive one-in-three 3SAT, where each clause contains only positive literals, remains NP-complete. Our strategy is, for a given positive one-in-three 3SAT instance F, we construct an instance W of the TWC problem, using only three processes, such that F has a satisfying assignment exactly when W is weakly consistent. The TWC instance W for each F is depicted in Figure 5.1.

The synchronization parts (as illustrated by # in the figure) separate the construction into m + 1 stages. The key idea behind this construction is to use the value at the end of the (INIT) stage as the assignment. The history is weakly consistent if every stage is weakly consistent. For each clause, each of the three processes is satisfied by a particular assignment. The subtle part is the writes highlighted in blue. Once a way of satisfying a clause is settled, the writes free up the other two processes by negating variables, and then return all variables to their initial setting (for the next stage). Conversely, for any assignment of F that does not satisfy this clause, there is no way to prove the weak consistency of this stage. Theorem 3. The TWC problem restricted to three processes is NP-complete.

P1 P2 P3 w(v1, F ) ... w(vn, F ) w(u, 1) #α r(u, 3) r(vx 1 , T ) r(vy 1 , F ) r(vz 1 , F ) w(vx 1 , F ) w(vy 1 , T ) ... ... ... w(v1, T ) ... w(vn, T ) w(u, 2) #α r(u, 3) r(vy 1 , T ) r(vz 1 , F ) r(vx 1 , F ) w(vy 1 , F ) w(vz 1 , T ) ... ... ... r(u, 1) r(u, 2) #α w(u, 3) r(vz 1 , T ) r(vx 1 , F ) r(vy 1 , F ) w(vz 1 , F ) w(vx 1 , T ) ... ... ... (INIT) (C1) (#) (#) (Cm)
In the above reduction, each clause of the 3SAT instance requires at least three processes for the simulation procedure. This is the simplest reduction we are aware of, leaving open the TWC problem restricted to two processes. Nevertheless, we prove below there is a polynomial algorithm for TWC-read problem restricted to two processes.

TWC-read problem with two processes is in P

For an instance H of two-processes TWC-read problem, every read in H knows precisely its responsible write, which means if two write w(v, d 1 ), w(v, d 2 ) are accessing the same location v, then d 1 and d 2 must differ. To sovle the two processes TWC-read problem, we begin by constructing an OCF, τ , capturing all events been observed by each access. The instance H is in TWC-read exactly when there exists a witness OCF that respects certain constraints, and involves none of the anomalous forms (as defined in the proof for Lemma 3). Constructing this OCF and checking whether certain conditions are met can be done in polynomial time. That is, there is a polynomial algorithm to solve this problem in two steps: [START_REF] Herlihy | Linearizability -a correctness condition for concurrent objects[END_REF] constructing for an instance a witness OCF, (2) checking whether this OCF meets required conditions. The proof for the following lemma is deferred to Appendix A.3. Lemma 3. The TWC-read problem restricted to two processes is in P.

Undecidability of Verifying Weak Consistency

We consider in this section the model checking problem of weak consistency, i.e., the problem of deciding whether a given implementation has correctly implemented weak consistency. For systems maintaining memory coherence, weak consistency implies sequential consistency if every data operation is synchronized by the same sync variable [START_REF] Gharachorloo | Memory consistency models for shared-memory multiprocessors[END_REF]. This implies the model checking problem of WC because the same problem of SC is generally undecidable [START_REF] Alur | Model-checking of correctness conditions for concurrent objects[END_REF]. However, here we offer another proof, which may provide some additional insight into the reason why verifying weak consistency is undecidable. For the proof, we assume the implementations are regular and specification is restricted to S r/w with a fixed number of variables whose domain sizes are fixed, such that this specification corresponds to a particular regular language. We then reduce PCP to the model checking problem. Definition 6. Let Σ be an alphabet with at least two letters. An instance of PCP is given by two sequences U = {u 1 , ..., u n } and V = {v 1 , ..., v n } of words over Σ. The problem is to determine whether there is a sequence (i 1 , ..., i p ) with i j ∈ {1, ..., n} and p > 1 such that

u i1 • • • u ip = v i1 • • • v ip . Theorem 4. [17] The Post Correspondence Problem is undecidable. A pair of words u, v ∈ Σ * × Σ * is a witness of a PCP instance P if they can be decomposed into u = u i1 • u i2 • • • u ip and v = v i1 • v i2 • • • v ip such that u i = U [i] and v i = V [i].
If there is also u = v, we call such a pair a valid witness, which corresponds to a positive answer to the PCP problem. Our goal is to build an implementation I that is not weakly consistent with respect to the read/write memory if and only if the instance P has a valid witness. That is the implementation I produces, for each pair of words u, v , an execution H uv that is not weakly consistent if and only if u, v forms a valid witness. The construction of each history H uv relies on ten processes and seven variables (six data variable and one synchronization variable). To conserve space, details of proof are given in Appendix A.4.

Theorem 5. Given an implementation I as a regular language, checking whether all executions of I are weakly consistent with respect to S r/w is undecidable.

For the testing problem of relaxed memory consistency models, Wei et al. [START_REF] Wei | Verifying pram consistency over read/write traces of data replicas[END_REF] proved that complexity of testing PRAM consistency is NP-complete. Bouajjani et al. [START_REF] Bouajjani | On verifying causal consistency[END_REF] studied the complexity of verifying causal consistency for one history. It was proved that the problem is NP-complete for all the three variations of CC (causal consistency, causal convergence and causal memory). A recent work by Furbach et al. [START_REF] Furbach | Memory-model-aware testing: A unified complexity analysis[END_REF] showed that the testing problem for any criterion weaker than sequential consistency and stronger than slow consistency is NP-complete. This range covers many relaxed memory consistency models, including (a weaker variation of) CC, TSO, PSO and PRAM consistency, but it does not cover WC. It is easy to construct executions that conform to WC but violate slow consistency.

The model checking problem for linearizability, quasi-linearizability and SC have been extensively studied. It was shown that verifying linearizability is EXPSPACE-complete when the number of processes is bounded and undecidable otherwise [START_REF] Bouajjani | Verifying concurrent programs against sequential specifications[END_REF]. Alur et al. [START_REF] Alur | Model-checking of correctness conditions for concurrent objects[END_REF] proved that checking sequential consistency is in general undecidable. The same conclusion holds for systems with only four objects. Wang et al. [START_REF] Wang | Quasi-linearizability is undecidable[END_REF] studied the model checking problem of quasi-linearizability and proved that it is undecidable. For consistency criteria weaker than sequential consistency, eventual consistency has been shown to be decidable [START_REF] Bouajjani | Verifying eventual consistency of optimistic replication systems[END_REF], and causal consistency was proved to be undecidable [START_REF] Bouajjani | On verifying causal consistency[END_REF] in general.

The method we used to formalize weak consistency in terms of distributed histories is inspired by the work of [START_REF] Perrin | Causal consistency: beyond memory[END_REF], which extends the definition of CC to all abstract data types. Their work uses transition systems to specify sequentially abstract data types, which is modeled as transducers, a model that is very similar to Mealy machines [START_REF] Mealy | A method for synthesizing sequential circuits[END_REF]. Their approach for CC, however, does not easily transfer here. For WC, we have to consider the different roles played by data and synchronization operations, while causal consistency does not distinguish memory access categories.

Conclusion

This paper explores the complexity of deciding whether an execution of a shared memory system is weakly consistent. We prove that the TWC problem is NP-complete, even for systems with only three processes or programs in which each process is permitted to have only two memory (data) accesses. We show the TWC-read problem is also NP-complete, which implies tagging each read with the identity of the responsible write does not reduce the complexity. However, for TWC-read, if we restrict the process number to two, then a polynomial algorithm exists.

A new approach is proposed to formalize weak consistency. This new formalization, unlike those from previous work [START_REF] Adve | Weak ordering -a new definition[END_REF][START_REF] Dubois | Memory access buffering in multiprocessors[END_REF], is given in terms of distributed histories abstracted from concrete executions, making possible a direct application of this formalization into automatic verification. We have also explored the model checking problem of weak consistency. Generally, deciding whether an implementation has correctly implemented the read/write memory is undecidable, even when the implementation and specification are both regular. These results on TWC and the model checking problem suggest that reasoning about weak consistency is intrinsically hard.

Although the read-mapping does not help with reducing the complexity, it would be interesting to investigate the TWC and model checking problem for implementations under certain constraints, such as data independence, a property ensuring the system behaviors are independent to particular data values stored at particular memory locations. These investigations remain future work. Moreover, as release consistency [START_REF] Gharachorloo | Memory consistency and event ordering in scalable shared-memory multiprocessors[END_REF] is a consistency model that refines weak consistency by slitting synchronization into two types, the results presented in this work may well be applicable (with minor adaptations) to release consistency. denote a sequence such that σ ∈ H| τ (o)∩D ∩ S r/w , we write σ b = σ| τ b (o) as the sub sequence of σ restricted to τ b (o). The sub-sequence σ b respects the weak order since σ does, then σ b ∈ H| τ b (o)∩D . Since every read r in σ b has a responsible write that happens before r, then σ b is LateWrite free. Also, as σ is ReadStaleUpdate free, then σ b is ReadStaleUpdate free (otherwise there is at least one read in σ that returns a stale value), which means σ b ∈ S r/w . Therefore,

σ b ∈ H| τ b (o)∩D ∩ S r/w , that is Υ (τ b ) = 1.
A. [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF] The Decidability of Verifying Weak Consistency Theorem A.2. Given an implementation I as a regular language, checking whether all executions of I are weakly consistent with respect to S r/w is undecidable.

Proof. Let Σ = {a, b} and P be an instance of PCP. The pair of sequences that defines P is:

U = {u 1 , ..., u n }, V = {v 1 , ..., v n }. For a letter v i ∈ V , we use v i to denote b if v i = a, and a if v i = b. We use the term ζ(ξ(x, d))
to denote a sequence of operations w(x, 0) • ξ(x, d) • w(x S , #) for a x ∈ X and d = 0, where x S is a synchronization variable, ξ is either a read or a write operation, and X is a finite set of variables. The synchronization used here ensures that at each time a process executes ζ(ξ(x, d)), all local updates of the current history are propagated outward and updates occurred elsewhere are brought in, in this way all processes are synchronized.

Let u, v be a valid witness of P. This history H uv is constructed in a way as illustrated in Figure A.4. For the sake of convenience, we will use [e] to refer to the name of the event that follows it in the history. We call a read operation r(x, d) reads from a write w(x, d), when w(x, d) is the value provider. The integers m, n, k and |v| used in the history have the relation: m + n + k = 2|v|, where |v| is the length of sequence the v. We now prove the following equivalence:

(1) H uv is weakly consistent; (2) u = v.

(1 ⇒ 2) Assume H uv is weakly consistent. Assume by contradiction that u = v. Thus, |u| = |v| and for all i ∈ {1, ..., |v|}, u i = v i . We prove that there is at least one [v i0 ] that has to read from [u i0 ]. Then, since u i = v i for all i ∈ {1, .., |v|}, [u i0 ] can not be the value provider for [v i0 ].

In order to return 1 for the read operation [r T ], one of the three write operations [w i T ](i = 1, 2, 3) has to happen before [r T ]. Assume the value provider is [w 1 T ], then [h 1 ] is overwritten by [v 0 ] since each synchronization operation works as a fence. Now there are 2|v| + 3 read operations on object o in process p v while only 2|v| + 2 writes are available on the writer processes and helper processes. This implies there is at least one read operation [v i ] will have to read from [u j ] on p u for some j ∈ {1, ..., |u|}. We now show that it can only read from [u i ] but not from [u j ] for i = j.

We start by proving that the read operation in [t i ] can only read value from [s i ]. To accomplish this, we need to prove that [t i ] can not read value from [z j ] in process p aux2 . Observe that [w q ] (and all the subsequent events) has to wait until [v |v|+3 ] is globally performed, otherwise the value written on x q will be visible to p v and event [r q ] is impossible. Assume by contradiction that there is a [t i ] reading value from [z j ] for some j, then [r q ] (and all preceding operations on p v ) will certainly happen before Similarly, we can prove that the read operation in [f i ] can only read value from [e i ]. Now, assume that [v i ] uses a write [u j ] with i < j, which means its following [f i ] will have to use [e k ] for j ≤ k, which is impossible based on the previously demonstrated property. Similarly, if [v i ] uses a write [u j ] with i > j, then [t j ] need to read value from [s k ] for k > i, which is also impossible. This concludes the proof that there is at least one read operation [v i0 ] that has to read from [u i0 ], but not from [u j ] for i 0 = j.

(2 ⇒ 1) To prove that the converse is true, we need to consider three cases: |u| = |v|, |u| < |v| and |u| > |v|, and prove that H uv is weakly consistent under all cases. And in order to show that H uv is weakly consistent, we need to guarantee that every read operation has a reasonable explanation for the value it returns. ]. This case is different with the above one in the way that the process p u itself can not provide enough write operations on x A that are needed by the read operations in [f i ] on process p v . However, this can be assisted by process p aux1 . It causes no trouble for the read operation [r p ] because the process p H1 can wait until all operations on p u are performed.

The value returned by each read operation can be explained in the following way:

- Now we have established the equivalence between (non) weak consistency of a history and the validity of its corresponding witness. The last thing is to describe how to define I as a regular language, such that I produces, for each witness u, v , an execution whose history is H uv .

For an execution of I, the helper processes execute their operations, which is followed by the auxiliary processes executing their first operations. The process p v then chooses nondeterministically a pair u i , v i from the instance P. Then p v and p u execute operations based on the symbols on v i and u i , the writer and auxiliary processes behave accordingly. For example, if u i , v i = a, b , then p u do operations [u i , e i , t i ], p v do operations [v j , w j , f j , s j ], the writer process p a does a write operation w(0, a). The auxiliary process do an operation [y i ], [z i ], respectively. This procedure may repeat for an arbitrary times, depending on the structures of u and v.

At the time that the above procedure terminates, p u , p v and the auxiliary processes will execute their rest operations, as detailed in Figure A.4. By the structure of operations [t i ] and [f i ], all processes synchronize after each choice of witness u i , v i (actually, they synchronize after every symbol), I thus can be described by a regular language.

Fig. 3 . 1 .

 31 Fig. 3.1. The visualization of WC, where SYNC represents a synchronization operation on a variable other than x and y. Initially, x = y = 0.

  (a) e u ∈ τ (e v ) and at least one of e u , e v belongs to E S , or (b) e u ∈ E S ∧ ∃e w .(e w ∈ τ (e v ) ∧ e u ∈ τ (e w )), (*) then τ (e u ) ⊆ τ (e v ). We call such a function a observation closed function (OCF).

Fig. 5 . 1 .

 51 Fig. 5.1. Transfroming an instance of positive one-in-three 3SAT to an instance of TWC. The 3SAT instance contains n variables v1, ..., vn and m clauses: C1, ..., Cm, where Ci = (vx i ∨ vy i ∨ vz i ) for some xi, yi, zi ∈ [1..n].

  [t i ], [r p ] and [w p ]. By the definition of ζ(r(x A , 1)), each read operation involved in [f i ] needs a unique value provider because all previous write operations on x A is overwritten by a leading write in ζ(•), then the write operations that are available for read operations in [f i ] are insufficient. Therefore the read operation in [t i ] can not read value from [z j ]. Notice that p u contains |u| + 1 read operations on x B , and p v contains |u| + 1 write operations on x B . Each read operation in [t i ] exactly corresponds to [s i ].

Case 1 :

 1 |u| = |v| but u i0 = v i0 for some i 0 ∈ {1, .., |v|}. Becauseu i0 = v i0 implies u i0 = v i0 , the write operation [u i0 ] can provide value to [v i0 ]. Also, [w 3 T ] provides value to [r T ], [h 1 ] to [v |v|+1 ], [h 2 ] to [v |v|+2 ], and [c k ] to [v |v|+3 ]. The remaining read operation [v i ], [w i ] ([v i0 ] excluded) can be explained by executing {[a 1 ], ..., [a m ], [b 1 ], ..., [b n ], [c 1 ], ..., [c k-1 ]}sequentially. Finally, the operations [e i ] provides value to the read operation in [f i ], and [s i ] to the read operation in [t i ] for i ∈ {1, ..., |v| + 1}. Case 2: |u| < |v|. The write operation [u |u|+1 ] can provide value to [v |u|+1

  [e i ] provides value to the read operation in [fi ] for i ∈ {1, ..., |u|} -[s i ] provides value to [t i ] for i ∈ {1, ..., |u|} -[y i ] provides value to [t i+|u| ] for i ∈ {1, ..., |v| -|u|} -[a i ] provides value to to [v i ] for i ∈ {1, ..., |v|} ∧ v i = a -[b i ] provides value to to [v i ] for i ∈ {1, ..., |v|} ∧ v i = b -[u |u|+1 ] provides value to [v |u|+1 ] -[c i ] provides value to to [w i ] for i ∈ {1, ..., |v|, |v| + 3}\{|u| + 1} -[h 1 ] provides value to [v |v|+1 ] -[h 2 ] provides value to [v |v|+2 ]Case 3: |u| > |v|. Similar to the previous case except that [u |u|+1 ] is used to provide values to [v |v|+3 ].

A Appendix

A.1 TWC problem with restricted accesses Lemma A.1. Let F be an instance of 3SAT, and W the instance of the TWC problem constructed as described above. Then W is weakly consistent if and only if F is satisfiable.

Proof (sketch). We show that if F is satisfiable, we can construct a schedule by which W is sequentially consistent, which implies W is weakly consistent. Conversely, if W is weakly consistent, the first value written to each variable v i is the satisfying assignment.

Assume, without loss of generality, F is satisfiable with an assignment A in which every variable v i is set to be true. We construct a schedule S as follows: Firstly, the writes w(v i , T ) are executed, which are followed by the reads of positive literals r(l i , B(l i )) in each clause C j , while the reads of negative literals and the following writes on d i and c i are postponed to the end. This ensures at least one w(c i , T ) occurs before each pair of r(c i , T ) and r(x, 0). The write w(x, 1) is then executed, which is followed by the sequences with r(v i , T ) (the sequence order does not matter). When every r(v i , T ) is executed, the sequences with r(v i , F ) start to execute. It is not hard to prove that W can be sequentially ordered by the schedule S described above, which implies W is weakly consistent. Now assume W is weakly consistent. The synchronization # α before r(x, 0) ensures w(x, 1) can not occur until all reads r(c i , T ) are done. Since w(x, 1) is the only source for r(x, 1), then one and only one write to v i occurs before w(x, 1) and before each r(c i , T ). Then the first value written to each v i constitutes the satisfying assignment. Take the clause C i = l p ∨ l q ∨ l r for example. Because w(d i , T ) is the only source for each read r(v i , T ), and in order for w(d i , T ) to happen, at least one of the three reads r(l p , B(l p )), r(l q , B(l q )), r(l r , B(l r )) will have to occur before w(d i , T ) and thus before r(d i , T ). Assume it is r(l q , B(l q )) where l q = ¬v k , then assign v k to be false (i.e., by executing w(v k , F )) will make the clause C i true. Other clauses can be analyzed along the same line.

A.2 TWC problem with restricted processes

Theorem A.1. The TWC problem restricted to three processes is NP-complete.

Proof. We show that the instance of TWC in Figure 5.1 is weakly consistent exactly when its corresponding one-in-three 3SAT instance F has a satisfying assignment. The sufficiency of this theorem can be easily validated. Assume F has a satisfying assignment, and C 1 is satisfied with (v x1 , v y1 , v z1 ) = (T, F, F ). During the (C 1 ) stage of the construction, process P 1 executes first, which is followed by P 2 and then P 3 . This forms a sequential schedule for the operations during this stage, therefore (C 1 ) is weakly consistent. As each stage ends with restoring all variables (v x1 , v y1 , v z1 ) to their original values. Then the stage (C 2 ), as well as (C 3 , ..., C m ), can be analyzed along the same line.

For the necessity, assume W is weakly consistent. An immediate inference is that every (sequence) segment on the stage C i is weakly consistent. At the start of each stage C i , only one variable is true, while the other two be false. This is because only in this way, there is a schedule by which all of the three processes can proceed. The variable values on each stage will be restored to their initial values when the stage ends. Thus, we construct an assignment A as one in which the value of the literals be the value at the end of stage (INIT). Obviously, this assignment A is the desired assignment for the instance F.

A.3 TWC-read problem restricted to two processes

Lemma A.2. The TWC-read problem restricted to two processes is in P.

Proof. We now describe a polynomial algorithm that determines whether a given instance H is weakly consistent. We assume: (a) every read in H has a responsible write; and (b) no read in H returns 0 (the initial value of variables). These assumptions are only made to simplify the proof and have no influence over the validity of this lemma. The algorithm starts with constructing a cover function τ as:

Denote by f the read-mapping that maps each read to the identifier of the responsible write, we then upgrade the cover function to a witness OCF with the following procedures:

AddWrite For each access o, if a read r belongs to τ (o), then we upgrade τ (o) to be τ (o)∪{f (r)}. ObsClosed For any two accesses u and v, if one of them is a synchronization, and

if u is a synchronization, and there is another access w ∈ τ (v) such that u ∈ τ (w), then

A typical OCF returns for each access a self-contained set, in which every read can find its corresponding write. This property is achieved with the procedure AddWrite. The procedure ObsClosed meets the constraints imposed by OCF as in Definition 4. Our algorithm repeats the above procedures until τ is fixed, which finishes in O(n 4 ) (O(n) for AddWrite and O(n 3 ) for ObsClosed for n accesses in H). Once an OCF is generated, the next step is to check whether the weak order is preserved, that is verifying: For any two accesses, u and v, if u ∈ τ (v), then v can not happen before u w.r.t. the weak order. This checking process can be done in O(n 2 ).

A failure of passing the check suggests that no OCF is available to satisfy Definition 5, that is the instance H is not in TWC-read. However, even if the check is passed, it is still possible that H is not weakly consistent, since the OCF can not guarantee every τ (o) will be reasonably explained. The algorithm continues with checking if there is a set τ (o) involves one of the following anomalous forms:

ReadStaleUpdate A read r observes two write w 1 , w 2 accessing the same location, the responsible write is w 1 but w 1 happens before w 2 w.r.t. the weak order. LateWrite An access w is the responsible write for r, but r happens before w w.r.t. the weak order.

ReadStaleUpdate can be verified within O(n 3 ) for each read, therefore the whole time required is O(n 4 ). The form LateWrite cam be verified within O(n 3 ). An OCF is anomalous forms free implies every τ (o) can be unfolded into a sequence residing in S r/w . Lemma A.3 validates this fact: Every τ (o) is anomalous forms free iff H is in TWC-read, a result, combined with the above analysis, supplies us the algorithm that can solve the two processes TWC-read problem in polynomial time.

Given H, we denote by Υ : τ → {0, 1} a function such that for any τ ∈ τ , Υ (τ ) = 1 ⇔ ∀o ∈ O, ∃σ ∈ H| τ (o)∩D ∩ S r/w . Lemma A.3. Let τ b be the OCF generated from the aforementioned procedures, then there exists an OCF τ such that Υ (τ ) iff Υ (τ b ).

Proof. (⇐)


Life Fellow, IEEE Bernard Picinbono
email: bernard.picinbono@lss.supelec.fr

Cherif Bendjaballah

Poisson Processes with Integrable Density

Keywords: Detection and estimation, integration of the density, nonhomogeneous Poisson processes, point processes, renewal processes

When the density of a Poisson process is integrable various expressions published in the literature are incorrect. This is especially the case of the probability distribution of the distance between an origin and the following points of the process. The first purpose of this paper is to explain why the integrability of the density changes the situation. The second is to discuss various consequences of this fact on the probability distribution of random variables extracted from the process. Computer experiments are presented and are in excellent agreement with theoretical results. Some extensions of the same problem concerning renewal processes are discussed.

I. INTRODUCTION

Poisson processes play an important role in many areas of Applied Probability, Physics, and Information Sciences. They are defined and studied in various books corresponding to quite different approaches and among them we can cite [START_REF] Snyder | Random Point Processes[END_REF], [START_REF] Snyder | Random Point Processes in Time and Space[END_REF], [START_REF] Blanc-Lapierrre | Fonctions Aléatoires[END_REF], [START_REF] Daley | An Introduction to the Theory of Point Processes, Vol I, Elementary Theory and Methods[END_REF], [START_REF] Lowen | Fractal-Based Point Processes[END_REF]. There are also many papers discussing the use of Poisson processes in communication theory [START_REF] Bar-David | Communication under the Poisson regime[END_REF], [START_REF] Rubin | Regular point processes and their detection[END_REF], [START_REF] Rubin | Reduced memory likelihood processsing of point processes[END_REF], [START_REF] Fishman | The statistical analysis of space-time point processes[END_REF], [START_REF] Hero | Timing estimation for a filtered Poisson process in Gaussian noise[END_REF]. This is especially important in the context of optical communications at very low level of intensity. Indeed in this case the only information available is the time instants when photons are detected [START_REF] Saleh | Photoelectron Statistics[END_REF], [START_REF] Saleh | Fundamental of Photonics[END_REF].

The purpose of this correspondence is to show that the expressions of some probability distributions associated with a Poisson process are quite different depending on whether the density of this process is integrable or not. Various expressions given in the literature which are valid when the density is not integrable, become incorrect when the density is integrable and this situation is very common. The simplest example appears for Poisson processes in time when the density is limited to a given time interval, as in any physical situation. In order to understand where the problem is coming from, we present in Section II some known properties of Poisson processes with non-integrable density. In Section III the problem introduced by the fact that the density is integrable is discussed and explained. Some consequences on the probability distributions of distance between points are studied and various numerical calculations are presented in order to illustrate the results. Finally some extensions to renewal processes are presented and computer experiments on Poisson and renewal processes show an excellent agreement between theory and experiment.

II. REVIEW OF KNOWN RESULTS FOR NON-INTEGRABLE DENSITY

Let us summarize the most important facts concerning Poisson processes used below.

A. Number of Points

A point process (PP) is a random distribution of points (in general time instants) x i . It is a Poisson process if the random variables (RV) equal to the number of points in non-overlapping time intervals are independent. Such a process is completely characterized by its density λ(x). In all that follows it is assumed that λ(x) < +∞. It results from the independence assumption that the number N (x 1 , x 2 ) of points in the interval [x 1 , x 2 [ is a Poisson RV characterized by its mean value m(x 1 , x 2 ) given by

m(x 1 , x 2 ) = x2 x1 λ(x)dx, x 1 < x 2 .
(1)

It is useful for what follows to introduce the mean value m(x) = m(0, x) where 0 is an arbitrary origin.

This yields

m(x 1 , x 2 ) = m(x 2 ) -m(x 1 ). (2)
In most cases the density λ(x) is not integrable, which means that m(+∞) is infinite. This is especially true for stationary Poisson processes for which λ(x) is constant and m(x) = λx. We shall see that this property greatly simplifies the calculations.

B. Position of Points

Another approach consists in defining the PP by the position of its points [START_REF] Snyder | Random Point Processes[END_REF], [START_REF] Bar-David | Communication under the Poisson regime[END_REF] - [START_REF] Hero | Timing estimation for a filtered Poisson process in Gaussian noise[END_REF]. Let 0 be an arbitrary origin and X i be the RV equal to the distance between the origin and the ith point of the Poisson process posterior to this origin. By construction we have 0 < X i < X j if i < j. Consider now the random vector X n with components X i , 1 ≤ i ≤ n. The probability density function (PDF) of X n is given by

p n (x n ) = exp[-m(x n )] n i=1 λ(x i ) (3)
when x 1 < x 2 < ... < x n and zero otherwise. This expression appears in [START_REF] Snyder | Random Point Processes[END_REF], [START_REF] Snyder | Random Point Processes in Time and Space[END_REF], [START_REF] Blanc-Lapierrre | Fonctions Aléatoires[END_REF] and in similar forms in [START_REF] Bar-David | Communication under the Poisson regime[END_REF]- [START_REF] Hero | Timing estimation for a filtered Poisson process in Gaussian noise[END_REF]. Note that for n = 1 this expression becomes

p 1 (x) = λ(x) exp[-m(x)], (4)
which yields the classical exponential distribution when λ(x) = λ or m(x) = λx.

The principle of the proof of (3) appearing almost in the same form in [START_REF] Snyder | Random Point Processes[END_REF], [START_REF] Snyder | Random Point Processes in Time and Space[END_REF], [START_REF] Blanc-Lapierrre | Fonctions Aléatoires[END_REF], [START_REF] Bar-David | Communication under the Poisson regime[END_REF] is given in Appendix I where it is also shown that if M = m(+∞) is not finite the integral of (3) is 1, as expected for any PDF.

From (3) we deduce the marginal distribution p n (x i ) of X i defined by

p n (x i ) = p n (x n )dx 1 ...dx i-1 dx i+1 ...dx n . (5)
It is shown analytically in Appendix II that p n (x i ) is independent of n and can be written as

p n (x i ) = p(x i ) = λ(x i ) exp[-m(x i )] m i-1 (x i ) (i -1)! . ( 6
)
This expression can be shown directly by using the property of independence of the number of points in non-overlapping intervals. Indeed the term λ(x i )dx i is the probability of having at least one point in the interval [x i , x i + dx i [ and the rest of the expression ( 6) is the probability of having i -1 points in the interval [0, x i [. It is easy to verify that if λ(x) is not integrable, the integral of (6) is equal to 1.

Let us now consider the marginal PDF p n (x i , x j ) i < j < n. From an obvious calculation or by using a direct reasoning similar to the one indicated above we deduce that p n (x i , x j ) = p(x i , x j ) with

p(x i , x j ) = λ(x i )λ(x j ) exp[-m(x j )] m i-1 (x i ) (i -1)! . m j-i-1 (x i , x j ) (j -i -1)! . ( 7
)
February 2, 2018 DRAFT

In particular for successive points we obtain

p(x i , x i+1 ) = λ(x i )λ(x i+1 ) exp[-m(x i+1 )] m i-1 (x i ) (i -1)! . ( 8
)
From the marginal PDFs already calculated we deduce the conditional PDFs

p n (x j |x i ) = p(x i , x j )/p(x i ) = λ(x j ) exp[-m(x i , x j )] m j-i-1 (x i , x j ) (j -i -1)! . (9)
For successive indices this becomes

p n (x i+1 |x i ) = p(x i , x i+1 )/p(x i ) = λ(x i+1 ) exp[-m(x i , x i+1 )]. (10)
We have of course

∞ xi p n (x i+1 |x i )dx i+1 = 1. (11)

Markov Property

The conditional probability of the RV X i+1 conditional to a given value of X i , or X i = x i is defined by p(x i+1 )/p(x i ). Using (3) yields that this ratio is equal to p(x i+1 |x i ) given by [START_REF] Hero | Timing estimation for a filtered Poisson process in Gaussian noise[END_REF]. This shows that the successive RVs X n are a Markov process with the transition probability [START_REF] Hero | Timing estimation for a filtered Poisson process in Gaussian noise[END_REF].

C. Time Intervals

Another possible approach of a PP is to consider the distances between successive points, sometimes called life times when x is the time. These distances Y i are related with the RVs X i by

Y i = X i -X i-1
and Y 1 = X 1 . These RVs can be considered as the values of a discrete time positive signal. By an obvious transformation we deduce the PDF of the Y i s which is

p(y n ) = λ(y 1 )λ(y 1 + y 2 )...λ(y 1 + y 2 ... + y n ) exp[-m(y 1 + y 2 + .. + y n )]. (12)
This is especially interesting in the stationary case where λ(x) = λ. In this situation the life times Y i are a sequence of IID random variables with an exponential distribution defined by λ. This means that a stationary Poisson process is a renewal process with an exponential distribution [START_REF] Daley | An Introduction to the Theory of Point Processes, Vol I, Elementary Theory and Methods[END_REF].

However in the nonstationary case the PDF (12) cannot be factored and this means that the successive life times are not independent RVs. Then the property of independence of the number of points in distinct intervals characteristic of Poisson processes is no longer valid for the intervals between points. This means that a non-stationary Poisson process is not a non-stationary renewal process characterized by the fact that the life times Y i are independent but not identically distributed.

It is easy to verify that the RVs Y i do not, in general, constitute a Markov process. This shows that it is much more convenient to work with the distances X i than with the life times Y i .

DRAFT February 2, 2018

III. THEORETICAL RESULTS WITH INTEGRABLE DENSITY

A. General Expressions

All the results of the previous section are consequences of (3). We shall see that this basic expression is no longer valid when the density λ(x) is integrable. Thus we must find another expression replacing

(3) in this situation.

Let us illustrate the problem in the very simple case of n = 1. The PDF p 1 (x 1 ) is given by ( 4) and its integral is obviously 1 -exp(-M ) where

M = +∞ 0 λ(x)dx < +∞. ( 13
)
Thus the integral is equal to 1 only when M is infinite. As a consequence for finite M the function

p 1 (x 1 )
of ( 4) is not a PDF.

This could be related with the concept of defective RVs introduced in [START_REF] Feller | An Introduction to Probability Theory and its Applications[END_REF], [START_REF] Feller | An Introduction to Probability Theory and its Applications[END_REF]. This concept, however, does not play any role in the following calculations. Readers interested in this question can look at p.

127 of [START_REF] Feller | An Introduction to Probability Theory and its Applications[END_REF] or p. 270 of [START_REF] Feller | An Introduction to Probability Theory and its Applications[END_REF].

The same situation appears for p n (x n ) of ( 3) and its integral, denoted B n , is no longer equal to 1 but to I n (0), where I n (x) is defined and calculated in Appendix III. This yields

B n = 1 -exp(-M ) 1 + M 1 (1)! + ... + M n-1 (n -1)! . ( 14
)
This relation shows clearly that if M is infinite B n = 1, and we return to the results of the previous section.

In order to obtain a normalized PDF it could be sufficient to replace (3) by

p n (x n ) = 1 B n exp[-m(x n )] n i=1 λ(x i ). (15)
But this procedure is quite artificial and does not at all explain why the reasoning of Appendix I which shows (3) is not valid when the density is integrable.

For this purpose note first the meaning of the quantity B n . Let N be the RV equal to the number of points of the Poisson process posterior to the origin 0. It is a Poisson RV with mean value M because of [START_REF] Feller | An Introduction to Probability Theory and its Applications[END_REF]. As a consequence we deduce from ( 14) that

B n = 1 -P [N ≤ n -1] = P [N ≥ n]. (16)
Then the parameter B n appearing in [START_REF] Bendjaballah | Correlation of time intervals for random point processes[END_REF] is the probability that there are at least n points of the Poisson process posterior to the origin 0. When M is infinite this probability is of course equal to 1 because, whatever n, there are, with probability 1, at least n points of the Poisson process posterior to 0.

February 2, 2018 DRAFT

Let us now introduce the following time intervals.

Ī1 = [0, x 1 [ , Īk = [x k-1 + dx k-1 , x k [ , 1 < k ≤ n, (17)
Jk = [x k , x k + dx k [ , 1 ≤ k ≤ n. (18)
Let N (K) be the number of points of the Poisson process in any interval K. We can associate with the previous intervals the following events

A n = n k=1 [N ( Īk ) = 0] , B n = n k=1 [N ( Jk ) ≥ 1]. (19)
Let now E n (x n , dx n ) = E n be the event A n ∩ B n . The principle of reasoning of Appendix I is to say

that p n (x n )dx n = P [E n ].
But the event E n has no meaning if there is less than n points posterior to the origin 0. Thus p n (x n )dx n is the conditional probability

p n (x n )dx n = P [E n |(N ≥ n)], (20)
where N is the number of points posterior to the origin 0, i.e. belonging to the interval [0, +∞[. This conditional probability can be written as

P [E n |(N ≥ n)] = P [E n ∩ (N ≥ n)]/B n , (21)
because B n is the probability that N ≥ n. We also have

P [E n ∩ (N ≥ n)] = P [E n ]P [(N ≥ n)|E n ]. ( 22
) But P [(N ≥ n)|E n ] = 1
because if E n is realized there are at least n points posterior to the origin.

Finally we deduce from the Poisson assumption that

P [E n ] = P [E n (x n , x n + dx n )] = exp[-m(x n )] n i=1 λ(x i )dx n , (23)
and inserting this expression in (21) yields [START_REF] Bendjaballah | Correlation of time intervals for random point processes[END_REF]. Thus the factor B n , defined by [START_REF] Feller | An Introduction to Probability Theory and its Applications[END_REF] and appearing in [START_REF] Bendjaballah | Correlation of time intervals for random point processes[END_REF] in order to ensure the normalization of the PDF, is not at all artificial but justified by the fact that

p n (x n ) is a conditional PDF.
In order to specify this fact it could be convenient to write this PDF as

p n,Xn (x n |N ≥ n) which is the conditional PDF of the random vector X n with the condition that N ≥ n.

This notation, however, has a complicated form and for simplification we admit that all the PDFs noted p n are conditional PDFs.

DRAFT February 2, 2018

B. Marginal Probability Density Functions

These PDFs are obtained by inserting (15) into [START_REF] Lowen | Fractal-Based Point Processes[END_REF]. It is clear that when λ(t) is integrable, the integration with respect to x i+1 , x i+2 , ..., x n will change the result and then ( 6) is no longer valid.

For i = n there is no such integration and the use of ( 3) or [START_REF] Bendjaballah | Correlation of time intervals for random point processes[END_REF] will only introduce the factor 1/B n ensuring the normalization. Thus we have

p n (x n ) = 1 B n λ(x n ) exp[-m(x n )] m n-1 (x n ) (n -1)! . ( 24
)
On the other hand if i < n there are n -i integrations with respect to the variables

x k , i + 1 ≤ k ≤ n = i + (n -i)
and the result is

p n (x i ) = 1 B n K i-1 (0, x i )λ(x i )I n-i (x i ), (25)
where K i (a, b) and I n (x) are defined in Appendices II and III respectively. By using ( 51) and ( 56) we obtain for

1 < i < n p n (x i ) = λ(x i ) m i-1 (x i ) (i -1)! exp[-m(x i )] × h n (x i ), (26)
h n (x i ) = 1 B n 1 -e -[M -m(xi)] c n-i [a(x i )] , (27)
where a and c n (a) are defined by ( 54) and ( 55) respectively. For i = n = 1 the result is given by (24).

Note that p n (x i ) = p(x i )h n (x i ), where p(x i ) is given by [START_REF] Bar-David | Communication under the Poisson regime[END_REF], and corresponds to the case where λ(x)

is not integrable. This means that h n (x i ) is the correction factor due to the fact that λ(x) has a finite integral. Note also that, contrary to [START_REF] Bar-David | Communication under the Poisson regime[END_REF], this PDF is no longer independent of n. Finally note that if

M → ∞ we return to [START_REF] Bar-David | Communication under the Poisson regime[END_REF].

It is especially interesting to study the PDF p n (x 1 ), written simply p n (x). It is given by

p n (x) = λ(x)e -m(x) 1 B n 1 -e -[M -m(x)] c n-1 [a(x)] . (28)
It is clear that for a stationary Poisson process of density λ, M is infinite, which yields p n (x) = λ exp(-λx), PDF obviously independent of n.

Consider now the case of a time-limited Poisson process. This means that its density λ(t) is bounded and zero outside an interval [0, T ]. This ensures that the density is integrable. The same kind of assumption is introduced in [START_REF] Bar-David | Communication under the Poisson regime[END_REF] and [START_REF] Hero | Timing estimation for a filtered Poisson process in Gaussian noise[END_REF]. In some sense this assumption corresponds to any experimental situation with Poisson processes because any experiment has a beginning (0) and an end (T ). Note that if n >> 1 the PDF p n (x) satisfies p n (T ) = 0. Indeed it results from (54) that a(T ) = 0 which implies h n (T ) = 0.

Let us now present numerical results calculated with some specific examples. First we assume that the density λ(x) is constant in the interval [0, T ] and 0 otherwise. This situation is sometimes specified by It is worth pointing out that when n → ∞ the density p n (x) tends to a Dirac distribution. Indeed it is a PDF of a RV with mean value and variance tending to 0. This has an evident interpretation: if there is an infinite number of points in [0, T ] the first after the origin is at the origin.

In order to amplify the phenomenon let us now consider the case where the density of the Poisson process is zero outside the interval [0, T [ and in this interval is the increasing exponential function Let us now consider the case of the two dimensional PDF p n (x i , x j ). If j = n we can use the same argument as previously and the result is

p n (x i , x n ) = 1 B n p(x i , x n ), (29)
where p(x i , x j ) is given by [START_REF] Rubin | Regular point processes and their detection[END_REF]. On the other hand if j < n there are n -j integrations with respect to the variables x k with k ≥ j + 1 is such a way that

p n (x i , x j ) = p(x i , x j )h n (x j ), (30)
where p(x i , x j ) and h n (x j ) are given by ( 7) and ( 27) respectively.

DRAFT February 2, 2018

For j = i + 1 we obtain

p n (x i , x i+1 ) = p(x i , x i+1 )h n (x i+1 ), (31)
where p(x i , x i+1 ) is given by [START_REF] Rubin | Reduced memory likelihood processsing of point processes[END_REF].

As above this yields the conditional PDFs and in particular we have

p n (x i+1 |x i ) = λ(x i+1 )e -m(xi,xi+1) h n (x i+1 ) h n (x i ) . ( 32
)
If M → ∞ the last term tends to 1 and we return to [START_REF] Hero | Timing estimation for a filtered Poisson process in Gaussian noise[END_REF]. Similar expression has recently been established for a simple case [START_REF] Bendjaballah | Correlation of time intervals for random point processes[END_REF]. Finally it is easy to verify that

p n (x i+1 |x 1 , x 2 , ..., x i ) = p n (x i+1 |x i ), (33)
which characterizes the Markov property.

C. Conditioning on fixed values of N

Instead of using the condition N ≥ n in order to arrive at the PDF given by ( 15), it is possible to introduce the condition N = n. To avoid confusion with the previous case we note q n (x n ) the conditional PDF p n (x n |N = n). This requires of course that the density λ(t) is integrable. This situation corresponds to the calculation presented in Section II of [START_REF] Bar-David | Communication under the Poisson regime[END_REF]. This assumption means that there is no point of the Poisson process posterior to x n . A reasoning similar to the one presented in Appendix I yields the result appearing in Eq. ( 4) of [START_REF] Bar-David | Communication under the Poisson regime[END_REF], or with slightly different notations

q n (x n ) = exp(-M ) n i=1 λ(x i ) (34)
for x 1 < x 2 < .... < x n and 0 otherwise. Let us show that this is not a PDF. Indeed the integral I of this function is

I = exp(-M ) M n n! = P (N = n) (35)
which is not equal to 1. Using the same reasoning as for ( 20)-( 23) we find that the true PDF is

q n (x n ) = n! M n n i=1 λ(x i ). ( 36
)
Let us present some consequences of this result. If n = 1 we obtain q 1 (x) = (1/M )λ(x). If furthermore we introduce the assumption of semistationarity which means that λ(x) = λ for 0 ≤ x ≤ T and 0

otherwise we obtain M = λT and thus q 1 (x) = 1/T . This is the well known result which states that if there is 1 point of a stationary Poisson process in an interval, this point is uniformly distributed in this interval. Finally the marginal PDF q n (x 1 ) defined as in ( 28) is

q n (x) = λ(x) n M n [M -m(x)] n-1 . ( 37
)
February 2, 2018 DRAFT

In the semistationary case considered just above this becomes

q n (x) = n T n [T -x] n-1 . ( 38
)
It can be verified that it is the PDF of the distance between the origin and the first point posterior to it when the RVs X i are IID and uniformly distributed in [0, T ]. This property of points of Poisson processes for a fixed value of N (N = n) is well known.

IV. EXTENSIONS TO RENEWAL PROCESSES

A renewal process (RP) is a PP in which the distances Y i between successive points are positive IID random variables [START_REF] Daley | An Introduction to the Theory of Point Processes, Vol I, Elementary Theory and Methods[END_REF]. Such a process is then defined by the PDF f (x) of these distances. We shall now consider RPs with a finite duration. We start from an origin considered as point of the process and we consider a sequence of IID RVs Y i . The PP is limited to the interval ]0, T ] and all the points outside of this interval are erased.

We limit our discussion to the calculation of the PDF p n (x) of the distance between the origin and the first point of the process posterior to this origin with the condition that there are at least n points in the interval ]0, T ].

For this purpose let π n (x) and b n (x) be the probabilities of having n points or at least n points in ]0, x] respectively. They are related by

b n (x) = 1 - n-1 i=0 π i (x) (39)
and b 0 (x) = 1. Finally let B n be the probability that there are at least n points in ]0, T ], or B n = b n (T ).

It is shown in Appendix IV that for n > 1

p n (x) = p n (x|N ≤ n) = (1/B n )f (x)b n-1 (T -x), (40)
where f (x) is the PDF of the distance between successive points when there is no time limitation of the process. The division by B n ensures that p n (x) is a normalized function. For n = 1 we have simply

p 1 (x) = (1/B 1 )f (x).
As π 0 (0) = 1 and π k (0) = 0 for k > 0, we deduce that b n (0) = 0 and then p n (T ) = 0, which is the same result as the one indicated above for Poisson processes.

In order to illustrate this result let us consider the case of a renewal process sometimes called an Erlang process. It is obtained by deleting regularly one point over two of a stationary Poisson process.

Thus the PDF function of the distances between points is f (y) = λ 2 y exp(-λy).

The functions p n (x) are represented in Figure 3 for λ = 2 and T = 1. The value of λ is chosen in order that the mean distance between successive points is equal to 1, as in Figure 1. Note finally that p n (T ) = 0, as indicated above. In order to realize such a PP in a computer experiment we can apply a general method used in [START_REF] Bendjaballah | Correlation of time intervals for random point processes[END_REF] to construct a large variety of PPs. The sequence Y i defining the renewal PP characterized by the PDF f (y) satisfies the relation

U i = Yi 0 f (y)dy = F Y (Y i ), (41)
where U i ∈ [0, 1] are RVs of uniform PDF U (0, 1) and f (y) is a given PDF with the distribution function

F Y (y).
Then the RVs Y i are deduced from the U i s by the relation

Y i = F -1 Y (U i ).
In order to obtain an exponential distribution characterizing a Poisson process this becomes

Y i = - 1 λ log (1 -U i ) . (42)
This method cannot be used directly to generate an Erlang renewal PP because the distribution function of the PDF f (y) = λ 2 y exp(-λy) cannot be simply inverted. But another procedure is possible. It suffices to note that f (y) is the PDF of the sum of two IID exponential RVs. Then the method starts now from two IID uniform RVs U 1,i , U 2,i ∈ U [0, 1]. By applying twice (42) we obtain S 1,i = -1 λ log(1 -U 1,i ) and S 2,i = -1 λ log(1-U 2,i ). These RVs are IID with an exponential distribution and their sum Y i = S 1,i +S 2,i has the PDF f (y) = λ 2 y exp(-λy) defining a stationary Erlang PP. Note that because this sum the density of the corresponding Erlang PP is λ/2, as indicated at the end of the previous section.

Up to now our two processes (Poisson and Erlang) are strictly stationary and in order to compare experimental results with those established above we have to construct the algorithm realizing the condition introducing the conditional PDFs p n (x) presented in (28) and (40) and appearing in Figs. 1 and 3. This condition is that there are at least n points in the finite interval [t i , t + T [ posterior to each point of the stationary process. We must then eliminate all the samples Y i such that

Y i + Y i+1 + ... + Y i+n-1 > T .
This sum can easily be calculated recursively from the samples Y i . In the experiments presented below we take n = 2. The condition used for p 2 (x) is then that there are at least 2 points in any interval February 2, 2018 DRAFT

[x 1 , x 1 + dx 1 [. As these intervals are distinct, the number of points in them are independent Poisson RVs, which yields

p(x 1 )dx 1 = λ(x 1 ) exp[-m(x 1 )]dx 1 . (45)
This is (3) for n = 1 or (4). Suppose now that n = 2. As the RV X 2 is related to the second point posterior to the origin 0, we deduce by the same reasoning that the probability p(x 1 , x 2 )dx 1 dx 2 is the probability of finding 0 points in the intervals [0, x 1 [ and [x 1 +dx 1 , x 2 [ and at least 1 point in the intervals

[x 1 , x 1 + dx 1 [ and [x 2 , x 2 + dx 2 [. This yields p(x 1 , x 2 )dx 1 dx 2 = λ(x 1 )λ(x 2 ) exp[-m(x 2 )]dx 1 dx 2 , (46)
which is (3) for n = 2. The extension to any value of n is obvious, which yields (3).

Let us now consider the calculation of the integral I = p n (x n )dx n where p n (x n ) is given by (3). It can be written as

I = ∞ 0 dx 1 λ(x 1 ) ∞ x1 dx 2 λ(x 2 )... ∞ xn-2 dx n-1 λ(x n-1 )J(x n-1 ) (47)
with

J(x n-1 ) = ∞ xn-1 dx n λ(x n ) exp[-m(x n )]. (48)
Noting that the derivative of exp

[-m(x)] is -λ(x) exp[-m(x)] yields J = exp[-m(x n-1 )]-exp[-M ] = exp[-m(x n-1 )
] because M is assumed to be infinite. By repeating the same calculation we arrive to

I = +∞ 0 dx 1 λ(x 1 ) exp[-m(x 1 )
] which is equal to 1.

APPENDIX B

CALCULATION OF [START_REF] Lowen | Fractal-Based Point Processes[END_REF] In ( 5) the integration with respect to x i+1 , x i+2 , ..., x n yields exp[-m(x i )] as seen in Appendix I. As

a result p n (x i ) = λ(x i ) exp[-m(x i )] × K i-1 (x i ) where K i-1 (x i ) is the integral K i-1 (x i ) = xi 0 dx 1 λ(x 1 ) xi x1 dx 2 λ(x 2 )... xi xi-2 dx i-1 λ(x i-1 ). (49)
It is a particular case of the integral

K i (a, b) = b a dx 1 λ(x 1 ) b x1 dx 2 λ(x 2 )... b xi-1 dx i λ(x i ). (50)
Let us show by recursion that

K i (a, b) = 1 i! [m(b) -m(a)] i . (51)
February 2, 2018 DRAFT This relation is obviously valid for i = 1. Suppose that it holds for i -1. Let us show that it is valid for i. Using (50) and (51) yields

K i (a, b) = b a dx 1 λ(x 1 ) 1 (i -1)! [m(b) -m(x 1 )] i-1 . (52)
Noting that the derivative of m(x) is λ(x) yields (51) for i. As p n (

x i ) = λ(x i ) exp[-m(x i )]K i-1 (0, x i )
and m(0) = 0, we obtain [START_REF] Bar-David | Communication under the Poisson regime[END_REF].

APPENDIX C CALCULATION OF I n (x)

This is the integral

I n (x) = +∞ x dx 1 λ(x 1 ) +∞ x1 dx 2 λ(x 2 )... +∞ xn-1 dx n λ(x n ) exp[-m(x n )]. (53)
Let introduce the following expressions

a(x) = M -m(x), (54)
This relation is obviously valid for n = 1. Suppose now that it is valid for n -1 and calculate I n (x).

We can write

I n (x) = +∞ x λ(x 1 )I n-1 (x 1 )dx 1 . (57)
From (56) we have to calculate two integrals. It is clear that

February 2 ,

 2 2018 DRAFTthe term of semistationarity because it corresponds to the case of a stationary Poisson process of density λ observed in a finite interval [0, T ]. In this case the parameter M of the previous calculations is simply λT . This quantity is always finite but there are three different situations. If λT >> 1 we are in the case where the expressions valid for stationary processes can be applied because the factor exp(-M ) is almost equal to zero. In the opposite case if λT << 1 the interval [0, T ] contains only 0 or 1 point and the problem disappears because the parameter B n defined by[START_REF] Feller | An Introduction to Probability Theory and its Applications[END_REF] and used in (17) is arbitrarily small. It remains the intermediary situation which will now be analyzed. For simplification of the calculation we assume that λ = T = 1 = λT .The results of the calculation of p n (x) appear in Figure1. The PDF p n (x) is represented in semilogarithmic coordinates for various values of n. As p 1 (x) is deduced from p 0 (x) = λ exp(-λx) by a simple normalization factor, the corresponding curves (0 and 1) are parallel straight lines. Furthermore p 1 (x) > p 0 (x) because the first is normalized in [0, ∞[ and the second in [0, T ]. The other six curves correspond to n = 2, 23, • • • , 7. It is easy to verify that they satisfy p n (T ) = 0 and also that they are normalized functions of x.

λ 0

 0 Figure 2 with the parameters λ 0 = 1, T = 1, and c = 1.25. The density λ(x) is also represented in this figure. The general property p n (T ) = 0 appears clearly in the figure. This is the main difference with p 1 (x) that does not satisfy this relation according to (24). The tendency to the Dirac distribution appears for the same reason as above.

  thatI n (x) = exp[-m(x)] -exp(-M )c n [a(x)].

  1 ) exp[-m(x 1 )]dx 1 = exp[-m(x)] -exp[-M ] (58) because λ(x 1 ) exp[-m(x 1 )] is the derivative of -exp[-m(x 1 )]. Furthermore +∞ x λ(x 1 )a k (x 1 )dx 1 = 1 k + 1 a k+1 (x)(59)because the derivative of a(x) is -λ(x) and a(+∞) = 0. Using (55) yields (56), which completes the proof. For x = 0, m(x) = 0, which yields[START_REF] Feller | An Introduction to Probability Theory and its Applications[END_REF]. OF p n (x) FOR A RENEWAL PROCESS Let A n be the event that there are at least n points in the interval [0, T ]. Let E be the event that there is no point in ]0, x] and at least one point in [x, x + dx[. We have p n (x)dx = P (E|A n ) andP (E|A n ) = P (E ∩ A n ) P (A n ) = P (E)P (A n |E) P (A n ) . (60)Noting that P (E) = f (x)dx and thatP (A n |E) = 1 -

Figures captionsFigure 1 .

 1 Figures captions

Figure 2 .

 2 Figure 2. Probability density functions p n (x), 1 ≤ n ≤ 7 for a time-limited Poisson process of density λ(x) = λ 0 [exp(cx/T ) -1] (curve quoted λ), λ 0 = T = 1, c = 1.25.

Figure 3 .

 3 Figure 3. Probability density functions p n (x), 1 ≤ n ≤ 7 for an Erlang time-limited renewal process. PDF of the life time: λ 2 y exp(-λy), λ = 2, T = 1.

Figure 4 .

 4 Figure 4. Experimental measurements of p 2 (x) for conditions of Figures 1 and 3. Solid line: theory,

  We have seen in Section II. C that the intervals {Y i } between points of a PP constitute a positive discrete time signal. Conversely to any such signal we can associate a PP. Experiments on PPs can then be transformed into experiments on positive signals, and conversely.If the signal {Y i } is positive and strictly white (sequence of IID positive RVs) the corresponding PP is a stationary renewal process. Then in order to generate such a PP characterized by the PDF f (y) it suffices to realize a sequence of IID RVs with this PDF. If it is an exponential distribution, we obtain a

	V. COMPUTER EXPERIMENTS
	Poisson process.
	DRAFT	February 2, 2018

[t i , t + T [ and we must eliminate the samples Y i such that Y i + Y i+1 > T . For this purpose we calculate V i = Y i + Y i+1 and the samples X i corresponding to the conditional PDFs are given by

where sign(z) = z |z| , z = 0. These samples are correlated because of the term V i which introduces a correlation between X i and X i+1 . In order to suppress this correlation it suffices to take the samples Xi = (1/2)[1 + (-1) i ]X i . This is realized in the experiments described below. Note, however, that there is no apparent difference in the results when using X i or Xi , which means that the correlation between adjacent samples X i does not play any role in the measurements of their histograms. These histograms yield the conditional PDF p 2 (x) analyzed above and appearing in Figs. 1 and The curve P1 corresponds to a stationary Poisson process. This means that there is no condition and the PDF is exponential. This curve is the curve 0 of Fig. 1. The curve P2 and E correspond to a Poisson process and an Erlang process respectively. For this last curve the calculation requires the expression of the probabilities π i (x) used in (39). It has recently been obtained in [START_REF] Bendjaballah | Nonclassical second-order photon statistics[END_REF] and in the case of a constant density λ the result is

with µ(x) = λx and i = 2.

This figure indicates an excellent agreement between theory and experimental results. The precision is a bit smaller in the case of Erlang distribution and this is due to the introduction of the sum of two RVs as explained above. Note finally that, as expected by the theory, the PDFs p 2 (x) are zero for x = T .

We have then an experimental confirmation of the main theoretical result of this paper stating that the PDFs p n (x) are conditional probability density functions.

APPENDIX A PROOF OF (3) AND CALCULATION OF ITS INTEGRAL

Suppose first that n = 1. As x 1 is related to the first point of the process posterior to 0, the quantity p(x 1 )dx 1 is the probability of finding 0 points in the interval [0, x 1 [ and at least 1 point in the interval DRAFT February 2, 2018