In recent years, many researchers have investigated optical interconnections as parallel computing. Optical interconnections are attractive due to their high bandwidth and concurrent access to the bus in a pipelined fashion. The Linear Array with Reconfigurable Pipelined Bus System (LARPBS) model is a powerful optical bus system that combines both the advantages of optical buses and reconfiguration. To increase the scalability of the LARPBS model, we propose a two-dimensional extension: a simplified two-dimensional Array with Reconfigurable Pipelined Bus System (2D ARPBS). While achieving better scalability, we show the effectiveness of this newly proposed model by designing two novel optimal sorting algorithms on this model. The first sorting algorithm is an extension of Leighton's seven-phase columnsort algorithm that eliminates the restriction of sorting only an r \times s array, where r \ge s^2 , and sorts an n \times n array in O(\log n) time. The second one is an optimal multiway mergesort algorithm that uses a novel processor efficient two-way mergesort algorithm and a novel multiway merge scheme to sort n^2 items in O(\log n) time. Using an optimal sorting algorithm Pipelined Mergesort designed for the LARPBS model as a building block, we extend our research on parallel sorting on the LARPBS to a more scalable 2D ARPBS model and achieve optimality in both sorting algorithms.

Recent advances in storage technology have enabled systems like Storage Area Networks, where disks are attached directly to the network, rather than being under the control of a single process. In such an environment there is no a priori bound on the number of processes that may access the network attached disks, and so uniform implementations are desirable, that is, implementations that do not rely on the number of processes. We investigate how to use network attached disks, where some disks may crash, as a shared communication medium. To do so, we model disk blocks as Multi-Writer Multi-Reader (MWMR) shared memory registers that may fail by crashing. We study whether a finite number of such fail-prone registers can be used to uniformly implement various types of fail-flee target registers: wait-free atomic, atomic, and wait-free sequentially consistent. For each of these types, we determine the implementability of Multi-Writer Multi-Reader registers, Multi-Writer Single-Reader registers (MWSR), Single-Writer Multi-Reader registers (SWMR) and Single-Writer Single-Reader registers (SWSR). For example, we show that there is no uniform atomic implementation of a MWMR register using finitely many base registers, even if the implementation need not be wait-free. On the positive side we show that with infinitely many base registers then all types of registers can be implemented. This opens the question of how to translate uniform shared memory protocols that use MWMR registers to use network attached disks.

We present a generic module, called Fast Collect. Fast Collect is an implementation of single-writer multi-reader (SWMR) shared-memory in an asynchronous system in which a processor updates its cell and then reads in any order all the other cells. Our simple implementation of Fast Collect uses some multiwriter multi-reader (MWMR) variables and one local Boolean per processor, such that eventually, in the absence of contention, i.e. if only a single processor repeatedly performs collect, the amortized cost per each collect is a constant. With the example of Disk Paxos we show how Fast Collect can be used as a building block in wait-free algorithms.

Token rotation algorithms play an important role in distributed computing, to support such activities as mutual exclusion, round-robin scheduling, group membership and group communication protocols. Ring-based protocols maximize throughput in busy systems but can incur a linear (in the number of processors) delay when a processor needs to obtain a token to perform an operation. This paper synthesizes new algorithmic techniques for improving the performance (responsiveness) of logical ring protocols. The parameterized technique presents the safety properties of ring protocols and maintains high throughput in busy systems, while reducing the delay in lightly loaded systems from a linear to a logarithmic function in the number of processors. The development in this paper is done using term rewriting systems, where our parameterized protocol is developed in a series of safety-preserving refinements of a basic specification.

Providing shared-memory abstraction in message-passing systems often simplifies the development of distributed algorithms and allows for the reuse of shared-memory algorithms in the message-passing setting. A robust emulation of atomic single-writer/multi-reader registers in message-passing systems was developed by Attiya, Bar-Noy and Dolev (1995). This emulation was extended by Lynch and Shvartsman (1997) to multi-writer/multi-reader registers using reconfigurable quorum systems. In this work we present a new atomic multi-writer/multi-reader register service that includes a fault-tolerant reconfiguration service. This new emulation has a substantially improved performance and fault-tolerance characteristics. We introduce the concept of intermediate quorum configurations and show how they can be used by readers/writers during reconfiguration. The result is that the quorum reconfigurations are graceful: readers and writers no longer "busy-wait" during reconfigurations, bur are able to complete their operations. An additional advance is that the reconfigurer is eliminated as the single point of failure. When the reconfigurer fails, readers and writers continue using intermediate configurations. In finite executions, read and write operations terminate in bounded time using a bounded number of messages (the bounds depend on the "currency" of the configuration at the invoker of the operation). Finally, the service places no restrictions on the installed quorum configuration: a previously installed quorum system can be replaced by an arbitrary new quorum system.