Shah, Shin and Tetali [25] initiated the study of queuing systems on the medium access channel with arbitrary interference graph. The graph models dependencies between the channel members -- any two connected by an edge are dependent. This problem could ...

Leader election is a fundamental task in distributed computing. It is a symmetry breaking problem, calling for one node of the network to become the leader, and for all other nodes to become non-leaders. We consider leader election in anonymous radio ...

Modern data centers are tasked with processing heterogeneous workloads consisting of various classes of jobs. These classes differ in their arrival rates, size distributions, and job parallelizability. With respect to parallelizability, some jobs are ...

We consider the problem of cross-chain payment whereby customers of different escrows---implemented by a bank or a blockchain smart contract---successfully transfer digital assets without trusting each other. Prior to this work, cross-chain payment ...

Hardware and software faults increasingly surface in today's computing environment and vast theoretical and practical research efforts are devoted to ameliorate the effects of malfunctionality in the computing process. Most research to date, however, ...

We present the tracking approach for deriving detectable implementations of many widely-used concurrent data structures for systems with non-volatile main memory (NVRAM). Detectable recovery ensures that in the crash-recovery model, every operation ...

Many modern parallel applications, such as desktop software and cloud-based web services, are service-oriented, long running, and perform frequent interactions with the external world (e.g., responding to user input). We want such interactive ...

We study the parallel query complexity of reconstructing binary trees from simple queries involving their nodes. We show that a querier can efficiently reconstruct a binary tree with a logarithmic number of rounds and quasilinear number of queries, with ...

In this paper we develop optimal algorithms in the binary-forking model for a variety of fundamental problems, including sorting, semisorting, list ranking, tree contraction, range minima, and ordered set union, intersection and difference. In the ...

This paper extends the Transactional Memory (TM) paradigm by proposing a new powerful abstraction, the transactional future. Transactional futures, as the name suggests, combine TM with futures, by allowing programmers to exploit intra-transaction ...

In a PODC 2008 paper, Helm proposed a protocol for solving distributed consensus using quantum techniques, and without exchanging messages in the classical sense. In this protocol, entangled qubits are distributed to the participants at initialization. ...

Herlihy's consensus hierarchy ranks the power of various synchronization primitives for solving consensus in a model where asynchronous processes communicate through shared memory, and may fail by halting. This paper revisits the consensus hierarchy in ...