Author name cluster
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.
TCS Journal 2010 Journal Article
This paper presents an algorithm for convex polygon decomposition around a given set of locations. Given an n -vertex convex polygon P and a set X of k points positioned arbitrarily inside P, the task is to divide P into k equal-area convex parts, each containing exactly one point of X. The algorithm runs in time O ( k n + k 2 log k ).
I&C Journal 1995 Journal Article
A quorum system is a collection of sets (quorums) every two of which intersect. Quorum systems have been used for many applications in the area of distributed systems, including mutual exclusion, data replication, and dissemination of information. In this paper we study the failure probabilities of quorum systems and in particular of nondominated coteries (NDC). We characterize NDC′s in terms of the failure probability, and prove that any NDC has availability that falls between that of a singleton and a majority consensus. We show conditions for weighted voting schemes to provide asymptotically high availability, and we analyze the availability of several other known quorum systems.
I&C Journal 1995 Journal Article
This paper concerns some of the theoretical complexity aspects of the reconfigurable network model. The computational power of the model is investigated under several variants, depending on the type of switches (or switch operations) assumed by the network nodes. Computational power is evaluated by focusing on the set of problems computable in constant time in each variant. A hierarchy of such problem classes corresponding to different variants is shown to exist and is placed relative to traditional classes of complexity theory.
I&C Journal 1993 Journal Article
Distributed systems often make use of directory servers enabling the storage and retrieval of global information in the network. In many practical situations, the data are directly related to particular sites of the network, and therefore the desired retrieval characteristics are dependent on the network topology; for example, priority is given to having high accessibility to data generated in nearby locations. This paper defines the concept of distance-dependent directories, and then proposes appropriate accessibility measures and presents strategies for constructing such directories. The construction methods are based on efficient solutions to a new type of graph-covering problem. As an application, it is shown how to use a distance-dependent directory to implement a name-server component for a routing scheme.
TCS Journal 1985 Journal Article
The paper proposes an extension RPL of the process logic PL of Harel, Kozen and Parikh (1980). The PL formula operators f and suf are replaced by the operators chop and slice, corresponding to Kleene's regular operators · and ∗, thus enabling formulas to express regular sets of paths. The main result is that, in expressive power, PL<RPL, the hard part being in showing that PL⩽RPL. It is argued that this version of PL comes closer to the desired goal of a natural and powerful (yet decidable) logic for reasoning about the ongoing behavior of programs.