Identifying what problems can be solved in a given distributed system is a central question in distributed computing. In this series of works, we study this question in the context of asynchronous fault tolerant systems that can execute consensus. These systems can be those executing deterministic protocols with access to a consensus routine or those running randomized error-free protocols. A previous work handled the class of distributed decision tasks. In these tasks, each processor receives one local input and has to respond with one local output. In an interactive distributed task each of n processors receives a sequence of local inputs and has to respond on line with an output for every new input (before getting its next input). Different processors can be at different stages concurrently, so that additional inputs are received by fast processors while slow processors are still working on early inputs. An interactive task is called finite if the number of local inputs (and outputs) is finite. Interactive tasks can neither be described as a single huge decision task nor be decomposed into distinct, independent decision tasks. The main result of this work is an exact characterization of the finite interactive tasks which can be solved by t-resilient protocols in either of the above two models. The major tool we use in the characterization is a directed acyclic graph that is associated with an interactive task. Properties of this graph are used to determine the resiliency of the task and to devise a "generic" resilient algorithm which solves such tasks. This generic algorithm can be viewed as a repeated, deterministic reduction to a consensus subroutine. This implies that any finite interactive task is solvable by randomized error-free protocols iff it is solvable by deterministic protocols with access to consensus.

Article Free Access Share on Resilience of general interactive tasks Authors: Benny Chor Dept. of Computer Science, Technion, Haifa 32000, Israel Dept. of Computer Science, Technion, Haifa 32000, IsraelView Profile , Lee-Bath Nelson Graduate School of Business, Stanford University, CA Graduate School of Business, Stanford University, CAView Profile Authors Info & Claims PODC '94: Proceedings of the thirteenth annual ACM symposium on Principles of distributed computingAugust 1994 Pages 173–182https://doi.org/10.1145/197917.198085Published:14 August 1994Publication History 0citation162DownloadsMetricsTotal Citations0Total Downloads162Last 12 Months5Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF