It has recently been shown that fair exchange, a security problem in distributed systems, can be reduced to a fault tolerance problem, namely a special form of distributed consensus. The reduction uses the concept of security modules which reduce the type and nature of adversarial behavior to two standard fault-assumptions: message omission and process crash. In this paper, we investigate the feasibility of solving consensus in asynchronous systems in which crash and message omission faults may occur. Due to the impossibility result of consensus in such systems, following the lines of unreliable failure detectors of Chandra and Toueg, we add to the system a distributed device that gives information about the failure of other processes. Then we give an algorithm using this device to solve the consensus problem. Finally, we show how to implement such a device in an asynchronous system using some weak timing assumptions. © Springer-Verlag Berlin Heidelberg 2005.

Delporte-Gallet C., Fauconnier H., Freiling F.C.

703.pdf    Gửi cho bạn bè

Từ khóa : Algorithms; Asynchronous sequential logic; Distributed computer systems; Error detection; Fault tolerant computer systems; Problem solving; Consensus; Failure detection; Message omission; Omission failure environments; Computer system recovery