Distributed consensus in the presence of sectional faults

ABSTRACT

Consider a synchronous network of n players, each with a local input. The goal of distributed consensus is to globally agree on one of the valid inputs even if some non-trivial subset of the players are faulty. By valid input, we mean the input of any non-faulty player. Extant results in Byzantine agreement literature capture the behaviour of faulty players in an "all-or-nothing" fashion. For instance, a (Byzantine) faulty player is completely unconstrained and could behave differently with different players. This leads to a gross underestimation of the achievable fault-tolerance. In this work, we propose a fault-model that considerably improves the estimation of fault-tolerance and helps capture real-life scenarios better. For instance, if two (honest) players were part of the same LAN (which is essentially a broadcast network), it is impossible for a external faulty player to behave differently with these two players (though the faulty player may behave with "equal" malice with both these players!). Among our results, we introduce the sectional fault-model that is more general and can capture practical scenarios not captured by any extant model. We provide a complete characterization of the tolerable faults and present efficient protocols to achieve consensus. We remark that the results of this paper strictly generalize the extant characterizations of fault-tolerance. For example, consider a network of four players P₁, P₂, P₃ and P₄, under the corrupting influence of a Byzantine adversary given by the adversary structure A = {(P₁, P₂), (P₂, P₃), (P₄)}. Agreement is impossible in such a scenario, since the three sets from A cover the player set. However, it would be evident from our results that consensus in the above scenario was indeed possible if (and only if) the players P₁, P₃ and P₄ belonged to a single LAN in the network!

REFERENCES

• 1: Bernd Altmann , Matthias Fitzi , Ueli M. Maurer, Byzantine Agreement Secure against General Adversaries in the Dual Failure Model, Proceedings of the 13th International Symposium on Distributed Computing, p.123-137, September 27-29, 1999
• 2: O. Babaoglu and R. Drummond. Streets of Byzantium: Network Architectures for Reliable Broadcast. IEEE Transactions on Software Engineering, SE-11(6):546--554, June 1985.
• 3: Piotr Berman , Juan A. Garay, Asymptotically Optimal Distributed Consensus (Extended Abstract), Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.80-94, July 11-15, 1989
• 4: Ran Canetti , Uri Feige , Oded Goldreich , Moni Naor, Adaptively secure multi-party computation, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.639-648, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238015]
• 5: D. Dolev and H. R. Strong. Authenticated algorithms for byzantine agreement. SIAM Journal of Computing, 12(4):656--666, November 1983.
• 6: Matthias Fitzi , Daniel Gottesman , Martin Hirt , Thomas Holenstein , Adam Smith, Detectable byzantine agreement secure against faulty majorities, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571841]
• 7: Matthias Fitzi , Ueli M. Maurer, Efficient Byzantine Agreement Secure Against General Adversaries, Proceedings of the 12th International Symposium on Distributed Computing, p.134-148, September 24-26, 1998
• 8: Mattias Fitzi , Ueli Maurer, From partial consistency to global broadcast, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.494-503, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335363]
• 9: Juan A. Garay, Reaching (and Maintaining) Agreement in the Presence of Mobile Faults (Extended Abstract), Proceedings of the 8th International Workshop on Distributed Algorithms, p.253-264, September 29-October 01, 1994
• 10: Juan A. Garay , Kenneth J. Perry, A Continuum of Failure Models for Distributed Computing, Proceedings of the 6th International Workshop on Distributed Algorithms, p.153-165, November 02-04, 1992
• 11: Martin Hirt , Ueli Maurer, Complete characterization of adversaries tolerable in secure multi-party computation (extended abstract), Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.25-34, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259412]
• 12: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 13: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 14: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 15: Rüdiger Reischuk, A new solution for the byzantine generals problem, Information and Control, v.64 n.1-3, p.23-42, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80042-5]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Network communication

General Terms:
Design, Performance, Security

Keywords:
distributed consensus, sectional faults