Loading...
Please wait, while we are loading the content...
Similar Documents
Efficient Fault-Tolerant Algorithms for Distributed Resource Allocation (1995)
| Content Provider | CiteSeerX |
|---|---|
| Author | Choy, Manhoi Singh, Ambuj K. |
| Abstract | this article, we first confine our attention to this particular problem and develop a suite of efficient and fault-tolerant algorithms for it. Later, we consider other process synchronization problems in distributed systems and solve them through transformations based on the these algorithms. Some of the existing criteria to measure the performance of the solutions to the dining philosophers problem are response time [Lynch 1980], which measures the time delay between a process wishing to access the resources and it actually being able to do so, and message complexity (or economy [Chandy and Misra 1984]), which measures the number of messages sent or received by a process during each access to shared resources. We introduce a new criterion, failure locality, which measures the effect of process failures. In a solution with a small failure locality, a process is less likely to be affected by the failure of other processes. We examine these criteria in more detail next. Response time quantifies how long it takes a process to access the resources it has requested. In order to measure time in an asynchronous system, we assume bounds on the message delivery time in the communication network and the time for which a process holds onto requested resources after it has been granted exclusive access to them. Treating these bounds as constants and assuming local processing time to be negligible, it is possible to express the response time of an algorithm in terms of ffi, the maximum degree of the underlying conflict graph. A lower bound of \Omega\Gamma ffi) |
| File Format | |
| Volume Number | 17 |
| Journal | ACM Transactions on Programming Languages and Systems |
| Language | English |
| Publisher Date | 1995-01-01 |
| Access Restriction | Open |
| Subject Keyword | Distributed Resource Allocation Efficient Fault-tolerant Algorithm Time Delay Response Time Lynch Economy Chandy Philosopher Problem Small Failure Locality Underlying Conflict Graph Requested Resource Failure Locality Communication Network Message Delivery Time Message Complexity Process Synchronization Problem Distributed System Response Time Asynchronous System Maximum Degree Particular Problem Fault-tolerant Algorithm Process Failure Exclusive Access Local Processing Time New Criterion Omega Gamma Ffi Response Time Quantifies |
| Content Type | Text |
| Resource Type | Article |
