Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Solvability in asynchronous environments - II: Finite interactive tasks
Autore:
Chor, B; Nelson, LB;
Indirizzi:
Massey Univ, Inst Fundamental Sci, Palmerston North, New Zealand Massey Univ Palmerston North New Zealand Palmerston North, New Zealand Stanford Univ, Grad Sch Business, Stanford, CA 94305 USA Stanford Univ Stanford CA USA 94305 Sch Business, Stanford, CA 94305 USA Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel Technion Israel Inst Technol Haifa Israel IL-32000 L-32000 Haifa, Israel
Titolo Testata:
SIAM JOURNAL ON COMPUTING
fascicolo: 2, volume: 29, anno: 1999,
pagine: 351 - 377
SICI:
0097-5397(199912)29:2<351:SIAE-I>2.0.ZU;2-M
Fonte:
ISI
Lingua:
ENG
Soggetto:
RANDOMIZED CONSENSUS; SHARED-MEMORY; DISTRIBUTED CONSENSUS; IMPOSSIBILITY; SYSTEMS;
Keywords:
solvability; asynchronous distributed systems; fault tolerance; randomized algorithms; consensus; interactive tasks; decision tasks; adversary scheduler;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
30
Recensione:
Indirizzi per estratti:
Indirizzo: Chor, B Massey Univ, Inst Fundamental Sci, Private Bag 11-222, Palmerston North, New Zealand Massey Univ Private Bag 11-222 Palmerston North New Zealand land
Citazione:
B. Chor e L.B. Nelson, "Solvability in asynchronous environments - II: Finite interactive tasks", SIAM J COMP, 29(2), 1999, pp. 351-377

Abstract

Identifying what problems can be solved in a given distributed system is acentral question in distributed computing. In this series of works, we study this question in the context of asynchronous fault tolerant systems thatcan 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 decisiontask 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. Propertiesof 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 consensussubroutine. 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.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 20/09/20 alle ore 19:44:58