George Giakkoupis
email: george.giakkoupis@inria.fr

Philipp Woelfel
email: woelfel@ucalgary.ca

Randomized Mutual Exclusion with Constant Amortized RMR Complexity on the DSM

Keywords: Mutual exclusion, RMR complexity, shared memory, oblivious adversary, DSM

In this paper we settle an open question by determining the remote memory reference (RMR) complexity of randomized mutual exclusion, on the distributed shared memory model (DSM) with atomic registers, in a weak but natural (and stronger than oblivious) adversary model. In particular, we present a mutual exclusion algorithm that has constant expected amortized RMR complexity and is deterministically deadlock free. Prior to this work, no randomized algorithm with o(log n/ log log n) RMR complexity was known for the DSM model. Our algorithm is fairly simple, and compares favorably with one by Bender and Gilbert [11] for the CC model, which has expected amortized RMR complexity O(log 2 log n) and provides only probabilistic deadlock freedom.

I. INTRODUCTION

Mutual exclusion, introduced by Dijkstra [START_REF] Dijkstra | Solution of a problem in concurrent programming control[END_REF], is one of the best studied problems in concurrent computing. A mutual exclusion object (or lock) is a fundamental synchronization primitive that allows processes to coordinate their access to a shared resource, by serializing the execution of a piece of code, called critical section. At any point in time, at most one process must be in its critical section; we say that this process owns the lock. A process obtains a lock through an entry section (or capture protocol), and the owner of a lock frees up the lock by executing an exit section (or release protocol). A textbook by Raynal [START_REF]Algorithms for Mutual Exclusion[END_REF] is devoted to mutual exclusion research up to the mid 80s, and a survey by Anderson, Kim, and Herman [START_REF] Anderson | Shared-memory mutual exclusion: Major research trends since 1986[END_REF] covers research between 1986 and 2003.

Early mutual exclusion algorithms did not take into account the gap between high processor speeds and the low speed/bandwidth of the processor-memory interconnect [START_REF] Culler | Parallel Computer Architecture: A Hardware/Software Approach[END_REF]. In distributed shared memory (DSM) systems, each shared variable is permanently locally accessible to a single processor and remote to all other processors. In cachecoherent (CC) systems, each processor keeps local copies of (remote) shared variables in its cache, and the consistency of copies in different caches is maintained by a coherence protocol. Memory accesses that cannot be resolved locally in DSM and CC systems are called remote memory references (RMRs). RMRs are orders of magnitude slower than local memory accesses. Hence, the performance of many algorithms for shared memory multiprocessor systems depends critically on the number of RMRs they incur [START_REF] Anderson | The performance of spin lock alternatives for shared-memory multiprocessors[END_REF], [START_REF] Mellor-Crummey | Algorithms for scalable synchronization on shared-memory multiprocessors[END_REF].

The mutual exclusion problem inherently requires processes to busy-wait in their entry section, and thus the number of shared memory accesses cannot be bounded. Therefore, the traditional step complexity measure, which counts the number of shared memory accesses, is not useful to determine the performance of mutual exclusion algorithms. Local-spin algorithms, which perform busy-waiting by repeatedly reading locally accessible shared variables, can achieve bounded RMR complexity and have practical performance benefits [START_REF] Anderson | The performance of spin lock alternatives for shared-memory multiprocessors[END_REF]. Recent research has almost entirely used the RMR complexity as a metric for the performance of mutual exclusion algorithms (see, e.g., [START_REF]Adaptive mutual exclusion with local spinning[END_REF]- [START_REF] Anderson | The performance of spin lock alternatives for shared-memory multiprocessors[END_REF], [START_REF] Attiya | An O(1)-barriers optimal RMRs mutual exclusion algorithm[END_REF]- [START_REF] Bender | Mutual exclusion with O(log 2 log n) amortized work[END_REF], [START_REF] Danek | Closing the complexity gap between FCFS mutual exclusion and mutual exclusion[END_REF], [START_REF] Danek | Brief announcement: Local-spin algorithms for abortable mutual exclusion and related problems[END_REF], [START_REF]A tight RMR lower bound for randomized mutual exclusion[END_REF], [START_REF] Hendler | Adaptive randomized mutual exclusion in sub-logarithmic expected time[END_REF], [START_REF]Randomized mutual exclusion with sub-logarithmic RMR-complexity[END_REF], [START_REF] Jayanti | Adaptive and efficient abortable mutual exclusion[END_REF]- [START_REF] Lee | Transformations of mutual exclusion algorithms from the cache-coherent model to the distributed shared memory model[END_REF], [START_REF] Pareek | RMR-efficient randomized abortable mutual exclusion[END_REF]).

Using strong primitives, such as fetch&increment objects, it is possible to implement mutual exclusion so that every process incurs only a constant number of RMRs per passage through the critical section. A prominent example is the MCS lock [START_REF] Mellor-Crummey | Algorithms for scalable synchronization on shared-memory multiprocessors[END_REF], which uses an object that allows both compare&swap (CAS) and swap operations. Other examples can be found in standard textbooks, such as [START_REF] Herlihy | The Art of Multiprocessor Programming[END_REF].

A significant amount of research has focused on determining the RMR complexity of the mutual exclusion problem if only atomic registers are available. Some common synchronization primitives, and in particular CAS and load-linked/store-conditional objects, have linearizable implementations with constant RMR complexity from registers [START_REF] Golab | RMRefficient implementations of comparison primitives using read and write operations[END_REF], and therefore they cannot help improving the asymptotic worst-case RMR complexity.

Unless mentioned otherwise, the results discussed below hold for the CC and the DSM model with atomic registers, and n is the number of processes.

The deterministic RMR complexity of mutual exclusion is Θ(log n) RMRs per passage through the critical section. The upper bound was established by Yang and Anderson's algorithm with O(log n) worst-case RMR complexity [START_REF] Yang | A fast, scalable mutual exclusion algorithm[END_REF]. Further, Anderson and Kim [START_REF] Anderson | Fast and scalable mutual exclusion[END_REF] conjectured that this bound is optimal. Following several lower bound proofs of increasing strength [START_REF] Cypher | The communication requirements of mutual exclusion[END_REF], [START_REF] Fan | An Ω(log n) lower bound on the cost of mutual exclusion[END_REF], [START_REF] Kim | A time complexity bound for adaptive mutual exclusion[END_REF], Attiya, Hendler, and Woelfel [START_REF] Attiya | Tight RMR lower bounds for mutual exclusion and other problems[END_REF] proved this conjecture true.

More recently, randomized techniques have been employed to improve the efficiency of mutual exclusion algorithms. To capture how random decisions made by processes can influence the order in which processes take steps (e.g., because accesses of some shared registers may be slower than others), it is assumed that an adversary produces the schedule. Among the most common adversary models are the strong adaptive adversary, where scheduling decisions can depend on all past events, including local coin flips, and the oblivious adversary, where scheduling decisions are independent of processes' random decisions, i.e., the adversary fixes the schedule in advance. Unfortunately, little can be gained by using randomization in the strong adaptive adversary model: Giakkoupis and Woelfel [START_REF]A tight RMR lower bound for randomized mutual exclusion[END_REF] showed that any mutual exclusion algorithm in this model has expected RMR complexity Ω(log n/ log log n), matching an upper bound by Hendler and Woelfel [START_REF]Randomized mutual exclusion with sub-logarithmic RMR-complexity[END_REF].

Note that unlike in deterministic algorithms, in randomized ones linearizable implementations of objects can in general not replace atomic objects, without affecting the probability distribution over possible outcomes [START_REF] Golab | Linearizable implementations do not suffice for randomized distributed computation[END_REF]. (Linearizability is defined in Section II; an object is atomic 1 if each operation takes effect instantaneously, once invoked. In particular, multiple operations on the same atomic object do not overlap in an execution.) The known constant-RMR CAS implementations [START_REF] Golab | RMRefficient implementations of comparison primitives using read and write operations[END_REF], however, preserve those probability distributions against a strong adaptive adversary. Therefore, the tight Θ(log n/ log log n) expected RMR bound for mutual exclusion for the strong adaptive adversary holds even if CAS or load-linked/store-conditional objects are available, in addition to registers. Hence, it is not possible to achieve o(log n/ log log n) RMR complexity without using stronger, less common synchronization primitives.

The strong adaptive adversary constitutes a very pessimistic system assumption, as it assumes that the system reacts in the most undesirable way to random decisions made by processes. Recently, researchers have increasingly focused on finding efficient randomized algorithms for the weaker, oblivious adversary model, e.g., for test-and-set [START_REF] Alistarh | Sub-logarithmic test-and-set against a weak adversary[END_REF], [START_REF] Giakkoupis | On the time and space complexity of randomized test-and-set[END_REF] or consensus [START_REF] Aspnes | Faster randomized consensus with an oblivious adversary[END_REF].

