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.
What can be computed in a distributed system in which faults can occur? This is a very broad question. There are many different models of distributed systems and many different kinds of faults that can occur. Unlike the situation in sequen- tial models of computation, small changes in the model of a distrubuted system can radically alter the class of problems that can be solved. Another important...
We present the first adaptive algorithm for iV-process mutual exclusion under read/write atomicity in which all busy waiting is by local spinning. In our algorithm, each process p performs O(min(k,log N)) remote memory references to enter and exit its critical section, where k is the maximum “point contention” experienced by p. The space complexity of our algorithm is <9(iV), which is clearly optimal.
Most weak memory consistency models are incapable of supporting a solution to mutual exclusion using only read and write operations to shared variables. Processor Consistency-Goodman’s version (PC-G) is an exception. Ahamad et al.[l] showed that Peterson’s mutual exclusion algorithm is correct for PC-G, but Lamport’s bakery algorithm is not. In this paper, we derive a lower bound on the number and...
The computer industry is examining the use of strong syn- chronization operations such as double compare-and-swap (DCAS) as a means of supporting non-blocking synchronization on tomorrow’s mul- tiprocessor machines. However, before such a primitive will be incorpo- rated into hardware design, its utility needs to be proven by developing a body of effective non-blocking data structures using DCAS....
This paper deals with the implementation of an English auction on a distributed system. We assume that all messages are restricted to bids and resignations (referred to as the limited communication assumption) and that all participants are trying to maximize there gains (referred to as the prudence assumption). We also assume that bidders are risk-neutral, and that the underlying communication network...
This paper presents a scalable leader election protocol for large process groups with a weak membership requirement. The underlying network is assumed to be unreliable but characterized by probabilistic failure rates of processes and message deliveries. The protocol trades correctness for scale, that is, it provides very good probabilistic guarantees on correct termination in the sense of the classical...
We are motivated by the developments in all-optical networks - a new tech- nology that supports high bandwidth demands. These networks provide a set of ligthpaths which can be seen as high-bandwidth pipes on which communication is performed. Since the capacity enabled by this technology substatially exceeds the one provided by conventional networks, its ability to recover from failures within the...
This paper presents a study of a distributed cooperation problem under the assumption that processors may not be able to communicate for a prolonged time. The problem for n processors is defined in terms of the tasks that need to be performed efficiently and that are known to all processors. The results of this study characterize the ability of the processors to schedule their work so that when some...
We show that Naming- the existence of distinct IDs known to all- is a necessary assumption of Herlihy’s universality result for Con- sensus. We then show in a very precise sense that Naming is harder than Consensus and bring to the surface some important differences existing between popular shared memory models which usually remain unnoticed.
In the long-lived M-renaming problem, processes repeatedly obtain and release new names taken from a domain of size M. This paper presents the first polynomial algorithm for long-lived (2ft - 1)- renaming. The algorithm is adaptive as its step complexity is O(k4); here k is the point contention-the maximal number of simultaneously active processes in some point of the execution. Polynomial step complexity...
We explore four classic problems in concurrent computing (election, mutual exclusion, consensus, and naming) when the number of processes which may participate is infinite. Partial information about the number of actually participating processes and the concurrency level is shown to affect the possibility and complexity of solving these problems. We survey and generalize work carried out in models...
Conventional mechanisms for electronic commerce provide strong means for securing transfer of funds, and for ensuring such things as authenticity and non-repudiation. But they generally do not attempt to regulate the activities of the participants in an e-commerce transac- tion, treating them, implicitly, as autonomous agents. This is adequate for most cases of client-to-vendor commerce, but is quite...
Metering schemes are cryptographic protocols to count the number of visits received by web sites. These measurement systems are used to decide the amount of money to be paid to web sites hosting advertisements. Indeed, the amount of money paid by the publicity agencies to the web sites depends on the number of clients which visited the sites. In this paper we consider a generalization of the metering...
A particularly suitable design strategy for constructing a ro- bust distributed algorithm is to endow it with a self-stabilization pro- perty. Such a property guarantees that the system will always return to and stay within a specified set of legal states within bounded time re- gardless of its initial state. A self-stabilizing application therefore has the potential of recovering from the effects...
Refining self-stabilizing algorithms which use tighter schedul- ing constraints (weaker daemon) into corresponding algorithms for weak- er or no scheduling constraints (stronger daemon), while preserving the stabilization property, is useful and challenging. Designing transforma- tion techniques for these refinements has been the subject of serious in- vestigations in recent years. This paper proposes...
A graph G with n vertices and maximum degree δG cannot be given weak sense of direction using less than δG colours. It is known that n colours are always sufficient, and it was conjectured that just δG + 1 are really needed, that is, one more colour is sufficient. Nonetheless, it has just been shown [2] that for sufficiently large n there are graphs requiring Ω(n/log n) more colours than δG. In this...
Rumor mongering (also known as gossip) is an epidemiolog- ical protocol that implements broadcasting with a reliability that can be very high. Rumor mongering is attractive because it is generic, scalable, adapts well to failures and recoveries, and has a reliability that gracefully degrades with the number of failures in a run. However, rumor mongering uses random selection for communications...
We consider the problem of generic broadcast in asynchronous systems with crashes, a problem that was first studied in [12]. Roughly speaking, given a “conflict” relation on the set of messages, generic broad- cast ensures that any two messages that conflict are delivered in the same order; messages that do not conflict may be delivered in different order. In this paper, we define what it means for...
We consider the problem of searching for a piece of informa- tion in a fully interconnected computer network (or clique) by exploiting advice about its location from the network nodes. Each node contains a database that “knows” what kind of documents or information are stored in other nodes (e.g. a node could be a Web server that answers queries about documents stored on the Web). The databases in...
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.