Abstract
Inspired by the characteristics of biologically-motivated systems consisting of autonomous agents, we define the notion of stabilizing consensus in fully decentralized and highly dynamic ad hoc systems. Stabilizing consensus requires non-faulty nodes to eventually agree on one of their inputs, but individual nodes do not necessarily know when agreement is reached. First we show that, similar to the original consensus problem in the synchronous model, there exist deterministic solutions to the stabilizing consensus problem tolerating crash faults. Similarly, stabilizing consensus can also be solved deterministically in presence of Byzantine faults with the assumption that n > 3f where n is the number of nodes and f is the number of faulty nodes. Our main result is a Byzantine consensus protocol in a model in which the input to each node can change finitely many times during execution and eventually stabilizes. Finally we present an impossibility result for stabilizing consensus in systems of identical nodes.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Lamport, L., Shostak, R., Pease, M.: The byzantine generals problem. In: Suri, N., Walter, C.J., Hugue, M.M. (eds.) Advances in Ultra-Dependable Distributed Systems, IEEE Computer Society Press, Los Alamitos (1995)
Pease, M., Shostak, R., Lamport, L.: Reaching agreement in the presence of faults. Journal of the ACM 27, 228–234 (1980)
Dolev, D.: The byzantine generals strike again. Journal of Algorithms 3(1), 14–30 (1982)
Dolev, D., Strong, H.R.: Polynomial algorithms for multiple processor agreement. In: Proceedings of the 14th annual ACM symposium on Theory of computing, San Francisco, California, United States, pp. 401–407 (1982)
Dolev, D., Fischer, M.J., Fowler, R., Lynch, N.A., Strong, H.R.: An efficient algorithm for byzantine agreement without authentication. Information and Control 52(3), 257–274 (1982)
Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. Journal of the ACM 32(2), 374–382 (1985)
Fischer, M.J.: The consensus problem in unreliable distributed systems (a brief survey). Technical Report YALEU/DCS/TR-273, Yale University (1983)
Vicsek, T., Czirók, A., Ben-Jacob, E., Cohen, I., Shochet, O.: Novel Type of Phase Transition in a System of Self-Driven Particles. Physical Review Letters 75, 1226–1229 (1995)
Jadbabaie, A., Lin, J., Morse, A.: Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transactions on Automatic Control (2002)
Chandra, T.D., Toueg, S.: Unreliable failure detectors for reliable distributed systems. Journal of the ACM 43(2), 225–267 (1996)
Chandra, T.D., Hadzilacos, V., Toueg, S.: The weakest failure detector for solving consensus. Journal of the ACM 43(4), 685–722 (1996)
Ben-Or, M.: Another advantage of free choice: Completely asynchronous agreement protocols. In: Proceedings of the Second Annual ACM Synmposium on Principles of Distributed Computing, Montreal, Quebec, Canada, pp. 27–30 (1983)
Rabin, M.O.: Randomized byzantine generals. In: 24th Annual Symposium on Foundations of Computer Science, pp. 403–409. IEEE, Los Alamitos (1983)
Feldman, P.N.: Optimal Algorithms for Byzantine Agreement. PhD thesis, Massachusetts Institute of Technology (1988)
Chaudhuri, S.: More choices allow more faults: Set consensus problems in totally asynchronous systems. Information and Computation 105(1), 132–158 (1993)
Dolev, D., Lynch, N.A., Pinter, S.S., Stark, E.W., Weihl, W.E.: Reaching approximate agreement in the presence of faults. Journal of the ACM 33(3), 499–516 (1986)
Lamport, L.: The part-time parliament. ACM Transaction on Computer Systems 16(2), 133–169 (1998)
Beraldi, R., Baldoni, R.: The handbook of ad hoc wireless networks. In: The handbook of ad hoc wireless networks, pp. 127–148. CRC Press, Inc., Boca Raton (2003)
Royer, E., Toh, C.: A review of current routing protocols for ad-hoc mobile wireless networks. In: IEEE Personal Communications, pp. 46–55 (1999)
Williams, B., Camp, T.: Comparison of broadcasting techniques for mobile ad hoc networks. In: ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 194–205 (2002)
Barbara, D.: Mobile computing and databases - a survey. Knowledge and Data Engineering 11(1), 108–117 (1999)
Bobineau, C., Pucheral, P., Abdallah, M.: A unilateral commit protocol for mobile and disconnected computing. In: 12th International Conference on Parallel and Distributed Computing Systems (2000)
Pitoura, E., Bhargava, B.K.: Data consistency in intermittently connected distributed systems. Knowledge and Data Engineering 11(6), 896–915 (1999)
Briesemeister, L.: Group Membership and Communication in Highly Mobile Ad Hoc Networks. PhD thesis, School of Electrical Engineering and Computer Science, Technical University of Berlin, Germany (2001)
Dolev, S., Schiller, E., Welch, J.: Random walk for self-stabilizing group communication in ad-hoc networks. In: 21st Symposium on Reliable Distributed Systems (2002)
Malpani, N., Welch, J.L., Vaidya, N.H.: Leader election algorithms for mobile ad hoc networks. In: Proc. Fourth International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 96–103 (2000)
Walter, J.E., Welch, J.L., Vaidya, N.H.: A mutual exclusion algorithm for ad hoc mobile networks. Wireless Networks 7(6), 585–600 (2001)
Angluin, D., Aspnes, J., Fischer, M.J., Jiang, H.: Self-stabilizing population protocols. In: 9th International Conference on Principles of Distributed Systems, pp. 79–90 (2005)
Basile, C., Killijian, M.O., Powell, D.: A survey of dependability issues in mobile wireless networks. Technical report, Laboratory for Analysis and Architecture of Systems, National Center for Scientific Research, Toulouse, France (2003)
Dolev, D., Strong, H.R.: Authenticated algorithms for byzantine agreement. SIAM Journal of Computing 12(4), 656–666 (1983)
Fischer, M.J., Lynch, N.A., Merritt, M.: Easy impossibility proofs for distributed consensus problems. Distributed Computing 1(1), 26–39 (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Angluin, D., Fischer, M.J., Jiang, H. (2006). Stabilizing Consensus in Mobile Networks. In: Gibbons, P.B., Abdelzaher, T., Aspnes, J., Rao, R. (eds) Distributed Computing in Sensor Systems. DCOSS 2006. Lecture Notes in Computer Science, vol 4026. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11776178_3
Download citation
DOI: https://doi.org/10.1007/11776178_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-35227-3
Online ISBN: 978-3-540-35228-0
eBook Packages: Computer ScienceComputer Science (R0)