Thumbnail
Access Restriction
Open

Author Aguilera, Marcos Kawazoe ♦ Kawazoe, Marcos ♦ Wei, Aguilera ♦ Toueg, Chen Sam
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Crash-recovery Model ♦ Failure Detection ♦ Asynchronous System ♦ New Failure Detector ♦ Next Determine ♦ Stable Storage ♦ Failure Detector ♦ Unreliable Failure Detector ♦ Maximum Message Delay ♦ Failure Detector Mistake ♦ Condition Stable Storage ♦ Algorithm Tolerate Link Failure
Abstract . We study the problems of failure detection and consensus in asynchronous systems in which processes may crash and recover, and links may lose messages. We first propose new failure detectors that are particularly suitable to the crash-recovery model. We next determine under what conditions stable storage is necessary to solve consensus in this model. Using the new failure detectors, we give two consensus algorithms that match these conditions: one requires stable storage and the other does not. Both algorithms tolerate link failures and are particularly efficient in the runs that are most likely in practice --- those with no failures or failure detector mistakes. In such runs, consensus is achieved within 3# time and with 4n messages, where # is the maximum message delay and n is the number of processes in the system. 1 Introduction The problem of solving consensus in asynchronous systems with unreliable failure detectors (i.e., failure detectors that make mistakes) was f...
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Publisher Date 1998-01-01