On-line algorithms and fast digital identity revocation.
详细信息
- 作者：Lodha ; Sachin Premsukh.
- 学历：Doctor
- 年：2002
- 导师：Szemeredi, Endre
- 毕业院校：Rutgers The State University of New Jersey
- 专业：Computer Science.
- ISBN：0493608257
- CBH：3046755
- Country：USA
- 语种：English
- FileSize：2764952
- Pages：82
文摘
The k-server problem is a generalized model of certain scheduling problems such as, for instance, multi-level memory paging, disk caching and head motion planning of multi-headed disks. The problem can be stated as follows: We are given k mobile servers that occupy k points of a metric space M. We assume that M is finite, |M| = n > k, and k > 1. At each time step a request, a point of M, appears. An algorithm must serve this request by moving one of its servers to the requested point (if that is vacant). The algorithm is charged a cost which is equal to the distance moved by the server. The algorithm A is on-line if it serves the request without knowing what the future requests will be. We present a O(n2/3 ln n)-competitive randomized on-line algorithm when the underlying metric space is given by n equally spaced points on a line. This algorithm is o( k)-competitive for n = k + o(k3/2/ln k).;Let A be an n-uniform hypergraph. Assume that the maximum degree of A is D = D( A ) (local condition), and | A | = N = N ( A ) (global condition). By the Lovász Local Lemma (L.L.L.), if D < 2n/8n, then A has a proper 2-coloring (i.e. there is no monochromatic edge) independently of the value of N (N can be infinite). Unfortunately L.L.L. is a pure existence argument which does not give any clue of how to find a proper 2-coloring. A hypergraph with the property that any two edges have at most one point in common is called almost disjoint (e.g. a family of lines). Assume that A is an n-uniform almost disjoint hypergraph. In this special case, we provide a polynomial time (in terms of N) algorithm to find a proper 2-coloring under the slightly weaker condition that D < (2 ? δ)n and N is less than a doubly exponential function of n.;The availability of fast and reliable digital identities is an essential ingredient for the successful implementation of the public-key infrastructure of the Internet. All digital identity schemes must include a method for revoking someone's digital identity in the case that this identity is stolen (or canceled) before its expiration date (similar to the cancelation of a credit-cards in the case that they are stolen). In 1995, Silvio Micali proposed an elegant method of identity revocation which requires very little communication between users and verifiers in the system. We extend Micali's scheme by reducing the overall Certificate Authority to Directory communication while still maintaining the same tiny user to vendor communication.