Bender and Gilbert [START_REF] Bender | Mutual exclusion with O(log 2 log n) amortized work[END_REF] have devised a randomized mutual exclusion algorithm (which will henceforth be called BG algorithm) that achieves O(log2 log n) expected amortized RMR complexity against the oblivious adversary, in a CC model that provides atomic registers and CAS objects. However, unlike existing randomized algorithms for the strong adaptive adversary, the BG algorithm guarantees deadlock freedom only with high probability per passage through the critical section (rather than with certainty). The BG algorithm uses CAS objects as mentioned above, and it 1 Sometimes in the literature the term "atomic" is used to denote "linearizable" (see, e.g., Lynch's textbook [START_REF] Lynch | Distributed Algorithms[END_REF]). remains unknown whether a similar efficient implementation from registers exist. 2 For the DSM model, no mutual exclusion algorithm with randomized o(log n/ log log n) RMR complexity against an oblivious adversary was known, until now.

Our Contribution

We present a mutual exclusion algorithm for DSM systems that is optimal w.r.t. several parameters. In particular, it

• has constant expected amortized RMR complexity in the oblivious adversary model, • is deterministically deadlock free (and can be transformed into starvation-free using standard techniques), • can be implemented from atomic O(log n)-bit registers only. In fact, we use an adversary that is stronger than the oblivious one, and seems realistic for the DSM model. The adversary can make scheduling decisions based on limited information about the operations each process has incurred in the past and the operation it will incur in its next step. While the adversary cannot know the exact register location on which such an operation has or will be performed, it can take into account the type of this operation (read or write), and whether it is a local or remote reference.

In our presentation of the DSM algorithm, we use a single CAS object, whose only purpose is to allow processes to repeatedly elect a leader, i.e., solve name consensus. Our complexity analysis makes no assumption that the CAS object is atomic (it assumes linearizability, but even weaker consistency conditions suffice), and therefore known implementation of CAS objects from registers [START_REF] Golab | RMRefficient implementations of comparison primitives using read and write operations[END_REF] can be used without sacrificing the asymptotic RMR complexity of our mutual exclusion algorithm.

Finally, our algorithm is fairly simple. This is in contrast to the BG algorithm, which relies on a stack of other implemented objects, such as max-registers and approximate counters with various properties.

II. MODEL

We consider the standard distributed shared memory (DSM) model, where a set {0, . . . , n -1} of n processes communicate by executing read and write operations on shared atomic registers. The set of registers is partitioned into n memory segments, one for each process. A read or write step on a register R by process p incurs a remote memory reference (RMR) if and only if R is not in p's memory segment. In this paper we assume that some registers are remote to all processes-it is not hard to see that this assumption can be made w.l.o.g. in mutual exclusion algorithms.

A schedule is a sequence of process IDs, and yields an execution in which processes take shared memory steps in the order determined by the sequence. Processes can flip (private) coins to make random decisions. We consider an adversary that schedules processes in an adaptive way, but with limited information. When scheduling the next process to take a step, the adversary has available the following information about each past step of any process, and about the step each process is poised to execute: the type of that step, i.e., whether it is a read or write, and whether the step constitutes a remote or local reference, i.e., whether or not the affected register is in the executing process' memory segment. The exact location of the register to which a read or write operation is applied, or what value is being read or written, is not revealed to the adversary, even after the process has executed that operation. In addition, we assume that the adversary learns whenever a lock() or release() call responds. (We assume that each process calls release() immediately after termination of its lock() method call, so the adversary knows when a process is poised to call release(). Thus, it can delay those release() calls arbitrarily.)

A compare&swap (CAS) object C supports the operations C.read(), which returns the value of C, and C.CAS(old, new), which writes new into C if C = old, and otherwise does not change C. In either case, it returns the value that C had at the point immediately before the operation was applied. It is known that CAS objects can be implemented from atomic registers such that each CAS() operation incurs O(1) RMRs [START_REF] Golab | RMRefficient implementations of comparison primitives using read and write operations[END_REF]. This implementation is linearizable: In any execution on an implemented CAS object, every CAS() operation can be associated with a linearization point between the invocation and response of that CAS(), such that ordering all CAS() operations by their linearization points yields a sequential execution that matches the specification of CAS.

The mutual exclusion problem can be specified in terms of a lock object, which supports operations lock() and release(). Each processes must alternate lock() and release() calls, starting with lock(). We say a process is in the entry section if its lock() method is pending; it is in the critical section if it has completed a lock() call but since then not called release(); and it is in the exit section while its release() method is pending. A process that is not in any of the entry, critical, or exit sections is in the remainder section.

A lock object provides the safety property of mutual exclusion, which states that no two processes can be in the critical section at the same time. Several progress conditions have been considered for mutual exclusion algorithms. The weakest standard condition is deadlock freedom, which guarantees system progress: as long as all processes that are not in the remainder section take sufficiently many steps, some process will enter the critical section.

III. THE ALGORITHM A. Main Ideas and High Level Description

We start by describing the core ideas of the algorithm. The complete pseudocode is given in Fig. 1, but here we will make some simplifications in order to not distract from the main insights. In particular, our code uses some sequence numbers, which we omit from this description. Also, some of the variables in the pseudocode are indexed by α. We will explain the purpose of this index later, and for now we will omit α from the corresponding variable names.

To decide which process enters the critical section first, we use a simple leader election protocol. The functionality of that is provided by a CAS object, denoted S in our pseudocode, which is initially ⊥. Each process p executes S.CAS(⊥, p), and if it succeeds (i.e., the operation returns ⊥) it becomes the leader, otherwise it loses.

A basic idea (albeit one that does not work without some additional twists) is the following: The losers of the leader election try to "notify" the leader, and if successful, the leader coordinates their passage through the critical section. For this mechanism, we use the notion of a backpack. Intuitively, processes try to join the leader's backpack while it is "open". At some point, the leader "closes" its backpack, and then arranges that all processes in the backpack go through the critical section, one by one.

More precisely, the leader w has n distinct registers in its local memory segment, namely, B[w][0..n -1]. If process p wants to join w's backpack (after losing the leader election), it writes its ID into B[w][p]. A flag, stored in register A[w] in our pseudocode, indicates whether w has already closed the backpack. Hence, after writing its ID to B[w][p], process p checks that flag, and if the backpack is still open, it is guaranteed to be found: After closing the backpack, the leader will scan the array B[w][ • ], and for every process it finds, it starts a handshaking procedure, coordinating the processes found to the critical section. (We say the leader promotes into the critical section each process it finds.) Hence, if process p joins the backpack while the backpack is still open, p can busy-wait on some variable in its local memory segment (in our case B[p][w])) which the leader will use to notify p, when it is p's turn to get promoted. Otherwise, if p finds that the backpack is closed when it checks the flag in A[w], then p "gives up", and does not wait for the leader to promote it. Finally, once the leader w has coordinated all processes from its backpack into the critical section, it resets the CAS object S by executing S.CAS(w, ⊥), so that subsequently other processes can become leaders.

While one can easily design a correct algorithm based on the above technique, this technique by itself does not achieve the desired RMR complexity, even against an oblivious adversary: The adversary could first schedule one process until it becomes the leader and has closed its backpack. After that, and before the leader resets the CAS object S, the adversary schedules all remaining processes to participate in the leader election. These processes will fail to join the backpack, and thus their RMRs are "wasted".

To motivate our second core idea, which deals with this issue, assume for a moment that processes have access to an oracle. After process w becomes the leader, the oracle provides it with exactly one ID, of a process q * chosen uniformly at random from the set M of processes that are already in the entry section or will enter the entry section before w closes its backpack. Given this information, the leader can busy-wait on B[w][q * ] (which is in w's memory segment) until q * appears there and thus has joined the backpack. Only after that, does w close its backpack and promotes all the processes it finds in B[w][ • ] into the critical section. If the random choice of q * ∈ M is independent of the adversary's scheduling decision, then we expect that roughly half of the processes in M join w's backpack (i.e, write to B[w][ • ]) before q * does. Hence, half of the processes in the entry section get promoted (in expectation), and thus for every constant number of RMRs, one process enters the critical section.

We now describe a randomized mechanism that provides a functionality that can replace the oracle above. We use a shared array R[1.. ], where = log n + 1, and each array entry is initially ⊥ (in our pseudocode we use again sequence numbers, so the actual initial value is different). Before participating in the leader election, each process writes its ID to an array entry R[λ], where λ ∈ {1, . . . , } is chosen at random in such a way that λ = i with probability Θ(1/2 i ). The leader scans this array from left to right until it finds the first index i such that R[i] = ⊥. Then (slightly simplifying matters) it uses the process ID q * found in R[i -1] in the same way as the oracle response above, i.e., it waits for q * to join its backpack. The crucial insight now is the following: Suppose M is the set of processes that write to R before the point t when q * starts to scan R, and let m = log |M | . Then with constant probability the following "good" event happened: all registers R[0], . . . , R[m] were written by processes in M , and exactly one process in

M wrote to R[m].
Given this event, the process that wrote to R[m] is uniformly distributed over M . Hence, by waiting for that process q * to join its backpack, w ensures that it does not close its backpack before Ω(|M |) processes have also joined its backpack, in expectation. To deal with some technical issues arising from processes writing to R at different times, and to simplify the analysis, the leader actually waits for every process it finds on R, not only the "topmost" one. Clearly, waiting longer cannot make matters worse.

The mechanism above still does not guarantee that all processes have a chance of getting promoted, but only those that write to R during a specific time interval. In particular, a process that writes to R after w scanned that array may be scheduled in such a way that it has no chance of getting promoted. To describe the solution to this problem we use the notion of "good" intervals. Recall that the CAS object S gets reset to ⊥ whenever a leader finishes its exit section, before it gets captured by the next leader. A good interval starts whenever the CAS object gets reset, and ends just before the next leader starts scanning R. As argued above, our technique guarantees that if M is the set of processes that write to R during a good interval, then in expectation Ω(|M |) processes get promoted by the one that becomes the leader in that interval.

We employ the following simple trick: We use two copies of essentially the entire data structure (i.e., of almost all shared objects). In the pseudocode, we add a subscript α to each shared object, where the value of α ∈ {0, 1} indicates the copy of the object. (We say "side α" to refer to copy α of the data structure.) At the beginning of its entry section, a process chooses a side α ∈ {0, 1} uniformly at random. Then, it proceeds as described above, but uses side α of the data structure. Since there are also two CAS objects, S 0 and S 1 , we may now have two competing leaders. To synchronize between them, we use an additional 2-process lock object, L (in fact, for technical reasons, we need that L be a 4-process lock). As soon as a process becomes the leader of side α (i.e., it captures S α ), it tries to capture L; and when it has captures L, it releases it only after it resets S α . As a consequence, every point in time belongs to either a good interval on side 0, or a good interval on side 1. Hence, since processes choose α at random, whenever they write to R α they have (at least) a 1/2 probability of writing during a good interval on side α.

There are several small technical difficulties to overcome in order to make these ideas work. Many of the difficulties stem from the fact that information on R may be outdated, i.e., it is left behind by processes that did not manage to join a backpack. To deal with this and other issues we use sequence numbers that processes increment frequently, and attach to the information they write to registers. Techniques to recycle sequence numbers are known [START_REF] Aghazadeh | Making objects writable[END_REF], [START_REF] Golab | RMRefficient implementations of comparison primitives using read and write operations[END_REF] and well understood. It is not difficult to bound sequence numbers so that our algorithm needs only O(log n)-bit numbers, but doing so makes the implementation more complicated and distracts from the core-ideas.

B. Implementation

The pseudocode of our algorithm is given in Fig. 1. We use array A[0..n -1] and, for s ∈ {0, 1}, arrays B s [0..n -1][0..n -1] and R s [1.. ], where = log n + 1. Array A s is used by processes to keep track of their sequence number and communicate their "status". Array B s implements the backpack functionality, and R s is used for the random "oracle" mechanism described earlier. Registers

Variables and Notation: N 0 = N ∪ {0} is the set of non-negative integers, and P = {0, . . . , n -1} is the set of processes. Lower case Latin and Greek symbols indicate (process-)local variables; the names of shared objects are capitalized. The scope of all process-local variables is global, i.e., they maintain their values between method calls. All shared variables are remote to all processes, except for array B, where B[p][q] is in p's local memory segment.

Shared Objects:

• A[0..n -1] is an array of registers, each storing a pair (seq, str),

where seq ∈ N 0 and str ∈ {want, done}∪ P ×N 0 . Each array entry is initially (0, done).

• Bs[0..n -1][0..n -1], for s ∈ {0, 1}, is an array of registers, each storing a pair (seq, stat), where seq ∈ N 0 and stat ∈ {trying, waiting, promoted, done}. Each array entry is initially (0, done). Subarray B[p][ • ] is in process p's memory segment.

• Rs[1.. ], for s ∈ {0, 1} and = log n +1 is an array of registers, each storing a pair in P × N 0 that is initially (0, 0). • Ss, for s ∈ {0, 1} is a CAS object which stores values in (P × N 0 ) ∪ {(⊥, ⊥)}, and is initially (⊥, ⊥). • L is a 4-process lock (4PLock) which can be accessed by the processes 0, . . . , 3. • Bits, for s ∈ {0, 1}, is a Boolean register that is initially 0.

lockp():

1 while True do B s [p][q] are in process p's local memory segment, and all other registers are remote to all processes. We also use compare&swap objects S s , s ∈ {0, 1}, to elect leaders, and registers Bit s to indicate the parity of the number of leaders that have been elected on S s . (The reason for this will be explained below.) Finally, we use a 4-process lock L. To capture L, a process calls L.lock(i), where i is a virtual ID in the set {0, 1, 2, 3}.

In line 2 of the lock() method, process p increments its sequence number stored in A[p].seq and writes the pair (c, want) to A[p], where c is the incremented sequence number. The status indicates that p has started the entry section. Then, in lines 3 and 4, p chooses α ∈ {0, 1} uniformly at random, and λ ∈ {0, . . . , } according to a geometric probability distribution that guarantees that λ = i with probability Θ(1/2 i ). In line 5, p writes its ID/sequencenumber pair (p, c) to R α [λ]. Then, in line 6, p tries to compare-and-swap (p, c) into S α .

If p's CAS() succeeds, p becomes the leader on side α. In that case, it reads Bit α into bit and then tries to capture lock L (in lines 8 and 9), using a virtual 2-bit ID with highorder bit α and low-order bit bit. Then, in lines 10-14, the process scans array R α , from left to right. Each time it finds a process/sequence-number pair (r, d), it checks the status of process r in A[r]. If that status is want or (p, c), then it is guaranteed that r will get promoted. All such pairs are added to a local set f ound, and as soon as the leader sees a process on R α that does not meet the above criterion, it stops scanning R α . In lines 15 and 16, the leader p waits for each process r added to f ound (except for itself), until r has joined p's backpack by writing to B α [p][r]. In line 17, p calls promote(), which is a method that promotes processes that wrote to B α [p][ • ], i.e., coordinates their entry into the critical section. The promote() method guarantees that p will successfully promote each process r that, before the invocation of that method, wrote to B α [p][r] the pair (c, trying) or (c, waiting), where c is p's current sequence number. Upon termination of promote(), all processes that p promoted will have exited the critical section. In lines 18 and 19, p first closes its backpack by writing (c, done) to A[p], and then calls promote() again. This second promotion call ensures that all processes that joined p's backpack before p closed it, will get promoted. After that, p enters the critical section. Now suppose p lost the leader election, i.e., its S α .CAS() in line 6 returned (w, d), where w is the leader of the CAS() operation at the time, and d is its sequence number. Then, in line 22, p writes the pair (c, (w, d)) to A[p] to indicate its new status, namely that it now aims to join w's backpack. In line 23, p reads a pair (w, d) from S α again, in case the leader has changed after p updated its status. This avoids deadlock, because otherwise p might try to join the backpack of an "old" leader, while the "new" leader may have seen (c, want) when it read A[p] in line 13, and In method release(), a loser p simply indicates in line 34 that it is done with the critical section by writing (c, done) to B α [w][p], where w is the current leader that promoted p. If p is a leader, then it executes lines 31-33. First it flips the bit Bit α , then it resets the CAS object S α to the initial value (⊥, ⊥), and finally it releases lock L. Note that it releases L only after resetting S α . This is necessary to ensure that there is always a good interval, either on side 0 or side 1 (see the high level description in Section III-A). However, this also means that a new leader may get elected on side α before the previous leader on side α has released L. Since processes use the bit Bit α to compute their virtual IDs, it is ensured that access to lock L is still safe. (This is the reason why we need to use a 4-process lock L, instead of a 2-process one.) Method promote() uses a straightforward handshaking mechanism to facilitate the promotion. The leader p scans array B α [p][ • ], and waits for each process r until either its sequence number stored in B α [p][r] changes, or until r is not trying to get promoted, as indicated by B α [p][r].status (lines 36 and 37). When this happens, r has made a decision whether it still wants to be promoted, by writing to that array entry that it is waiting for promotion, in line 26, or that it has given up, in line 29. (In the latter case, r may also subsequently have increased the sequence number stored in B α [p][r].seq, if meanwhile it started another attempt.) If r still wants to be promoted, it wrote (d, waiting), and is now busy-waiting in line 27. In this case, in line 39 process p notifies process r that it can enter the critical section, and then in line 40, p waits until r writes to B α [p][r] again; r will do so at the end of its exit section in line 34.

IV. COMPLEXITY ANALYSIS

In this section we analyze the RMR complexity of our algorithm. The proofs of deadlock freedom and mutual exclusion, as well as the proofs of some claims used for the complexity analysis are omitted due to space restrictions.

We start with some terminology and some simple facts. A subscript attached to a local variable indicates the process to which the local variable belongs to; e.g., c x denotes local variable c of process x.

We consider an execution of the algorithm, and fix linearization points of all CAS() operations in an arbitrary but unique way. When we say a process executes a CAS() operation op at time t, we mean that t is the linearization point of op. Sometimes we talk about the value that the CAS object has at a certain point; with that we mean the value it would have at that point, if all CAS() operations occurred atomically at their linearization points.

For s ∈ {0, 1} and i ≥ 0, we define a phase (s, i). Phase (s, 0) starts at the beginning of the execution, and phase (s, i), for i ≥ 1, starts when for the i-th time a S s .CAS() operation in line 32 linearizes. Phase (s, i) ends when phase (s, i + 1) starts. The leader of phase (s, i) is the unique process p that executes a successful S s .CAS() operation in line 6 which linearizes during phase (s, i). We say process x gets promoted during a promote() call by process y, if x enters the critical section while y's promote() call is pending. Note that y must own lock L when it calls promote(), so no two promote() calls can overlap, and thus a process can only get promoted during a single promote() call.

Theorem 1. Consider the random execution of the algorithm scheduled by a locality-aware adversary, and let τ m be the point when the implemented lock method has been invoked m ≥ 1 times. The expected total number of RMRs incurred until point τ m is O(m). W.l.o.g. we assume that after point τ m , the adversary does not schedule any new invocations to the lock() method; it only schedules processes that have already started a lock() operation until all such pending operations are completed. Let τ m denote that completion point. We will bound the number of RMRs incurred until point τ m , as this is clearly an upper bound on the RMRs incurred until τ m . The next lemma says that it suffices to bound instead the number of writes to arrays R s in line 5.

Lemma 2. The total number of RMRs incurred until point τ m is O(W m ), where W m is the total number of write operations on the two arrays R 0 and R 1 until τ m .

Proof: We consider the number of RMRs incurred by process p in a single iteration of the while-loop in the lock() method. Up to (and including) line 7, p incurs O(1) RMRs. The number of RMRs incurred in the rest of the while-loop iteration depends on whether or not p becomes a leader (i.e., wins the CAS object S αp in line 6). If p does not become a leader, then it executes the else-part of the if-else statement, in lines 21-21, which requires just O(1) RMRs. If p does become a leader, then it executes lines 8-20, which may incur more than O(1) RMRs. Precisely, more than O(1) RMRs may be needed in the for-loop in lines 11-11, and also in each of the two promote() operations in lines 17 and 19 (the remaining operations incur O(1) RMRs). In each iteration of the for-loop in lines 11-11, p incurs two RMRs, in lines 12 and 13, and in each promote() operation, an RMR is incurred every time p executes line 39. We explain next how to charge those RMRs to other processes, without charging more than O(1) RMRs in total to each process, per iteration of the while-loop. Claim 3. Let t be some point at which process w * has finished the for-loop in lines but not yet started the loop in lines 15 and 16. If (r * , d * ) ∈ f ound w * at point t, then at this point r * executes some iteration of the whileloop in a lock() operation, and enters the critical section in the same iteration while c r * = d * .

From Claim 3, it follows that in each iteration of the forloop in lines 11-11, except possibly for the last one, process p adds to set f ound p a distinct pair (r, d), not added to any other f ound set. For each such pair (r, d), we have that process r executes a different iteration of the while-loop in the lock() method. We charge to r the two RMRs incurred in the for-loop iteration in which (r, d) is added to f ound p , and charge to p the two RMRs of the last for-loop iteration. It follows that for each iteration of the while-loop executed by r or p, this process is charged at most O(1) of the RMRs incurred (by any process) in lines 11-11. Claim 4 allows us to distribute the RMR cost of a promote() operation to the processes that go through the critical section during that call, charging one RMR to each process q for each of its entries to the critical section. Since only one promote() operation can be in progress at a time (as the leader must own lock L during the call), no process is charged twice for the same passage through the critical section. Finally, we observe that each release() operation incurs O(1) RMRs.

Combining the above, we obtain that the total number of RMRs is asymptotically the same as the total number of iterations of the while-loop in the lock() method, executed by all processes, plus the total number of passages of processes through the critical section. Since for each passage, a process must execute at least one iteration of the while-loop, we conclude that the total number of RMRs is asymptotically the same as the total number of iterations of the while-loop, which is equal to the number of write operations on R 0 and R 1 . This completes the proof of Lemma 2.

Next we introduce the notions of good intervals and good writes, and show that in expectation at least half of the writes to arrays R 0 and R 1 are good. Thus, it suffice to bound the number of good writes.

For s ∈ {0, 1} and i ≥ 0, the good interval I s,i starts at the beginning of phase (s, i), and ends when the L.lock() operation in line 9 by the leader of phase (s, i) responds (i.e., when the leader has acquired that lock). A write operation on array R s in line 5 is good if it takes place in some good interval I s,i . Good intervals I s,i and I s,i with i = i do not overlap, but good intervals for different sides s may overlap. A critical observation for our analysis is that the union of all good intervals covers the complete execution. Since each process chooses the side α at random before writing to R α , with probability 1/2 that write will occur during a good interval on side α. A straight-forward application of Wald's Theorem yields the following lemma.

Lemma 5. In expectation, at least half of all write operations on arrays R 0 and R 1 are good.

Next we look at a single phase (s, i), and bound from below the number of times processes go through the critical section during that phase, in terms of the number of good writes to R s in the phase. Let k s,i be the number of good writes to array R s in phase (s, i), and let s,i be the number of passages through the critical section by processes in phase (s, i); if phase (s, i) does not exists, then k s,i = s,i = 0.

Lemma 6. E[ s,i ] ≥ E[k s,i ]/36.
Proof: We first give an overview of the proof. We fix the set of processes that perform a good write to array R s during phase (s, i), and condition on the event E that all the first κ = log(k s,i ) positions in R s get written by those good writes. Event E has constant probability, and implies that the leader of phase (s, i) will execute at least κ iterations of the for-loop comprising lines 11-11; and for each 1 ≤ j ≤ κ, it will add to its f ound set some process that wrote to R s [j] after the beginning of the phase. The leader will then have to wait in line 16 until all these processes have executed line 24, and in particular until the process p * that wrote to R s [κ] has done so. Given E, the conditional distribution of the position λ in which a process writes to R s in phase (s, i) is very close to the unconditional one, described in line 4. In particular, the probability that a process writes to the κ-

th position R s [κ] is O(1/2 κ ) = O(1/k s,i ).
It follows that any schedule by the adversary will result in an expected number of at least Ω(k s,i ) processes that write to R s in phase (s, i), and execute line 24 before process p * does. All these processes will be promoted to the critical section before the end of the phase, as the leader has to wait for p * in line 16 before it invokes a promote() operation in line 17, and thus it will see those Ω(k s,i ) processes (in expectation) when it scans through its backpack.

We now give the detailed proof. We define three sets of processes, K s,i , M s,i , and P s,i , as follows. Set K s,i consists of all processes that perform a good write to R s during phase (s, i). Set M s,i consists of the processes that write to R s between the beginning of phase (s, i), and the point right after the leader of the phase has either completed the κ-th iteration of the for-loop in lines 11-11, where κ := log(k s,i ) , or has broken out of the loop in line 13 (whichever of the two happens first). Note that K s,i ⊆ M s,i . Finally, set P s,i contains all processes p ∈ M s,i that write to array B s in line 24 before the leader invokes the promote() operation in line 17.

We let E be the event that for each position 1 ≤ j ≤ κ of array R s , at least one of the k s,i good write operations on R s during phase (s, i) is performed on register R s [j].

The following claim establishes that no process, which writes to R s in phase (s, i), can proceed past line 27, or, unless it is the leader of that phase, read an entry of R s , before the leader of that phase executes line 17.

Claim 7. Let t be some point after the leader w * of phase (s, i) finished line 9, but has not yet started line 17, and let c * be the value of c w * at that point. Then at point t, (a) no process other than w * has performed a read operation on R s since the beginning of the phase; and (b) for each process q = w * that has written to R s at some point t < t during phase (s, i):

(b1) at point t, q is poised to execute a shared memory step in line 6 or in one of lines 22-27; and (b2) if in interval [t , t] process q executes a read() or CAS() operation on S s in line 6 or 23, respectively, then this operation returns (w * , c * ), and if it executes line 25 during [t , t], then the if-condition in that line evaluates to true.

Between the beginning of phase (s, i) and the point when good interval I s,i ends, the leader does not access R s . Claim 7 implies that the position λ in R s , where a process p ∈ K s,i writes to when it executes line 5 during I s,i does not affect any other processes' steps, or p's steps starting with line 5 and until interval I s,i ends. Since the adversary does not know which position λ a process p chooses, and only the location of p's write to R s depends on λ, that random choice does not affect the schedule up to the point interval I s,i ends.

Fix some execution prefix E that ends at the beginning of good interval I s,i . In addition, fix all remaining random choices made by processes until the end of I s,i , except for the choice of λ that each process makes on side s. Then for every infinite sequence λ = (λ 1 , λ 2 , . . . ), the adversary schedules an execution that is uniquely determined by λ up to the end of I s,i , where the j-th process that executes line 4 on side s during I s,i chooses the value λ j in that line. Let E λ denote that unique execution up to the point when I s,i ends. Then we have that for any two λ, λ , the adversary cannot distinguish between E λ and E λ , and the only difference any process sees (if any) is the random value it chooses in line 4 on side s during I s,i . Since the adversary cannot distinguish between those two executions, K s,i is the same for both, and so is the order of all steps. Hence, κ is also fixed, and the probability of event E, that each of the values 1, . . . , κ is chosen at least once by processes in K s,i , is

Pr(E) = 1 -Pr( Ē) ≥ 1 - 1≤i≤κ (1 -1/2 i ) ks,i ≥ 1 - 1≤i≤κ e -ks,i/2 i ≥ 1 - j≥1 e -j = e -2 e -1 > 1 3 . (1)
(We used that κ = log(k s,i ) .)

Claim 8. If event E occurs, then the leader of phase (s, i) does not break out of the for-loop in lines 11-11 during the first κ iterations.

Let κ ≥ κ be the number of iterations of the for-loop in lines 11-11 completed by the leader of phase (s, i), without including the last iteration if it ends with a break. Let T be the point right after the end of the last iteration of the for-loop.

In the following we condition on event E and also on the value of κ . Note that E implies κ ≥ κ, by Claim 8.

We are interested in the conditional distribution of the λvalue of each process p ∈ M s,i , given E and κ = k, for k ≥ κ. At point T the adversary has no knowledge of those λ-values, except for what can be inferred from the value of κ . Hence, conditionally on events E and κ = k, the value of λ chosen by each p ∈ M s,i has no effect on the schedule and thus on p's steps during the interval starting with p's good write to R s and ending at point T . Then, for each p ∈ M s,i and 1 ≤ j ≤ κ, the probability that a given p ∈ M s,i chooses λ = j is

Pr(λ = j | E, κ = k) ≤ Pr(λ = j | E, κ = κ) = Pr(λ = j ∧ E | κ = κ) Pr(E | κ = κ) . Since Pr(λ = j ∧ E | κ = k) ≤ Pr(λ = j | κ = κ) ≤ Pr(λ = j | λ ≤ κ) ≤ (1/2 j )/(1 -1/2 j ), and
Pr(E | κ = κ) ≥ Pr(E) ≥ 1/3, by (1), it follows
Pr(λ = j | E, κ = k) ≤ (3/2 j )/(1 -1/2 j ). (2)
The next claim says that the leader will wait in line 16 until all processes in its f ound set (other than the leader itself) have executed line 24. 9. Let t 1 be the point when phase (s, i) begins, and t 2 > t 1 the point during phase (s, i) when the leader of that phase, w * , finishes the for-loop in line We are interested in the total number of processes p ∈ M s,i that execute line 24 until all processes in the leader's f ound set (other than the leader) have executed that line. This is lower bounded by the number Y of processes p ∈ M s,i that execute line 24 until the first process p * ∈ M s,i with λ p * = κ executes that line, provided that the λ-value of the leader is not κ.

After point T , the leader executes the loop in lines 15-16 throughout which all shared memory steps are reads of registers in the leader's own local memory segment, and thus do not incur RMRs. Hence, the adversary does not gain any information about how many iterations of the for-loop have been executed by the leader, until the leader finishes that loop. Therefore, to determine Y we can assume that the λ-value of each process p ∈ M s,i (other than the leader) remain unknown until the leader has finished its loop in lines [START_REF] Danek | Brief announcement: Local-spin algorithms for abortable mutual exclusion and related problems[END_REF][START_REF] Dijkstra | Solution of a problem in concurrent programming control[END_REF]. Given E and κ , the probability that any given process p ∈ M s,i (including the leader) chooses λ = κ is at most π = (3/2 κ )/(1 -1/2 κ ), by [START_REF] Aghazadeh | Making objects writable[END_REF]. From the union bound, the probability that neither the leader nor any of the first j -1 processes p ∈ M s,i that execute line 24 choose λ = κ is at least 1 -jπ. Thus, E[Y | E, κ ] is at least

j≥1 max {0, 1 -jπ} ≥ 2 κ (1 -1/2 κ ) 6 - 1 2 .
Therefore, the expected number of processes p ∈ M s,i that execute line 24 before the leader initiates a promotion is

E[|P s,i | | E] ≥ 2 κ (1-1/2 κ ) 6
-1 2 , and thus

E[|P s,i |] ≥ E[|P s,i | | E] • Pr(E) (1)
≥ 2 κ (1 -1/2 κ ) 18 - 1 6 . (3)
The next claim says that the leader and all p ∈ P s,i go through the critical section in phase (s, i). cl Claim 10. The leader of phase (s, i) finishes its lock() operation in the same iteration of its while-loop in which it becomes the leader, and each process q ∈ P s,i in the iteration of its while-loop in which it writes to R s for the first time during phase (s, i).

Since the leader does not belong to P s,i , it follows from Claim 10 and (3), that the expected total number of processes that go through the critical section in phase (s, i) is at least 2 κ (1-1/2 κ ) 18

-1 6 + 1 ≥ k s,i /36, as κ = log(k s,i ) . This completes the proof of Lemma 6.

We now have all the pieces we need to prove the main result of the section, the bound on the total number of RMRs.

Proof of Theorem 1: Recall, we have assumed w.l.o.g. that the adversary schedules exactly m invocations to the implemented lock() operation. We will bound the total number of RMRs until the point τ m when all those operations are completed. The total number of passages by processes through the critical section is also m. Thus, m = s,i s,i , where the summation is over all s ∈ {0, 1} and i ≥ 0 ( s,i = 0 if phase (s, i) does not exist). Since m is fixed and finite, it follows m = E[ s,i s,i ] = V. CONCLUSION For the CC model, there is currently no randomized algorithm that achieves constant RMR complexity. We believe that our techniques can be extended to the CC model. To achieve this, we are working on a mechanism that allows processes to join the backpack of a leader in a similar way as in our DSM algorithm. The naive algorithm requires the leader to scan an array of size n and incurs Ω(n) RMRs in the CC model, but we have a randomized technique that achieves something similar in O(1) RMRs. However, it is a technical challenge to combine this with the "oracle" mechanism of our DSM algorithm.

2 c 9 Lfailed to become a leader 22 AFigure 1 .

 29221 Figure 1. Lock Implementation.

Claim 4 .

 4 If during a promote() operation process w * finishes line 40 k ≥ 1 times, then during that promote() call at least k lock() calls respond and k release() calls get invoked.

16 .

 16 If at point t 2 , (r * , d * ) ∈ f ound w * and r * = w * , then r * writes (d * , trying) to B s [w * ][r * ] at some point t * ∈ [t 1 , t 2 ].

  thus might try to promote p. Then, in line 24, p tries to enter w's backpack by writing (c, trying) to B α [w][p]. In line 25, it reads A[w] to check whether w's backpack is still open. If not, p "gives up" and indicates that is not trying to get promoted anymore by writing (c, done) to B α [w][p], in line 29. Otherwise, in lines 26 and 27, p indicates that it is ready to get promoted by writing (c, waiting) to B α [w][p], and then it busy-waits on B α [p][w] until w promotes it. After that p can enter the critical section by returning from its lock() call, in line 28.

  Using that E[ s,i ] ≥ E[k s,i ]/36, from Lemma 6, gives m ≥ s,i E[k s,i ]/36 = E[ s,i k s,i ]/36.Further, from Lemma 5, we have for the total number W m of writes to arrays R 0 and R1 , E[W m ] ≤ 2 E[ s,i k s,i ].Combining this with the inequality above, yields E[W m ] ≤ 72m. The theorem now follows from this and Lemma 2, which bounds the total number of RMRs by O(W m ).

s,i E[ s,i ]..

A statement in[START_REF] Bender | Mutual exclusion with O(log 2 log n) amortized work[END_REF], saying that it is safe to replace the CAS objects with the implementation provided in[START_REF] Golab | RMRefficient implementations of comparison primitives using read and write operations[END_REF], for the reason that this implementation is strongly linearizable, is incorrect. Strong linearizability[START_REF] Golab | Linearizable implementations do not suffice for randomized distributed computation[END_REF] only preserves the power of the strong adaptive adversary, but there are examples showing that it does not in general preserve the power of the oblivious adversary.

ACKNOWLEDGEMENTS

This research was undertaken, in part, thanks to funding from the Canada Research Chairs program, the Discovery Grants program of NSERC, and the INRIA Associate Team RADCON.


Jean-Paul Gauthier
email: gauthier@univ-tln.fr

Felipe Monroy-P Érez Dedicated

Siddhārtha Gautama

ON CERTAIN HYPERELLIPTIC SIGNALS THAT ARE NATURAL CONTROLS FOR NONHOLONOMIC MOTION PLANNING

Keywords: Mathematics Subject Classification. 49J15, 93C15 Motion planning, nonholonomic systems, subriemannian geometry

In this paper we address the general problem of approximating, in a certain optimal way, non admissible motions of a kinematic system with nonholonomic constraints. Since this kind of problems falls into the general subriemannian geometric setting, it is natural to consider optimality in the sense of approximating by means of subriemannian geodesics. We consider systems modeled by a subriemannian Goursat structure, a particular case being the well known system of a car with trailers, along with the associated parallel parking problem. Several authors approximate the successive Lie brackets by using trigonometric functions. By contrast, we show that the more natural optimal motions are related with closed hyperelliptic plane curves with a certain number of loops.

Introduction

The nonholonomic motion planning problem has attracted the attention of researchers for more than thirty years. It is out of the scope of this paper to provide a complete bibliography on the subject. We limit ourselves to mention a short bibliography which is related to our approach. Roughly speaking the literature can be separated in two different but complementary approaches: the one that proposes methods for motion planning based upon typical input signals such as constant controls, polynomial controls, trigonometric controls, etc., for instance H. Sussmann et al. [START_REF] Sussmann | Motion planning for controllable systems without drift[END_REF][START_REF] Sussmann | Lie bracket extensions and averaging: the single bracket generating case[END_REF], and R. Murray et al. [START_REF] Tilbury | Trajectory generation for the n-trailer problem using Goursat normal form[END_REF][START_REF] Tilbury | Steering car-like systems with trailers using sinusoids[END_REF]; and the one that pursues the formalization of the motion planning problem through the concepts of complexity, entropy and nilpotent approximations, for instance the pioneering work of F. Jean [START_REF] Jean | Complexity of Nonholonomic Motion Planning[END_REF][START_REF] Jean | Entropy and Complexity of a Path in subriemannian Geometry[END_REF][START_REF] Jean | Measures and transverse paths in subriemannian geometry[END_REF] and the series of papers of one of the authors [START_REF] Boizot | Motion Planning for Kinematic Systems[END_REF][START_REF] Boizot | On the Motion Planning of the Ball with a Trailer[END_REF][START_REF] Gauthier | On the motion planning problem, complexity, entropy and nonholonomic interpolation[END_REF][START_REF] Gauthier | Motion planning and fastly oscillating controls[END_REF][START_REF] Romero-Melendez | On Complexity and Motion Planning for Corank one Sub-riemannian Metrics[END_REF][START_REF] Gauthier | On the Codimension One Motion Planning Problem[END_REF][START_REF] Gauthier | On the one-step-bracket-generating motion planning problem[END_REF].

The main idea we want to get across in this paper is that there is a natural class of input signals and admissible trajectories, that solves the motion planning problem in an optimal sense that shall be explained in the paper. In contrast with the extrinsic signals considered in the literature, the signals we propose are given by certain periodic hyperelliptic functions and are obtained intrinsically out of some invariants of the nilpotent approximation of the system. In the papers [START_REF] Boizot | Motion Planning for Kinematic Systems[END_REF] and [START_REF] Boizot | On the Motion Planning of the Ball with a Trailer[END_REF] some preliminary results were given in this direction, for systems involving Lie brackets up to order 3. Furthermore, the results in these papers strongly suggest a regular pattern for the signals, namely, the length of the Lie brackets of highest order, determines the number of loops of the hyperelliptic curve, concurrently it is natural to conjecture about the shape of the optimal signals in the general case.

In this paper we prove the conjecture on the shape of the optimal signals in the case of systems with two controls, that correspond to the so-called Goursat structures, that is, systems for which the higher order of the Lie brackets involved is exactly equal to the dimension of the state manifold plus two.

This class of systems includes the well known models for a car with trailers along with the so-called parallel parking problem. At the level of this example, and in accordance with the aforementioned literature, two points of view for the motion planning problem become apparent:

(1) The one that starts by observing that the system is exactly feedback equivalent to the Goursat system in chained form, and then by driving the system by means of extrinsic inputs, such as sinusoids. [START_REF] Sussmann | Lie bracket extensions and averaging: the single bracket generating case[END_REF] The one that reduces the problem to the successive nilpotent approximations of the system along the curve to approximate.

It is worth mentioning that in this case, the nilpotent approximation coincides with the Goursat system and the system is, in the subriemannian context, feedback equivalent to its nilpotent approximation, situation that does not occur in the general cases treated in our previous papers. At this point it is clear that there is a polemic ingredient in the picture, namely, which are the best possible signals for driving these class of systems? Whereas most of the authors approximate brackets by sequences of trigonometric signals, or piecewise constant signals, our approach leads to an intrinsic natural class of control signals and state trajectories that are optimal in the sense of nonholonomic interpolation. Therefore we claim that ours are the best signals to approximate the brackets at any order.

The papers [START_REF] Boizot | Motion Planning for Kinematic Systems[END_REF][START_REF] Boizot | On the Motion Planning of the Ball with a Trailer[END_REF] and [START_REF] Gauthier | On the motion planning problem, complexity, entropy and nonholonomic interpolation[END_REF] tackle the generic motion planning problem that involves brackets of order less or equal to three. By contrast, in the present paper we treat the highly nongeneric case of the Goursat flag, but for brackets of any order.

Our conclusions for brackets of order 1, 2 and 3 are roughly summarized by the curves in figure 1, which shows, for a generic subriemannian metric, (with flag (2, 3), [START_REF] Sussmann | Lie bracket extensions and averaging: the single bracket generating case[END_REF][START_REF] Tilbury | Trajectory generation for the n-trailer problem using Goursat normal form[END_REF][START_REF] Tilbury | Steering car-like systems with trailers using sinusoids[END_REF], and (2, 3, 5, 6) respectively), the projection of the motion along the non-admissible curve to be approximated, on the plane of the distribution (the plane of admissible motions) in certain coordinates called normal coordinates. In these normal coordinates, the motion for one bracket is a circle, the curve for two brackets is the well-known periodic elastica, see for instance [START_REF] Love | A treatise on the mathematical theory of elasticity[END_REF], and the one for three brackets is a closed three loops universal hyperelliptic curve. A kinematic example associated to this last hyperelliptic curve corresponds to the motion planning of the ball with a trailer discussed in [START_REF] Boizot | On the Motion Planning of the Ball with a Trailer[END_REF]. The interested reader is invited to see the animation showing this motion in http://www.lsis.org/boizotn/KinematicVids/.

Another interesting picture showed in figures 2 and 4 is a peanut shape curve that we shall call the cacahuète, the vertical coordinate is the first control and the horizontal coordinate is one of the normal coordinates in the distribution.

It is completely natural to conjecture that the series depicted by the cacahuètes and the corresponding closed multi loops curves persists. Although our intuition points out in that direction, up to now it is not clear if such persistence remains in general. The aim of this paper is to show in a constructive way, that for Goursat The organization of the paper is as follows: in section 2 we set our notations, give the precise statement of the problem and summarize some preliminary results from the papers [START_REF] Boizot | Motion Planning for Kinematic Systems[END_REF][START_REF] Boizot | On the Motion Planning of the Ball with a Trailer[END_REF][START_REF] Gauthier | On the motion planning problem, complexity, entropy and nonholonomic interpolation[END_REF] and [START_REF] Gauthier | Motion planning and fastly oscillating controls[END_REF] in connexion with generic cases of small coranks. We also introduce special coordinates adapted to the problem and reformulate, for the Goursat case, a result that allows to reduce the interpolation entropy to the nilpotent approximation. At the end of the section, we present our main result along with some remarks on the interpolation entropy methodology that are important in applications. In section 3 we show that there is essentially only one left invariant Goursat subriemannian structure, and complete the proof of the main result by dealing with the integrability of Goursat structures, following the integration process developed in [START_REF] Anzaldo-Meneses | Goursat distributions and sub-riemannian structures[END_REF]. In section 4 some explicit computations in coordinates for optimal curves are carried out. In section 5, using the integrability results and the explicit formulae for extremals, we show that the conjecture about the persistence of the geometric pattern of optimal trajectories certainly holds in the Goursat case. In Section 6, we derive some conclusions and pose two challenging questions that still remain open.

The Goursat motion planning problem

In this section we present the notations used in the paper, the summary of the known results for the generic case, the description of the Goursat motion planning, the statement of the problem and our results.

Notations and preliminary results.

We present in this paragraph the general lines of the subriemannian entropy interpolation theory, for details we refer the reader to the series of papers [START_REF] Boizot | Motion Planning for Kinematic Systems[END_REF][START_REF] Boizot | On the Motion Planning of the Ball with a Trailer[END_REF][START_REF] Gauthier | On the motion planning problem, complexity, entropy and nonholonomic interpolation[END_REF][START_REF] Gauthier | Motion planning and fastly oscillating controls[END_REF][START_REF] Romero-Melendez | On Complexity and Motion Planning for Corank one Sub-riemannian Metrics[END_REF]. As customary, we work in the smooth category and the genericity we refer to is with respect to the Whitney topology.

A rank-2 subriemannian metric over a n-dimensional manifold M is a pair (∆, g) where ∆ is a 2-dimensional vector-distribution on M , and g is a Riemannian metric over ∆. Equivalently, the metric is specified by the following control system over M

(2.1) (Σ) ẋ = F 1 (x)u 1 + F 2 (x)u 2 ,
in such a way that the vector fields F 1 and F 2 form an orthonormal frame for g. Geodesic curves (length minimizing curves) are those which minimize the functional

(2.2) C 1 (u) = T 0 (u 1 (t)) 2 + (u 2 (t)) 2 dt,
in free time, or equivalently the functional

C 2 (u) = T 0 ((u 1 (t)) 2 + (u 2 (t)) 2 ) dt,
in fixed time T . The interpolation entropy of a path Γ : [0, T Γ ] → M transversal to the distribution ∆ was introduced by J.P. Gauthier and V. Zakalyukin in [START_REF] Gauthier | On the motion planning problem, complexity, entropy and nonholonomic interpolation[END_REF], following the pioneering work of F. Jean in [START_REF] Jean | Entropy and Complexity of a Path in subriemannian Geometry[END_REF]; this concept is related to the Kolmogorov entropy of a path, considering it as a metric space with respect to the subriemannian metric.

For any ε > 0 consider ℓ(ε) the minimum subriemannian length of a Σ-admissible curve that interpolates Γ by means of pieces of sub-riemannian length ≤ ε, the function ℓ(ε) tends to infinity when ε tends to zero. The ε-interpolation entropy of Γ, denoted as E Σ Γ (ε), is the leading term of ε -1 ℓ(ε), (modulo the equivalence relation ℓ 1 (ε) ≈ ℓ 2 (ε) if and only if lim ε→0 ℓ1(ε) ℓ2(ε) = 1).

For a generic pair (Σ, Γ) with ∆ a p-step bracket generating distribution and Γ a transversal path to ∆, the entropy has an expression of the form E Σ Γ (ε) = a ε p . However this is true only in the absence of codimension 1 generic singularities, in which case one has E Σ Γ (ε) =ln(ε) a ε p . The generic expression of the constants a has been exhausted for small values of the ranks and co-ranks. For details we refer the reader to the aforementioned papers where proofs are always constructive.

Approaching the motion planning problem (Σ, Γ) by means of the subriemannian formalism and the interpolation entropy of Γ provides a natural optimal way to approximate Lie brackets, issue that is fundamental in control theory, and that has been addressed by a number of people using trigonometric control signals u 1 and u 2 for the approximation. We claim that sinusoids are pertinent for first order Lie brackets only, but far from being optimal for higher order Lie brackets. In the recent work [START_REF] Gauthier | Minimal Complexity Sinusoidal Controls for Path Planning, submitted to CDC[END_REF], which has strong connections with the present paper, we argue about the use of Lissajous like controls for approximating high order Lie brackets in the free nilpotent Lie algebra associated with F 1 and F 2 .

Given a generic pair (Σ, Γ), the behavior of the system along Γ is dominated by what we call nilpotent approximation of the system along Γ, roughly speaking it can be viewed as a one parameter family of nilpotent approximations of the system at the points of Γ. For the concept of nilpotent approximation, we refer the reader to A. Bellaïche [START_REF] Bellaiche | The Tangent Space in Sub-Riemannian geometry[END_REF].

The standard concept of nilpotent approximation at a point relies on the socalled adapted coordinates, that can be obtained by polynomial transformations from any coordinate system, while our concept of nilpotent approximation along a curve relies on normal coordinates which are the subriemannian analog of the normal coordinates in Riemannian geometry. In normal coordinates, the curve Γ is rectified to become a vertical line given by the last coordinate, whereas the distribution along Γ is realized by the horizontal plane given by the first two coordinates. The results in the rank 2 case are summarized in the following: Theorem 1. (Rank 2, generic couple (Σ, Γ)). The curves that minimize the entropy (maximize the displacement in the direction of Γ) are (small modifications of ) those that minimize the entropy of the nilpotent approximation along Γ. The horizontal projections of these entropy-minimizing curves are the following closed plane curves (shown in figure 1): case 1: corank 1 (n = 3, Dubins car) circle, case 2: corank 2 (n = 4, car with a trailer) periodic elastica, corank 3 (n = 5, ball rolling on a plane) periodic elastica, case 3: corank 4 (n = 6, ball with a trailer) 3-loops hyperelliptic curve.

Remark 1. In all cases, the curves are universal once normalized to have length one, although they should be of length ε. This asymptotic result is obtained for ε → 0, and is dominated by the nilpotent approximation which is defined out of a gradation of the involved variables and their corresponding derivatives, and consequently has a certain quasi-homogeneity property (with respect to the gradation). This property allows to obtain the ε-optimal curves by means of quasi-homogeneous dilations from the curves described in the theorem.

Remark 2. In case 3 we were not able to show the result in the general corank 4 case. We proved it only in the case of (the nilpotent approximation of ) the ball with a trailer. Surprisingly in that case the system that yields the geodesics is Liouvilleintegrable, while in the general corank 4 case it is not.

2.2. The Goursat case.

2.2.1.

Preliminaries. This section presents the main result of the paper on the non-holonomic interpolation problem on Goursat structures.

Associated with a 2-dimensional (in fact, to any) distribution ∆ on a n dimensional manifold M , the following two flags of distributions

∆ i : ∆ 0 = ∆, ∆ i+1 = [∆, ∆ i ], D i : D 0 = ∆, D i+1 = [D i , D i ]
are well defined.

We assume that pair (∆, Γ) with ∆ a bracket generating distribution and Γ a transversal curve to ∆ is given once for all. Such a pair shall be called Goursat pair if all the distributions D i , ∆ i have rank strictly less than n, and are minimalequiregular in the following sense: all the distributions D i , ∆ i have constant rank r i along Γ with r 0 = 2, r 1 = 3, r i+1 = r i + 1 as long as r i ≤ n. A distribution ∆ is usually called Goursat distribution if satisfies the minimal-equiregularity condition in all M .

Goursat distributions have been in the literature for long, apparently they were introduced by E. von Weber [START_REF] Weber | Zur Invariantentheorie der Systeme Pfaff'scher Gleichungen.Berichte über die Verhandlungen der Königlich Sächsischen Gesellshaft der Wissenshaften[END_REF] at the beginning of the last century within the general framework of differential equations. This class of distributions has been incorporated into the geometric control theory literature partly because it provides good models for the study of certain kinematic systems, such as the one of the car with trailers. Proposition 1. [START_REF] Weber | Zur Invariantentheorie der Systeme Pfaff'scher Gleichungen.Berichte über die Verhandlungen der Königlich Sächsischen Gesellshaft der Wissenshaften[END_REF] The dimension n being fixed, there is a single Goursat distribution, up to a (local) diffeomeorphism, generated by the two following (local) vector fields:

(2.3)          X 1 = ∂ ∂x 1 , X 2 = n i=2 (x 1 ) i-2 (i -2)! ∂ ∂x i .
This result endows M = R n with the structure of (n -1)-step nilpotent Lie algebra, by considering the generating relations:

(2.4)

X i = [X 1 , X i-1 ], i = 3, . . . , n
as the only non-vanishing Lie brackets. The exponential mapping establishes a local diffeomorphism onto a (n -1)-step nilpotent simply connected Lie group, that we shall call the Goursat group.

Remark 3. The normal form (2.3) is the not the usual one that commonly appears in the literature, but is shown in [START_REF] Anzaldo-Meneses | Goursat distributions and sub-riemannian structures[END_REF] that they are diffeomorphic.

Remark 4. It is clear that the problem of parallel parking of a car with n -3 trailers reduces to the problem of ε-approximating (or ε-interpolating) the trajectory of the vector field

X n = [X 1 , X n-1 ]
, that is, the x n -axis, by means of an admissible trajectory.

A Goursat motion planning problem on a n dimensional manifold M is a triple G = (∆, g, Γ) where (∆, g) is a subriemannian structure on M and (∆, Γ) is a Goursat pair. A one parameter family of admissible curves γ ε realizing the interpolation entropy of the curve Γ is in a sense the optimal way to approximate Γ by ε-close admissible curves.

In this paper we give a general solution to the Goursat motion planning, and show that the solution generalizes the generic cases described in Theorem 1. Since everything is local and because of Proposition 1, there is no loss of generality in assuming that M = R n with coordinates x = (x 1 , . . . , x n ). We shall proceed in three steps:

(1) We define and compute the nilpotent approximation of G along Γ.

(2) We show that computing the entropy reduces to computing that of the nilpotent approximation. (3) We solve the corresponding optimal control problem, which is possible due to Liouville integrability of the corresponding Hamiltonian system. The two first steps are carried out in the two next paragraphs.

2.2.2.

Nilpotent approximation of G along Γ. The data G = (∆, g, Γ) is given, with ∆ = span{F 1 , F 2 } a Goursat distribution and Γ a smooth curve tranversal to ∆. The vector fields F 1 , F 2 define the control system (2.1), that we shall write simply as Σ = (F 1, F 2).

Σ is feedback equivalent to the normal form (2.3) therefore there exist functions α, β, γ, δ with αδβγ nowhere vanishing, and local coordinates x = (x 1 , . . . , x n ), that we shall call Goursat coordinates, such that

F 1 (x) = α(x)X 1 (x) + β(x)X 2 (x), F 2 (x) = γ(x)X 1 (x) + δ(x)X 2 (x). Generically the curve Γ : [0, S] → R n , s → Γ(s) = (γ 1 (s), . . . , γ n (s)) is transver- sal to ∆ n-3 = D n-3 , therefore γ ′
n (s) = 0 and we can make the following change of coordinates: In what follows, we consider that the change of coordinates has been carried out, and we shall omit the tilde symbol in both the coordinates and the curve.

(2.5) xi = x i -γ i • γ -1 n (x n ), for i = 1, . . . , n -
For an arbitrary but fixed point Γ(s) on the curve Γ, the coordinates x 1 , . . . , x n-1 are centered at zero but x n is not. Assuming that the last coordinate is small, we consider the gradation in the formal power series in the variables x 1 , . . . , x n-1 , x nγ n (s) obtained by assigning weight 1 to both x 1 and x 2 , weight 2 to x 3 , weight 3 to x 4 , . . ., weight (n -2) to x n-1 and weight (n -1) to x nγ n (s). This gradation induces a gradation in the formal vector fields in such way that both weight -(n -1). This gradation is homogeneous with respect to the Lie bracket operation along the curve Γ. We define the Goursat nilpotent approximation Σ = ( F 1 , F 2 ) of Σ along Γ to be the homogeneous term of order -1 of the gradation, that is,

(2.6)      F 1 = α(Γ(s))X 1 (x 1 ) + β(Γ(s))X 2 (x 1 ) + O 0 = F 1 x=Γ(s) + O 0 , F 2 = γ(Γ(s))X 1 (x 1 ) + δ(Γ(s))X 2 (x 1 ) + O 0 = F 2 x=Γ(s) + O 0 .
As customary, O n denotes a vector field of order n. A function of order n is a function contained in the n th power of the ideal generated by x 1 , . . . , x n-1 , x nγ n (s).

For both, the system Σ and its nilpotent approximation Σ, we have the following rough estimates, for admissible curves x : [0, T ] → R n , t → (x 1 (t)x 2 (t), . . . , x n (t)) with initial point on Γ (x(0) ∈ Γ), and (subriemannian) length

l(ε) = T 0 (u 1 (t)) 2 + (u 2 (t)) 2 ≤ ε: |x i (t)| ≤ kε, i = 1, 2; (2.7) |x i (t)| ≤ kε i-1 , i = 3, n -1; |x n (t) -x n (0)| ≤ kε n-1 , (2.8)
with an appropriate constant k.

2.2.3.

Equivalence between entropy of the system and that of its nilpotent approximation. Since the estimates in this paragraph are similar to those of the generic cases of small coranks, we shall give here only the general lines of the proof, the interested reader can see more details in [START_REF] Gauthier | On the motion planning problem, complexity, entropy and nonholonomic interpolation[END_REF].

For the same control functions u 1 (t), u 2 (t) we consider two admissible curves x(t) and x(t), t ∈ [0, T ] of the systems Σ and and Σ respectively. Further we assume that both curves have length ≤ ε and the same initial point x(0) = x(0) ∈ Γ. Set e(t) = x(t)x(t)

First for i = 1, 2 we have

ėi (t) = O 1 , therefore |e i (t)| ≤ kε 2 , i = 1, 2;
now for i > 2 we have

| ėi (t)| ≤ |(x 1 ) i-2 -( x 1 ) i-2 | (i -2)! + O i-1 ,
as a consequence, taking into account (2.7), we have that

|e i (t)| ≤ kε i , i = 3, . . . , n,
of course there is no loss of generality assuming that the constant k is the same as in the rough estimates (2.7).

This means that the subriemannian distance between x(t) and x(t) relative to either Σ or Σ, is smaller than kε (1+ 1 n-1 ) , that is,

(2.9) d(x(t), x(t)) ≤ kε (1+ 1 n-1 )
.

With these estimates in hand, we can choose now a curve x(t) : [0, θ] → R n that ε-interpolates Γ by maximizing x n (θ), and applying the previous inequality to the interpolating pieces, we get that (2.10)

E Σ Γ (ε) ≤ E Σ Γ (ε).
In this line of argumentation we can interchange the role of x and x to get finally that:

(2.11)

E Σ Γ (ε) ≈ E Σ Γ (ε) 2.3.
Statement of the main result. Before stating the theorem, it is worth pointing out that our result can be understood and utilized in practical applications of motion planning, under two completely different viewpoints:

• One may think that the Goursat system is given, the car with trailers for instance, and that it is put via feedback and change of coordinates under the canonical form (2.3). After that, one chooses to apply the interpolation entropy strategy. This procedure shall provide an exact ε-interpolation control strategy, but with a non-natural cost (due to the preliminary feedback). It is equivalent, after feedback, to solve the problem of finding admissible εinterpolating curves that have an arbitrary but fixed subriemannian length given by (2.2), and that maximize the distance on Γ between two successive interpolated points. Under this strategy the actual size of ε is irrelevant. • The other viewpoint is to consider any subriemannian metric whatsoever over the Goursat distribution, and to apply without preliminary feedback, the interpolation entropy strategy for small ε. In such a case, the metric is free, but the result is asymptotic only (when ε → 0). It is noticeable that the (asymptotic) result is in fact independent of the chosen metric.

Our result is the following:

Theorem 2. (In Goursat coordinates, for model 2.6 or for its nilpotent approximation Σ.) A length one extremal of the interpolation problem between the origin and a point of the x n axis, maximizing the endpoint coordinate x n can be explicitly calculated. Its projection on the plane (x 1 , x 2 ) is a closed hyperelliptic curve, smooth-periodic, with n -2 loops, shown on figure 3 for n = 6, 7. The curve that interpolates with length ε is obtained from this one by homogeneity.

According to the estimates in paragraphs 2.2.2 and 2.2.3, what remains to be done is to find the explicit equations for the extremals along with the corresponding projections. The key point for proving this result is the fact that the Hamiltonian system of geodesic equations of the Goursat model is Liouville integrable whatever the dimension n. We carry this out in the next section, following the integration process developed in [START_REF] Anzaldo-Meneses | Goursat distributions and sub-riemannian structures[END_REF].

Extremal curves for the Goursat Case

3.1. The optimal control problem. As explained in the paragraph 2.1, in general the subriemannian geodesic problem on a subriemannian manifold is tantamount to an optimal control problem with quadratic cost. For our data G = (∆, g, Γ) we deal with a left invariant optimal control problem on the Goursat Lie group G. This Lie group can be identified with R n with the group law defined as follows, if g 1 = (x 1 , . . . , x n ) and g 2 = (y 1 , . . . , y n ) are two elements in G, then g 1 ⊕ g 2 = (z 1 , . . . , z n ) with:

(3.1)            z 1 = x 1 + y 1 , z 2 = x 2 + y 2 , and
z k = x k + y k + k-1 j=2 x k-j 1 (k -j)! y j , for k = 3, . . . , n,
and the group identity e = (0, . . . , 0). The vector fields in the normal form (2.3) are ⊕-left invariant, and, as mentioned before, G is a simply connected n-step nilpotent Lie group with Lie algebra g, whose basis is defined by means of the commuting relations (2.4). At the level of the nilpotent approximation of the left invariant control problem we deal with is the following: among the admissible trajectories of the system

(3.2) ġ = u 1 (αX 1 (g) + βX 2 (g)) + u 2 (γX 1 (g) + δX 2 (g)), g ∈ G,
with αδβγ = 0, find the one that minimizes

(3.3) (u 1 (t) 2 + u 2 (t) 2 ) dt.
As it is explained in the papers ( [START_REF] Boizot | Motion Planning for Kinematic Systems[END_REF][START_REF] Boizot | On the Motion Planning of the Ball with a Trailer[END_REF][START_REF] Gauthier | On the motion planning problem, complexity, entropy and nonholonomic interpolation[END_REF]), we have to find a minimizing geodesic of length 1 (homogeneity) connecting the origin to a point on the x n axis. Since the rotation R ϕ preserves the metric it is enough to consider the constant transformation given by T , in such a case the system (3.2) writes as follows

(3.4) ġ = (aX 1 (g) + bX 2 (g)) u 1 + cX 2 (g) u 2
and in coordinates we have

(3.5)          ẋ1 = au 1 , ẋ2 = bu 1 + cu 2 , and ẋk = b x k-2 1 (k -2)! u 1 + c x k-2 1 (k -2)! u 2 , for k = 3, . . . , n.
We consider the change of coordinates

g = (x 1 , . . . , x n ) → g = ( x 1 , . . . , x n ), given by (3.6)                x 1 = 1 a x 1 , x 2 = - b ca x 1 + 1 c
x 2 , and

x k = - b ca k-1 x k-1 1 (k -1)! + 1 ca k-2 x k for k = 3, . . . , n, a straightforward computation yields (3.7) ˙ g = u 1 X 2 ( g) + u 2 X 2 ( g),
as can be easily verified. Furthermore the left invariance of the vector fields X 1 and X 2 implies that for any h ∈ G we have

(3.8) DL h ( ˙ g), DL h ( ˙ g) = ˙ g, ˙ g = u 2 1 + u 2 2
, where h → L h is the left translation.

We summarize the result:

Theorem 3. Given a Goursat triple G = (∆, g, Γ), we can choose coordinates along Γ and orthonormal vector fields F 1 , F 2 generating ∆, such that the nilpotent approximation along Γ writes ẋ = X 1 (x)u 1 + X 2 (x)u 2 , and Γ(s) = (0, . . . , 0, ϕ(s)) for some smooth function ϕ(s).

Lemma 1. The map : G → G, g → g is an automorphism of G.
Proof. From the definition (3.6) it is clear that g → g is a diffeomorphism. Let g 1 = (x 1 , . . . , x n ) and g 2 = (y 1 , . . . , y n ) be two arbitrary elements in G and let g 1 ⊕ g 2 = (z 1 , . . . z n ). If we denote as g 1 = ( x 1 , . . . , x n ), g 2 = ( y 1 , . . . , y n ) and g 1 ⊕ g 2 = ( z 1 , . . . z n ) the corresponding images, then the first two coordinates of g 1 ⊕ g 2 are given by

x 1 + y 1 = 1 a x 1 + 1 a y 1 = z 1 , x 2 + y 2 = - b ca x 1 + 1 c x 2 + - b ca y 1 + 1 c y 2 = z 2 ,
whereas for its k th coordinate, with k = 3, . . . , n we have

x k + y k + k-1 j=2 x k-j 1 (k -j)! y j = - b ca k-1 x k-1 1 (k -1)! + 1 ca k-2 x k - b ca k-1 y k-1 1 (k -1)! + 1 ca k-2 y k + k-1 j=2 x1 a k-j (k -j)! - b ca j-1 y j-1 1 (j -1)! + 1 ca j-2 y j = - b ca k-1   x k-1 1 (k -1)! + k-1 j=2 x k-j 1 (k -j)! y j-1 1 (j -1)! + y k-1 1 (k -1)!   + 1 ca k-2   x k + y k + k-1 j=2 x k-j 1 (k -j)! y j   = - b ca k-1 (x 1 + y 1 ) k-1 (k -1)! + 1 ca k-2   x k + y k + k-1 j=2 x k-j 1 (k -j)! y j   = z k . It follows that g 1 ⊕ g 2 = g 1 ⊕ g 2
Now, a (weak) corollary of Theorem (3) and Lemma (1) is the following Corollary 1. In the Goursat group, up to automorphisms, there is only one subriemannian left invariant metric that is defined by the normal form (2.3) with X 1 and X 2 orthonormal.

3.3. The entropy. Going back to the motion planning problem, we observe first that the automorphism (3.6) essentially does not change the reference path since now we have s → Γ(s) = (0, . . . , 0, 1 ca n-2 γ n (s)), and a formula for the entropy can be explicitly written.

In fact, if ω is the 1-form that vanishes on the distribution ∆ (n-2) and which satisfies ω(X n-1 ) = 1 where

X n-1 = [X 1 , X n-2 ], then by denoting f (s) = ω( Γ(s)) we have (3.9) E(ε) ≈ E(ε) ≈ Γ f (s) ds • A n ε n
where A n is a universal constant that depends on the dimension n only.

3.4. Application of the Pontryagin Maximum Principle. We now tackle the left invariant optimal control problem on the Goursat group G consisting of the minimization of the functional

(3.10) u 2 1 + u 2 2 ,
among the admissible trajectories of the left invariant control system

(3.11) ġ = u 1 X 1 (g) + u 2 X 2 (g),
with X 1 and X 2 given by the normal form (2.3) and satisfying the commuting relations (2.4), the Lie algebra of G is denoted as g and can be identified with T e G.

As it is well known, Pontryagin maximum principle provides a standard geometric tool for the description of extremals by establishing necessary conditions for optimality, for details we refer the reader to ( [START_REF] Agrachev | A Control Theory from the Geometric Viewpoint[END_REF]).

If p denotes the dual variable in g * , then for each vector field X i we have the corresponding Hamiltonian H i = p, X i , i = 1, . . . n with Poisson brackets satisfying commuting relations dual to those of (2.4), that is, (3.12)

H i = {H 1 , H i-1 }, i = 3, . . . n.

Maximality condition of the Pontryagin Maximum Principle yields

u 1 = H 1 , and u 2 = H 2 , and the system Hamiltonian becomes quadratic

H = 1 2 (H 2 1 + H 2 2
), the associated adjoint equations are obtained by differentiating along the extremal as customary: Ḣi = {H i , H}. In consequence, the commuting relations (3.12) clearly yield

Ḣ1 = H 2 H 3 (3.13) Ḣ2 = -H 1 H 3 (3.14) Ḣ3 = -H 1 H 4 (3.15) . . . Ḣi = -H 1 H i+1 (3.16) . . . Ḣn-3 = -H 1 H n-2 (3.17) Ḣn-2 = -H 1 H n-1 (3.18) Ḣn-1 = -H 1 H n (3.19) Ḣn = 0 (3.20)
Therefore H n is constant along extremals and shall be denoted

c 1 := H n = H n (0).
1 2! H 2 n-1 -c 1 H n-2 = 0
Another conservation law is then obtained as

c 2 := 1 2! H 2 n-1 (0) -c 1 H n-2 (0) Now starting from the polynomial equation in the variables (H n-1 , H n-2 ) (3.21) 1 2! H 2 n-1 -c 1 H n-2 -c 2 = 0,
and using the adjoint system, a further conservation law can be generated by multiplying for Ḣn-1 :

1 2! H 2 n-1 Ḣn-1 -c 1 H n-2 Ḣn-1 -c 2
Ḣn-1 = 0, for then equations (3.18) and (3.17) imply

d dt 1 3! H 3 n-1 -c 2 1 H n-3 -c 2 H n-1 = 0.
In consequence, another conservation law c 3 is obtained and the procedure can continue with a polynomial equation in the variables (H n-1 , H n-3 )

1 3! H 3 n-1 -c 2 1 H n-3 -c 2 H n-1 -c 3 = 0.
Following this procedure of multiplying by Ḣn-1 and integrating, an extra conservation law is obtained at each step j, together with a polynomial equation in the variables (H n-1 , H n-j ) with j = 2, . . . , k. For instance, next step yields c 4 together with the polynomial equation in the variables (H n-1 , H n-4 )

1 4! H 4 n-1 -c 3 1 H n-4 - c 2 2! H 2 n-1 -c 3 H n-1 -c 4 = 0.
The last two steps of this process make use of equations (3.15) and (3.14) and (3.14) and (3.13) respectively. By performing the corresponding integration the conservation laws c k-1 and c k are obtained, together with the polynomial equations in the variables (H n-1 , H 3 ) and (H n-1 , H 2 )

1 (k -1)! H k-1 n-1 -c k-2 1 H 3 - k-1 j=2 c j (k -1 -j)! H k-1-j n-1 = 0 and (3.22) 1 k! H k n-1 -c k-1 1 H 2 - k j=2 c j (k -j)! H k-j n-1 = 0, (3.23)
respectively. In conclusion we have the following This fact is very useful and it is illustrated in the figure [START_REF] Jean | Complexity of Nonholonomic Motion Planning[END_REF], where the intersection of these two cylinders is shown.

Computations in coordinates

In this section we change the notation having in mind some applications, we write the dimension as n = 2 + k, and the coordinates as (x, y, θ 1 , . . . , θ k ). The corank k distribution is given by the normal form (2.3), that in these coordinates writes as follows:

X 1 = ∂ ∂x , X 2 = ∂ ∂y + x ∂ ∂θ 1 + x 2 2! ∂ ∂θ 2 + x 3 3! ∂ ∂θ 3 + • • • + x k k! ∂ ∂θ k .
The Lie algebra generated by {X 1 , X 2 } satisfies the commuting relations (2.4), and is isomorphic to the (k + 1)-step nilpotent Goursat Lie algebra g. The control system (Σ) in these coordinates is written as follows:

ẋ = u 1 ẏ = u 2 θ1 = xu 2 θ2 = x 2 2! u 2 θ3 = x 3 3! u 2 . . . θk = x k k! u 2
The Pontryagin maximum principle applies in the same lines as before, to obtain that along extremals one has ẋ = H 1 , ẏ = H 2 and θj = H 2 x j j! Lemma 2. H n-1 is a linear function of x. Moreover x and ẏ are periodic functions of time.

Proof. In fact equation (3.19) writes Ḣn-1 = -c 1 H 1 = -c 1 ẋ.

In consequence:

H n-1 = H n-1 (0) -c 1 (x -x(0)).
Without loss of generality we can assume that c 1 = H n = H n (0) = -1 and H n-1 (0) = x(0) = 0 in such a way that H n-1 may be identified with x.

4.1. The hyperelliptic curve. Following the inductive procedure explained in paragraph (3.5) and assuming that c 1 = -1 we can write equations (3.23) and (3.22) as follows:

H 3 = - 1 (k -1)! x k-1 + k-1 j=2 c j (k -1 -j)!
x k-1-j =: p k-1 (x), (4.1)

H 2 = - 1 k! x k + k j=2 c j (k -j)! x k-j =: p k (x). (4.2)
Here and in the remaining of the paper the subindex of a polynomial denote its degree. For then a further derivation of equation (3.19) together (3.13) yield ẍ = Ḣ1 = H 2 H 3 = p k (x)p k-1 (x) =: q k(k-1) (x), and by multiplying both sides by ẋ one gets ( ẋ) 2 = r k(k-1)+1 (x). As a consequence, x can be explicitly integrated by inverting the hyperelliptic integral We use now the geometric information provided by the Pontryagin maximum principle and the hyperelliptic curve described above, for deriving the geometric features that optimal trajectories in the plane {(x, y)} ≃ {(x, y, 0, . . . , 0)} necessarily have.

To begin with, we consider the three-dimensional space with coordinates (x, u 1 , z) = (x, ẋ, ẏ) = (x, u 1 , u 2 ) = (H n-1 , H 1 , H 2 ), and the following two cylinders:

C 1 = {(x, u 1 , z) | u 2 1 + z 2 = 1} and C 2 = {(x, u 1 , z) | z = p k (x)}.
We can assume that the C 1 ∩ C 2 = ∅ and by choosing the initial conditions properly, we can assume that this intersection is a smooth, connected, closed and simple curve. We denote by C the parametrized curve that is the projection of C 1 ∩ C 2 to the plane {(x, u 1 )} ≃ {(x, u 1 , 0)}, and call it the cacahuète curve of the problem, taking equation (4.4) into consideration we have:

C = (x, u 1 ) | u 1 = 1 -p 2 k (x) .
The cacahuète is a smooth, closed and simple curve that has both, vertical and horizontal symmetries, and by choosing the initial conditions properly it can be assumed that it is centered at the origin.

One can see on figure [START_REF] Jean | Complexity of Nonholonomic Motion Planning[END_REF] how the cacahuète comes. The cacahuète encodes the information of extremal curves in the plane {(x, y)} ≃ {(x, y, 0, . . . , 0)} ⊂ {(x, y, θ 1 , . . . , θ k )}. Let E be such an arc-length parametrized extremal curve in this plane, taking equation (4.5) into account we have:

E = {(x, y) | ẏ = p k (x)}.
We assume E to be centered at the origin. Moreover, we want the curve E to have total length 1 (or ε), but this can be obtained a posteriori by homogeneity.

In order to depict the curve E we have the freedom of choosing the coefficients of the polynomial p k (x) and the initial condition y(0). Also we have to take into consideration the following interpolation conditions (which are independent of any translation of coordinates):

(1) The coordinate y is periodic, y(1) = y(0).

(2) The moments m i = E x i dy are all zero for i = 1, . . . , n -3, which corresponds to the fact that the coordinates θ 1 , . . . , θ n-3 , given by (4.5) are all periodic. Observe that the first moment m 1 is the area swept out by the curve, whereas the last moment m n-2 is not only non vanishing but also the one to be maximized.

The curves E are symmetric with respect to the x-axis but we do not know if they are symmetric with respect to the y-axis, however we make this assumption, a priori reasonable.

Remark 5.

• Since we will be able to find geodesics meeting this assumption plus the boundary conditions, it is reasonable to expect that these geodesics are optimal.

• It is clear the union set of our centered solutions, is symmetric with respect to the y-axis, but it is not clear that the minimal solution is unique. • Due to the interpolation requirements, it is clear that the projection of our curve on the plane (x, y) has to be periodic. Moreover, with the group law explicitly exhibited in (3.1) we can follow the same proof as in the papers [START_REF] Boizot | Motion Planning for Kinematic Systems[END_REF][START_REF] Boizot | On the Motion Planning of the Ball with a Trailer[END_REF], to show that this curve is in fact smooth-periodic.

Under these symmetry considerations and depending on the parity of n, (which is the same parity of k) certain moments are automatically zero and the description of E can always be completed.

• If n is even, the odd moments are zero. The polynomial p k (x) has even degree and by the symmetry considerations, it has no terms of odd degree. Then, if we chose a monic polynomial, it remains k 2 free coefficients, that have to be used to vanish k 2 -1 moments (plus the zero-moment y). For instance, for n = 6, we have to chose only two coefficients to make y periodic and to vanish the moment m 2 .

• if n is odd, the even moments are zero. The polynomial p k (x) has odd degree and by the symmetry considerations, it has no terms of even degree.

Then, if we chose a monic polynomial, it remains k-1 2 free coefficients, that have to be used to vanish k-1 2 moments and the value y(0) to make y periodic, which can be done as an independent (trivial) step.

For instance, for n = 7, we have to chose two coefficients to vanish two moments, and we chose the value y(0) to make y vanishing at a quarter period.

From this analysis we can conclude that, at the end we have as many free parameters (plus one that accounts for the initial condition y(0)) as the number of moments that have to vanish. In practice, we use the only following numerical integration: 2 , and compute the solution for a quarter period only. The x corresponding to a quarter period (denoted by x 1 4 ) is just given by the largest real root of p k (x). The value y(0) follows. Solutions over the other 3 intervals are obtained by symmetry.

dy dx = p k (x) 1 -p k (x)
Hence, for both n = 6, 7, the computation reduces to this numerical integration (over a quarter period), and to performing shooting on 2 coefficients of p k (x). We obtained the numerical results that are presented in the introduction.

Conclusions and some open questions

In this paper we propose to use our entropy method of previous papers to treat the motion-planning problem for Goursat sub-riemannian metrics in arbitrary dimensions. We put in evidence a class of control trajectories and state trajectories that are in a sense universal and optimal, and therefore we think that these signals are the natural ones for dealing with motion planning questions. This conclusion is reinforced by the fact that it fits with the conclusions (in the generic cases, but for low order brackets) of our previous studies.

In particular, our results apply to the motion planning of the car with trailers, which is the prototype of a Goursat structure. In this case, moreover, the method can be used in a direct way (not asymptotic) to interpolate non-admissible paths by means of admissible ones.

In our view, there are many interesting issues to address in this regard, but we just want to bring the attention to the following two challenging questions:

• Find arguments (like it was done in the paper [START_REF] Boizot | On the Motion Planning of the Ball with a Trailer[END_REF]) to prove that our (symmetric) Goursat extremals are actually optimal. • Prove (or find counterexample) that in the generic case the geometric pattern of the pictures of optimal extremals persists, and depends only on the length of the Lie brackets of the highest order. This is not so clear: when the order increases, the number of interpolation conditions increases much more (contrarily to what happens in the Goursat case), and it might happen that some more complicated periodic extremals come into the picture. Some of these more complicated extremals were exhausted in [START_REF] Boizot | On the Motion Planning of the Ball with a Trailer[END_REF]. We show one of them in the figure 6.

Figure 1 .

 1 Figure 1. Generic optimal interpolating motion for 1 to 3 brackets.

Figure 2 .

 2 Figure 2. Cacahuètes for 1 to 3 brackets

Figure 3 .

 3 Figure 3. Optimal interpolating motion for Goursat structure with 4 and 5 brackets

Figure 4 .

 4 Figure 4. Cacahuètes for 4 and 5 brackets

  1, and xn = x n , in these new coordinates the curve Γ is rectified to become the vertical line Γ(s) = (0, . . . , 0, γ n (s)).

  ∂ ∂x1 and ∂ ∂x2 have weight -1, ∂ ∂x3 has weight -2, . . . , ∂ ∂xn-1 has weight -(n -2) and ∂ ∂xn has

3. 2 .

 2 Gauge invariance of the metric. Any arbitrary nonsingular 2 × 2 matrix as A = T R ϕ where R ϕ ∈ SO 2 and T is a non-singular lower triangular 2 × 2 matrix, say T = a 0 b c , with ac = 0.

3. 5 .

 5 Geometry of extremals. From equations (3.19) and (3.18) one gets d dt

Figure 5 .

 5 Figure 5. Intersection of the energy cylinder H = 1 2 and the cylinder with generatrix (3.23).

2 . 5 .

 25 Optimal curves. As projection of extremal curves, optimal solutions necesk (x), for j = 1, . . . k (4.6) Motion planning for Goursat structures.

Figure 6 .

 6 Figure 6. Other periodic extremals for order 3 (length-4) brackets

Aknowledgements

This paper was prepared during the sabbatical leave of the second author at the Laboratoire des Sciences de l'Information et des Systèmes (LSIS, UMR 7296) in the Université du Sud Toulon-Var, France. The author was financially supported by the CONACYT under the program of sabbatical leaves abroad for the reinforcement of the research groups, project number 204051.