The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
We study accuracy guaranteed solutions of geometric problems define on convex region under an assumption that input points are known only up to a limited accuracy, that is, each input point is given by a convex region that represents the possible locations of the point. We show how to compute tight error bounds for basic problems such as convex hull, Minkowski sum of convex polygons, diameter of points,...
This paper considers the leader election problem (LEP) in asynchronous complete networks with undetectable fail-stop failures. Especially, it is discussed whether presence of a global sense of direction affects the message complexity of LEP in faulty networks. For a complete network of n processors where k processors start the algorithm spontaneously and at most fp...
We present a wait-free implementation of the atomic snapshot object on the shared memory system. A snapshot object shared by n processes is a data structure partitioned into n segments such that each process owns one segment. Each process can update its own segment, and instantaneously scan all segments. In our implementation, each object operation requires O(n) operations on atomic multi-writer multi-reader...
The specification of a class of single resource schedulers is presented. A class of these schedulers is regarded as a parameterized data type whose formal parameter is a scheduling strategy. The specification is given by using the concept of parameterization in algebraic techniques. The specification of each scheduler instance can be directly obtained only by replacing the formal parameter with a...
In this paper, we study the computation of 2-dimensional convex hull of a set of points whose positions are inaccurate, that is, known only up to a given accuracy. To compute accuracy guaranteed results from such an imprecise input, we consider two types of convex hull, inner convex hull and outer convex hull which are defined as the intersection and the union of all possible convex hulls. The gap...
This paper considers the Updating Minimum-weight Spanning Tree Problem (UMP), that is, the problem to update the Minimum-weight Spanning Tree (MST) in response to topology change of the network. This paper proposes the algorithm which reconstructs the MST after several links are deleted and added. Its message complexity and its ideal-time complexity are O(m+n log (t+f)) and O(n+n log(t+f)) respectively,...
Acausal distributed breakpointis one of the fundamental mechanisms for debugging distributed programs. It is initiated by a sequential breakpoint in one process of a distributed computation, and restores each process to theearlieststate that reflects all events that happened causally before the sequential breakpoint. This paper presents an algorithm for finding the causal distributed breakpoint when...
An IP-schema (Ianov schema with pushdown memory) has one register just as for Ianov schemas, but the finite-state control is augmented by a pushdown memory that can only be used for storing the contents of the register or fetching the contents of the top to the register. An IP(k)-schema is an IP-schema which uses only the first k memory locations of the pushdown memory. Let CIP(k)(or CIP) be the class...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.