Arrow Research search

Author name cluster

Micah Adler

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

13 papers
1 author row

Possible papers

13

STOC Conference 2003 Conference Paper

A stochastic process on the hypercube with applications to peer-to-peer networks

  • Micah Adler
  • Eran Halperin
  • Richard M. Karp
  • Vijay V. Vazirani

Consider the following stochastic process executed on a graph G=(V,E) whose nodes are initially uncovered. In each step, pick a node at random and if it is uncovered, cover it. Otherwise, if it has an uncovered neighbor, cover a random uncovered neighbor. Else, do nothing. This can be viewed as a structured coupon collector process. We show that for a large family of graphs, O(n) steps suffice to cover all nodes of the graph with high probability, where n is the number of vertices. Among these graphs are d -regular graphs with d =Ω(log n log log n) , random d -regular graphs with d =Ω(log n) and the k -dimensional hypercube where n=2 k .This process arises naturally in answering a question on load balancing in peer-to-peer networks. We consider a distributed hash table in which keys are partitioned across a set of processors, and we assume that the number of processors grows dynamically, starting with a single processor. If at some stage there are n processors, the number of queries required to find a key is log 2 n+O(1) , the number of pointers maintained by each processor is log 2 n+O(1) , and moreover the worst ratio between the loads of processors is O(1) , with high probability. To the best of our knowledge, this is the first analysis of a distributed hash table that achieves asymptotically optimal load balance, while still requiring only O(log n) pointers per processor and O(log n) queries for locating a key; previous methods required Ω(log 2 n) pointers per processor and Ω(log n) queries for locating a key.

Details

STOC Conference 2002 Conference Paper

Tradeoffs in probabilistic packet marking for IP traceback

  • Micah Adler

There has been considerable recent interest in probabilistic packet marking schemes for the problem of tracing a sequence of network packets back to an anonymous source. An important consideration for such schemes is the number of packet header bits that need to be allocated to the marking protocol. Let b denote this value. All previous schemes belong to a class of protocols for which b must be at least log n , where n is the number of bits used to represent the path of the packets. In this paper, we introduce a new marking technique for tracing a sequence of packets sent along the same path. This new technique is effective even when b =1. In other words, the sequence of packets can be traced back to their source using only a single bit in the packet header. With this scheme, the number of packets required to reconstruct the path is O (2 2 n ), but we also show that ω(2 n ) packets are required for any protocol where b =1. We also study the tradeoff between b and the number of packets required. We provide a protocol and a lower bound that together demonstrate that for the optimal protocol, the number of packets required (roughly) increases exponentially with n , but decreases doubly exponentially with b . The protocol we introduce is simple enough to be useful in practice. We also study the case where the packets are sent along k different paths. For this case, we demonstrate that any protocol must use at least log(2 k —1) header bits. We also provide a protocol that requires ⌈log(2 k +1)⌉ header bits in some restricted scenarios. This protocol introduces a new coding technique that may be of independent interest.

Details

FOCS Conference 1998 Conference Paper

Protocols for Asymmetric Communication Channels

  • Micah Adler
  • Bruce M. Maggs

In this paper we examine the problem of sending an n-bit data item from a client to a server across an asymmetric communication channel. We demonstrate that there are scenarios in which a high-speed link from the server to the client can be used to greatly reduce the number of bits sent from the client to the server across a slower link. In particular, we assume that the data item is drawn from a probability distribution D that is known to the server but not to the client. We present several protocols in which the expected number of bits transmitted by the server and client are O(n) and O(H(D)+1), respectively, where H(D) is the binary entropy of D (and can range from 0 to n). These protocols are within a small constant factor of optimal in terms of the number of bits sent by the client. The expected number of rounds of communication between the server and client in the simplest of our protocols is O(H(D)). We also give a protocol for which the expected number of rounds is only 0(1), but which requires more computational effort on the part of the server. A third technique provides a tradeoff between the computational effort and the number of rounds.

Details

FOCS Conference 1996 Conference Paper

New Coding Techniques for Improved Bandwidth Utilization

  • Micah Adler

The introduction of parallel models that account for communication between processors has shown that interprocessor bandwidth is often the limiting factor in parallel computing. In this paper, we introduce a new coding technique for transmitting the XOR of carefully selected patterns of bits to be communicated which greatly reduces bandwidth requirements in some settings. This technique has broader applications. For example, we demonstrate that the coding technique has a surprising application to a simple I/O (Input/Output) complexity problem related to finding the transpose of a matrix. Our main results are developed in the PRAM(M) model, a limited bandwidth PRAM model where P processors communicate through a small globally shared memory of M bits. We provide new algorithms for the problems of sorting and permutation routing. For the concurrent read PRAM(M), as P grows with M held constant, our sorting algorithm outperforms any previous algorithm by /spl Omega/(log/sup c/ P) for any constant c. The combination of a known lower bound for sorting in the exclusive read PRAM(M) model and this algorithm implies that the concurrent read PRAM(M) is strictly more powerful than the exclusive read PRAM(M).

Details

MFCS Conference 1995 Invited Paper

Scheduling Parallel Communication: The h-relation Problem

  • Micah Adler
  • John W. Byers
  • Richard M. Karp

Abstract This paper is concerned with the efficient scheduling and routing of point-to-point messages in a distributed computing system with n processors. We examine the h -relation problem, a routing problem where each processor has at most h messages to send and at most h messages to receive. Communication is carried out in rounds. Direct communication is possible from any processor to any other, and in each round a processor can send one message and receive one message. The off-line version of the problem arises when every processor knows the source and destination of every message. In this case the messages can be routed in at most h rounds. More interesting, and more typical, is the on-line version, in which each processor has knowledge only of h and of the destinations of those messages which it must send. The on-line version of the problem is the focus of this paper. The difficulty of the h -relation problem stems from message conflicts, in which two or more messages are sent to the same processor in a given round, but at most one can be received. The problem has been well studied in the OCPC optical network model, but not for other contemporary network architectures which resolve message conflicts using other techniques. In this paper, we study the h -relation problem under alternative models of conflict resolution, most notably a FIFO queue discipline motivated by wormhole routing and an arbitrary write discipline motivated by packet-switching networks. In each model the problem can be solved by a randomized algorithm in an expected number of rounds of the form ch +o( h )+log Θ (1) n, and we focus on obtaining the smallest possible asymptotic constant factor c. We first present a lower bound, proving that a constant factor of 1 is not achievable in general. We then present a randomized algorithm for each discipline and show that they achieve small constant factors.

Details