The extended BG-simulation and the characterization of t-resiliency

ABSTRACT

A distributed task T on n processors is an input/output relation between a collection of processors' inputs and outputs. While all tasks are solvable if no processor may ever crash, the FLP result revealed that the possibility of a failure of just a single processor precludes a solution to the task of consensus. That is consensus is not solvable 1-resiliently. Yet, some nontrivial tasks are wait-free solvable, i.e. n-1-resiliently. What tasks are solvable if at most t processors may crash? I.e. what tasks are solvable t-resiliently? The Herlihy-Shavit condition characterizes wait-free solvability, i.e., when t=n-1. The Borowsky-Gafni (BG) simulation extends this characterization to the t-resilient case for the case "colorless" tasks - tasks like consensus in which one processor can adopt the output of any other processor. It does this by reducing questions about t-resilient solvability, to a question of wait-free solvability. The latter question has been characterized. In this paper, we amend the BG-simulation to result in the Extended-BG-simulation, an extension that yields a full characterization of t-resilient solvability: A task T on n processors is solvable t-resiliently iff all tasks T' on t+1 simulators s₀,..., s_t created as follows are wait-free solvable. Simulator s_i is given an input of processor p_i as well as the input to a set of processors of size n-(t+1) with ids higher than i. Simulator s_i outputs for p_i as well as for a (possibly different) set of processors of size n-(t+1) with ids higher than i. The input/output of the t+1 simulators have to be a projection of a single original input/output tuple-pair in T. We demonstrate the convenience that the characterization provides, in two ways. First, we prove a new equivalence result: We show that n processes can solve t-resiliently weak renaming with n+(t+1)-2 names, where n>1 and 0

REFERENCES

• 1: Yehuda Afek , Danny Dolev , Hagit Attiya , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.1-13, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93394]
• 2: Elizabeth Borowsky , Eli Gafni, Generalized FLP impossibility result for t-resilient asynchronous computations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.91-100, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167119]
• 3: BERGE, C., Graphs and Hypergraphs.,North-Holland, Amsterdam, 1973
• 4: M Loui, H Abu-Amara,Memory Requirements for Agreement Among Unreliable Asynchronous Processes,Advances in Computing Research, JAI (1987).
• 5: Gafni E., Rajsbaum S. and Herlihy M., Subconsensus Tasks: Renaming Is Weaker Than Set Agreement.,DISC 2006: 329--338
• 6: E. Borowsky , E. Gafni , N. Lynch , S. Rajsbaum, The BG distributed simulation algorithm, Distributed Computing, v.14 n.3, p.127-146, October, 2001 [doi>10.1007/PL00008933]
• 7: Armando Castaneda and Sergio Rajsbaum, New Combinatorial Topology Upper and Lower Bounds for Renaming. to appear in PODC 2008.
• 8: Hagit Attiya , Amotz Bar-Noy , Danny Dolev, Sharing memory robustly in message-passing systems, Journal of the ACM (JACM), v.42 n.1, p.124-142, Jan. 1995 [doi>10.1145/200836.200869]
• 9: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 10: Attiya H.,Private Communication,August, 2005.
• 11: Maurice Herlihy , Nir Shavit, The topological structure of asynchronous computability, Journal of the ACM (JACM), v.46 n.6, p.858-923, Nov. 1999 [doi>10.1145/331524.331529]
• 12: Hagit Attiya , Amotz Bar-Noy , Danny Dolev , David Peleg , Rüdiger Reischuk, Renaming in an asynchronous environment, Journal of the ACM (JACM), v.37 n.3, p.524-548, July 1990 [doi>10.1145/79147.79158]
• 13: Eli Gafni, Round-by-round fault detectors (extended abstract): unifying synchrony and asynchrony, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.143-152, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277724]
• 14: Ofer Biran , Shlomo Moran , Shmuel Zaks, A combinatorial characterization of the distributed tasks which are solvable in the presence of one faulty processor, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.263-275, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62590]
• 15: Maurice Herlihy , Sergio Rajsbaum, The decidability of distributed decision tasks (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.589-598, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258652]
• 16: Eli Gafni, Elias Koutsoupias: 3-Processor Tasks Are Undecidable (Abstract). PODC 1995: 271
• 17: Eli Gafni , Elias Koutsoupias, Three-Processor Tasks Are Undecidable, SIAM Journal on Computing, v.28 n.3, p.970-983, Feb. 1999 [doi>10.1137/S0097539796305766]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Relations between models

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Computability theory

General Terms:
Algorithms, Performance, Theory

Keywords:
decidability, renaming, solvability, symmetry breaking, t-resiliency, wait-freedom