BeRGeR: Byzantine-Robust Geometric Routing
Pages 247 - 263
Abstract
We present BeRGeR: the first asynchronous geometric routing algorithm that guarantees delivery of a message despite a Byzantine fault without relying on cryptographic primitives or randomization. The communication graph is a planar embedding that remains three-connected if all edges intersecting the source-target line segment are removed. We prove the algorithm correct and estimate its message complexity.
References
[1]
Imieliński, T., Navas, J.C.: Gps-based geographic addressing, routing, and resource discovery. Commun. ACM. 42(4), 86–92 (1999)
[2]
Ko, Y.B., Vaidya, N.H.: Geocasting in mobile ad hoc networks: Location-based multicast algorithms. In: Proceedings WMCSA 1999 Second IEEE Workshop on Mobile Computing Systems and Applications, pp. 101–110. IEEE (1999)
[3]
Ko, Y.B., Vaidya, N.H.: Location-aided routing (lar) in mobile ad hoc networks. Wirel. Networks 6(4), 307–321 (2000)
[4]
Kranakis, E., Singh, H., Urrutia, J.: Compass routing on geometric networks. In: Proceedings of 11th Canadian Conference on Computational Geometry, Citeseer (1999)
[5]
Johnson, D.B., Maltz, D.A.: Dynamic source routing in Ad Hoc wireless networks. In: Imielinski, T., Korth, H.F. (eds.) Mobile Computing. The Kluwer International Series in Engineering and Computer Science, vol. 353, pp. 153–181. Springer, Boston, MA (1996).
[6]
Perkins, C., Royer, E.: Ad-hoc on-demand distance vector routing. In: Proceedings WMCSA’99. Second IEEE Workshop on Mobile Computing Systems and Applications, pp. 90–100 (1999)
[7]
Karagiannis G et al. Vehicular networking: a survey and tutorial on requirements, architectures, challenges, standards and solutions IEEE Commun. Surv. Tutorials 2011 13 4 584-616
[8]
Arora A et al. A line in the sand: a wireless sensor networking for target detection, classification, and tracking Comput. Netw. Special Issue Future Adv. Mil. Commun. Technol. 2004 46 5 605-634
[9]
Bose P, Morin P, Stojmenović I, and Urrutia J Routing with guaranteed delivery in ad hoc wireless networks Wireless Netw. 2001 7 6 609-616
[10]
Liu, P.C., Geldmacher, R.C.: On the deletion of nonplanar edges of a graph. In: Proceedings of the 10th Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp. 727–738 (1979)
[11]
Bose P, Morin P, Stojmenovic I, and Urrutia J Routing with guaranteed delivery in ad hoc wireless networks J. Mobile Commun. Comput. Inf. 2001 7 6 48-55
[12]
Ruben Gabriel, K., Sokal, R.R.: A new statistical approach to geographic variation analysis. Syst. Biol. 18(3), 259–278 (1969)
[13]
Karp, B., Kung, H.T.: GPSR: greedy perimeter stateless routing for wireless networks. In: Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobille Computing and Networking (MobiCom), pp. 243–254. ACM Press, August 2000
[14]
Toussaint, G.T.: The relative neighbourhood graph of a finite planar set. Pattern Recogn. 12(4), 261–268 (1980)
[15]
Kuhn, F., Wattenhofer, R., Zhang, Y., Zollinger, A.: Geometric ad-hoc routing: of theory and practice. In: Proceedings of the Twenty-Second Annual Symposium on Principles of Distributed Computing, pp. 63–72 (2003)
[16]
Clouser T, Miyashita M, and Nesterenko M Concurrent face traversal for efficient geometric routing J. Parall. Distrib. Comput. 2012 72 5 627-636
[17]
Lamport L, Shostak R, and Pease M The byzantine generals problem ACM Trans. Program. Lang. Syst. 1982 4 3 382-401
[18]
Pease M, Shostak R, and Lamport L Reaching agreement in the presence of faults J. ACM (JACM) 1980 27 2 228-234
[19]
Sánchez-Carmona A, Robles S, and Borrego C Privhab+: a secure geographic routing protocol for DTN Comput. Commun. 2016 78 56-73
[20]
Pathak, V., Yao, D., Iftode, L.: Securing location aware services over VANET using geographical secure path routing. In: 2008 IEEE International Conference on Vehicular Electronics and Safety, pp. 346–353. IEEE (2008)
[21]
Dolev, D., Raymond Strong, H.: Authenticated algorithms for byzantine agreement. SIAM J. Comput. 12(4), 656–666 (1983)
[22]
Katz J and Koo C-Y On expected constant-round protocols for byzantine agreement J. Comput. Syst. Sci. 2009 75 2 91-112
[23]
Ben-Or, M.: Another advantage of free choice (extended abstract) completely asynchronous agreement protocols. In: Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, pp. 27–30 (1983)
[24]
Feldman P and Micali S An optimal probabilistic protocol for synchronous byzantine agreement SIAM J. Comput. 1997 26 4 873-933
[25]
Castro, M., Liskov, B.: Practical byzantine fault tolerance. In: Proceedings of the Third Symposium on Operating Systems Design and Implementation, OSDI 1999, pp. 173–186. USENIX Association, USA (1999)
[26]
Dolev D The byzantine generals strike again J. Algorithms 1982 3 1 14-30
[27]
Fischer, M.J., Lynch, N.A., Merritt, M.: Easy impossibility proofs for distributed consensus problems. Distrib. Comput. 1, 26–39 (1986)
[28]
Adnan, A.I., Hanapi, Z.M., Othman, M., Zukarnain, Z.A.: A secure region-based geographic routing protocol (SRBGR) for wireless sensor networks. PloS ONE 12(1), e0170273 (2017)
[29]
Boulaiche M and Bouallouche-Medjkoune L HSecGR: highly secure geographic routing J. Netw. Comput. Appl. 2017 80 189-199
[30]
Maurer A and Tixeuil S Containing byzantine failures with control zones IEEE Trans. Parallel Distrib. Syst. 2014 26 2 362-370
[31]
Zahariadis, T., Trakadas, P., Leligou, H.C., Maniatis, S., Karkazis, P.: A novel trust-aware geographical routing scheme for wireless sensor networks. Wirel. Personal Commun. 69, 805–826 (2013)
[32]
García-Otero M et al. Secure geographic routing in ad hoc and wireless sensor networks EURASIP J. Wirel. Commun. Networking 2010 2010 1-12
[33]
Leinmüller, T., Maihöfer, C., Schoch, E., Kargl, F.: Improved security in geographic ad hoc routing through autonomous position verification. In: Proceedings of the 3rd International workshop on Vehicular Ad Hoc Networks, pp. 57–66 (2006)
[34]
Vora A and Nesterenko M Secure location verification using radio broadcast IEEE Trans. Dependable Secure Comput. 2006 3 4 377-385
[35]
Oglio, J., Hood, K., Sharma, G., Nesterenko, M.: Byzantine heoconsensus. In: Echihabi, K., Meyer, R. (eds.) Networked Systems, NETYS 2021, LNCS, vol. 12754, pp 19–35. Springer, Cham (2021).
[36]
Zaz B and Nesterenko M Using Braids for Byzantine Resistant Geographic Routing on Polyhedral Networks 2024 San Francisco, USA In Joint Mathematics Meet
[37]
Sanchez, J.A., Ruiz, P.M., Stojmenovic, I.: GMR: geographic multicast routing for wireless sensor networks. In: 3d IEEE Communication Society Conference on Sensors and Ad Hoc Communications and Networks (SeCon), pp. 20–29. IEEE, September 2006
[38]
Mauve M, Füßler H, Widmer J, and Lang T Position-based multicast routing for mobile ad-hoc networks Mobile Comput. Commun. Rev. 2003 7 3 53-55
[39]
Wu, S., Candan, K.S.: GMP: distributed geographic multicast routing in wireless sensor networks. In: 26th IEEE International Conference on Distributed Computing Systems (26th ICDCS’06), p. 49, Lisboa, Portugal, IEEE Computer Society, July 2006
[40]
Chen, K., Nahrstedt, K.: Effective location-guided tree construction algorithms for small group multicast in MANET. In: Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Society (INFOCOM-02), volume 3 of Proceedings IEEE INFOCOM 2002, pp. 1180–1189, Piscataway, NJ, USA, IEEE Computer Society, 23–27 June 2002
[41]
Adamek, J., Nesterenko, M., Robinson, J.S., Tixeuil, S.: Concurrent geometric multicasting. In: Proceedings of the 19th International Conference on Distributed Computing and Networking, pp. 1–10 (2018)
[42]
Lian, J., Naik, K., Liu, Y., Chen, L.: Virtual surrounding face geocasting with guaranteed message delivery for ad hoc and sensor networks. In: Proceedings of the 2006 14th IEEE International Conference on Network Protocols, ICNP 2006, pp. 198–207. IEEE (2006)
[43]
Adamek, J., Nesterenko, M., Robinson, J.S., Tixeuil, S.: Stateless reliable geocasting. In: 2017 IEEE 36th Symposium on Reliable Distributed Systems (SRDS), pp. 44–53. IEEE (2017)
[44]
Clouser T, Vora A, Fox T, and Nesterenko M Void traversal for efficient non-planar geometric routing Ad Hoc Netw. 2013 11 8 2345-2355
[45]
Kuhn, F., Wattenhofer, R., Zollinger, A.: Ad-hoc networks beyond unit disk graphs. In: Proceedings of the 2003 Joint Workshop on Foundations of Mobile Computing, pp. 69–78 (2003)
[46]
Kim, Y.J., Govindan, R., Karp, B., Shenker, S.: Geographic routing made practical. In: Proceedings of the 2nd Conference on Symposium on Networked Systems Design and Implementation, vol. 2, pp. 217–230 (2005)
[47]
Driscoll, K., Hall, B., Sivencrona, H., Zumsteg, P.: Byzantine fault tolerance, from theory to reality. In: Anderson, S., Felici, M., Littlewood, B. (eds.) SAFECOMP 2003. LNCS, vol. 2788, pp. 235–248. Springer, Heidelberg (2003).
Index Terms
- BeRGeR: Byzantine-Robust Geometric Routing
Index terms have been assigned to the content through auto-classification.
Recommendations
On a conjecture related to geometric routing
Algorithmic aspects of wireless sensor networksWe conjecture that any planar 3-connected graph can be embedded in the plane in such a way that for any nodes s and t, there is a path from s to t such that the Euclidean distance to t decreases monotonically along the path. A consequence of this ...
Topology of Geometric Joins
We consider the geometric join of a family of subsets of the Euclidean space. This is a construction frequently used in the (colorful) Carathéodory and Tverberg theorems, and their relatives. We conjecture that when the family has at least $$d+1$$d+1 ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2024
275 pages
ISBN:978-3-031-67320-7
DOI:10.1007/978-3-031-67321-4
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 25 August 2024
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 09 Jan 2025