Some of the first routing algorithms for position-aware wireless networks used the Delaunay triangulation of the point-locations of the network's nodes as the underlying connectivity graph. Later on these solutions were considered impractical because the Delaunay triangulation may in general contain arbitrarily long edges and because calculating the Delaunay triangulation may require a global view of the network. Many other algorithms were then suggested for geometric routing, often assuming random placement of network nodes for analysis or simulation [27, 5, 28, 15]. But as we show, when the nodes are uniformly placed in the unit disk the Delaunay triangulation does not contain long edges, it is easy to compute locally and it is in many ways optimal for geometric routing and flooding.In particular, we prove that with high probability the maximal length of an edge in Del(P), the Delaunay triangulation of a set P of n nodes uniformly placed in the unit disk, is O(3√3log novern), and that the expected sum of squares of all the edges in Del(P) is O(1). These geometric results imply that for wireless networks, randomly distributed in a unit disk (1) computing the Delaunay triangulation locally is asymptotically easy; (2) simple "face routing" through the Delaunay triangulation optimizes, up to poly-logarithmic factors, the energy load on the nodes, and (3) flooding the network, an operation quite common in sensor nets, is with high probability optimal up to a constant factor. The last property is particularly important for geocasting because the Delaunay triangulation is known to be a spanner.

Long-lived and adaptive to point contention implementations of snapshot and immediate snapshot objects in the read/write shared-memory model are presented. In [2] we presented adaptive algorithms for mutual exclusion, collect and snapshot. However, the collect and snapshot algorithms were adaptive only when the number of local primitive operations that a process performs are ignored, i.e., not counted. The number of primitive local steps (operations that do not access the shared memory) in the collect and snapshot operations presented in [2] is O(Nk3) and O(Nk4) respectively where N is the total number of processes in the system and k is the encountered contention. Here we developed new techniques that enabled us to achieve fully adaptive implementations in which the step complexity (combined local and shared) of any operation is bounded by a function of the number of processes that are concurrent with the operation, in particular, O(k4) for the snapshot implementation.

A distributed algorithm is adaptive if the worst case step complexity of its operations is bounded by a function of the number of processes that are concurrently active during the operation (rather than a function of N, the total number of processes, which is usually much larger). We present long-lived and adaptive algorithms for collect in the read/write shared-memory model. Replacing the reads and writes in long-lived shared memory algorithms with our adaptive collect results in many cases in a corresponding long-lived algorithm which is adaptive. Examples of such applications, which are discussed are atomic-snapshots, and l-exclusion. Following the long-lived and adaptive collect we present a more pragmatic version of collect, called active set. This algorithm is slightly weaker than the collect but has several advantages. We employ this algorithm to transform algorithms, such as the Bakery algorithm, into their corresponding adaptive long-lived version, which is more efficient than the version that was obtained with the collect. Previously, long-lived and adaptive algorithms in this model were presented only for the renaming problem.

Theoretically, various shared synchronization objects, such as compare&swap and arbitrary read-modify-write registers, are universal [10, 20].That is, any sequentially specified task can be solved in a concurrent system that supports these objects and a large enough number of shared read/write registers.Are these objects indeed almighty?Or, are there other considerations that have

Though it is common practice to treat synchronization primitives for multiprocessors as abstract data types, they are in reality machine instructions on registers. A crucial theoretical question with practical implications is the relationship between the size of the register and its computational power. The authors study this question and choose as a first target the popular compare and swap operation (which is the basis for many modern multiprocessor architectures). The results of this paper suggest that a complexity hierarchy for multiprocessor synchronization operations should be based on the space complexity of synchronization registers and not on the number of so called "synchronization objects".>