The Internet enables connectivity between many strangers: entities that don't know each other. We present the Trust Policy Language (TPL), used to define the mapping of strangers to predefined business roles, based on certificates issued by third parties. TPL is expressive enough to allow complex policies, e.g. non-monotone (negative) certificates, while being simple enough to allow automated policy checking and processing. Issuers of certificates are either known in advance, or provide sufficient certificates to be considered a trusted authority according to the policy. This allows bottom-up, "grass roots" buildup of trust, as in the real world. We extend, rather than replace, existing role based access control mechanisms. This provides a simple, modular architecture and easy migration from existing systems. Our system automatically collects missing certificates from peer servers. In particular this allows use of standard browsers, which pass only one certificate to the server. We describe our implementation, which can be used as an extension of a Web server or as a separate server with interface to applications.

A layered graph is a connected graph whose vertices are partitioned into sets L 0 =s, L 1 , L 2 ,..., and whose edges, which have nonnegative integral weights, run between consecutive layers. Its width is $\max\{|L_i|\}$. In the on-line layered graph traversal problem, a searcher starts at s in a layered graph of unknown width and tries to reach a target vertex t; however, the vertices in layer i and the edges between layers i-1 and i are only revealed when the searcher reaches layer i-1. We give upper and lower bounds on the competitive ratio of layered graph traversal algorithms. We give a deterministic on-line algorithm which is O(9 w )-competitive on width-w graphs and prove that for no w can a deterministic on-line algorithm have a competitive ratio better than 2 w-2 on width-w graphs. We prove that for all w, w/2 is a lower bound on the competitive ratio of any randomized on-line layered graph traversal algorithm. For traversing layered graphs consisting of w disjoint paths tied together at a common source, we give a randomized on-line algorithm with a competitive ratio of O(log w) and prove that this is optimal up to a constant factor.

In this paper, the authors prove lower bounds on the competitive ratio of randomized algorithms for two on-line problems: the k-server problem, suggested by Manasse, McGeoch, and Sleator [Competitive lgorithms for on-line problems, J. Algorithms, 11 (1990), pp. 208–230], and an on-line motion-planning problem due to Papadimitriou and Yannakakis [Shortest paths without a map, Lecture Notes in Comput. Sci. 372, Springer-Verlag, New York, 1989, pp. 610–620]. The authors prove, against an oblivious adversary, 1. an $\Omega \log k$ lower bound on the competitive ratio of any randomized on-line k-server algorithm in any sufficiently large metric space, 2. an $\Omega (\log \log k)$ lower bound on the competitive ratio of any randomized on-line k-server algorithm in any metric space with at least $k + 1$ points, and 3. an $\Omega (\log \log n)$ lower bound on the competitive ratio of any on-line motion-planning algorithm for a scene with n obstacles. Previously, no superconstant lower bound on the competitive ratio of randomized on-line algorithms was known for any of these problems.

A layered graph is a connected, weighted graph whose vertices are partitioned into sets L/sub 0/=(s), L/sub 1/, L/sub 2/, . . ., and whose edges run between consecutive layers. Its width is max( mod L/sub i/ mod ). In the online layered graph traversal problem, a searcher starts at s in a layered graph of unknown width and tries to reach a target vertex t; however, the vertices in layer i and the edges between layers i-1 and i are only revealed when the searcher reaches layer i-1. The authors give upper and lower bounds on the competitive ratio of layered graph traversal algorithms. They give a deterministic online algorithm that is O(9w)-competitive on width-w graphs and prove that for no w can a deterministic online algorithm have a competitive ratio better than 2w/sup -2/ on width-w graphs. They prove that for all w, w/2 is a lower bound on the competitive ratio of any randomized online layered graph traversal algorithm. For traversing layered graphs consisting of w disjoint paths tied together at a common source, they give a randomized online algorithm with a competitive ratio of O(log w) and prove that this is optimal up to a constant factor.>

No abstract available.

Deterministic competitive k-server algorithms are given for all k and all metric spaces. This settles the k-server conjecture of M.S. Manasse et al. (1988) up to the competitive ratio. The best previous result for general metric spaces was a three-server randomized competitive algorithm and a nonconstructive proof that a deterministic three-server competitive algorithm exists. The competitive ratio the present authors can prove is exponential in the number of servers. Thus, the question of the minimal competitive ratio for arbitrary metric spaces is still open. The methods set forth here also give competitive algorithms for a natural generalization of the k-server problem, called the k-taxicab problem.>