SwarmDAG: A Partition Tolerant Distributed Ledger Protocol for Swarm Robotics

Authors

  • Jason A Tran Ming Hsieh Department of Electrical Engineering, University of Southern California, Los Angeles https://orcid.org/0000-0002-9439-8931
  • Gowri Sankar Ramachandran Center for Cyber-Physical Systems and Internet of Things, University of Southern California, Los Angeles
  • Palash M Shah Ming Hsieh Department of Electrical Engineering, University of Southern California, Los Angeles
  • Claudiu B. Danilov Networks & Cyber Systems Group, Boeing Research and Technology
  • Rodolfo A. Santiago Networks & Cyber Systems Group, Boeing Research and Technology
  • Bhaskar Krishnamachari Ming Hsieh Department of Electrical Engineering, University of Southern California, Los Angeles

DOI:

https://doi.org/10.5195/ledger.2019.174

Keywords:

swarmdag, distributed ledger, partition tolerant, directed acyclic graph, swarm robotics, extended virtual synchrony

Abstract

Blockchain technology has the potential to disrupt applications beyond cryptocurrencies. This work applies the concepts of blockchain technology to swarm robotics applications. Swarm robots typically operate in a distributed fashion, wherein the collaboration and coordination between the robots are essential to accomplishing the application goals. However, robot swarms may experience network partitions either due to navigational and communication challenges or in order to perform certain tasks efficiently. We propose a novel protocol, SwarmDAG, that enables the maintenance of a distributed ledger based on the concept of extended virtual synchrony while managing and tolerating network partitions.

Author Biography

Jason A Tran, Ming Hsieh Department of Electrical Engineering, University of Southern California, Los Angeles

PhD student in the Ming Hsieh Department of Electrical Engineering

References

Amir, Y., Moser, L. E., Melliar-Smith, P. M., Agarwal, D. A., Ciarfella, P. “The Totem Single-Ring Ordering and Membership Protocol.” ACM Trans. Comput. Syst. 13.4 311–342 (1995) http://doi.acm.org/10.1145/210223.210224.

Baird, L. “The Swirlds Hashgraph Consensus Algorithm: Fair, Fast, Byzantine Fault Tolerance.” Swirlds (2016) (accessed 9 March 2019) https://www.swirlds.com/downloads/SWIRLDS-TR-2016-01.pdf.

Brambilla, M., Ferrante, E., Birattari, M., Dorigo, M. “Swarm Robotics: A Review from the Swarm Engineering Perspective.” Swarm Intelligence 7.1 1–41 (2013) https://doi.org/10.1007/s11721-012-0075-2.

Brewer, E. “CAP Twelve Years Later: How the “Rules” Have Changed.” Computer 45.2 23–29 (2012) https:/doi.org/10.1109/MC.2012.37.

Castelló Ferrer, E. “The Blockchain: A New Framework for Robotic Swarm Systems.” arXiv (2016) (accessed 9 March 2019) http://arxiv.org/abs/1608.00695.

Francesca, G., Birattari, M. “Automatic Design of Robot Swarms: Achievements and Challenges.” Frontiers in Robotics and AI 3 29 (2016) https://doi.org/10.3389/frobt.2016.00029.

Lamport, L. “The Part-time Parliament.” ACM Trans. Comput. Syst. 16.2 133–169 (1998) http://doi.acm.org/10.1145/279227.279229.

Li, Z., Wen, G., Duan, Z., Ren, W. “Designing Fully Distributed Consensus Protocols for Linear Multi-Agent Systems With Directed Graphs.” IEEE Transactions on Automatic Control 60.4 1152–1157 (2015) https://doi.org/10.1109/TAC.2014.2350391.

Lopes, Y. K., Trenkwalder, S. M., Leal, A. B., Dodd, T. J., Groß, R. “Supervisory Control Theory Applied to Swarm Robotics.” Swarm Intelligence 10.1 65–97 (2016) https://doi.org/10.1007/s11721-016-0119-0.

Moser, L. E., Amir, Y., Melliar-Smith, P. M., Agarwal, D. A. “Extended Virtual Synchrony.” In 14th International Conference on Distributed Computing Systems IEEE 56–65 (1994) https://doi.org/10.1109/ICDCS.1994.302392.

Ongaro, D., Ousterhout, J. “In Search of an Understandable Consensus Algorithm.” In Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference Berkeley: USENIX Association 305–320 (2014) http://dl.acm.org/citation.cfm?id=2643634.2643666.

Popov, S. “The Tangle.” IOTA (2018) IOTA Whitepaper (accessed 9 March 2019) https://assets.ctfassets.net/r1dr6vzfxhev/2t4uxvsIqk0EUau6g2sw0g/45eae33637ca92f85dd9f4a3a218e1ec/iota1_4_3.pdf.

Pritchett, D. “BASE: An Acid Alternative.” Queue 6.3 48–55 (2008) http://doi.acm.org/10.1145/1394127.1394128.

Silvestre, D., Hespanha, J. P., Silvestre, C. “Broadcast and Gossip Stochastic Average Consensus Algorithms in Directed Topologies.” IEEE Transactions on Control of Network Systems 1–1 (Early Access) https://doi.org/10.1109/TCNS.2018.2839341.

Downloads

Published

2019-04-09

How to Cite

Tran, J. A., Ramachandran, G. S., Shah, P. M., Danilov, C. B., Santiago, R. A., & Krishnamachari, B. (2019). SwarmDAG: A Partition Tolerant Distributed Ledger Protocol for Swarm Robotics. Ledger, 4. https://doi.org/10.5195/ledger.2019.174

Issue

Vol 4, Supplement 1 (2019): Proceedings of the First Symposium on Blockchain and Robotics, MIT Media Lab, 5 December 2018

Section

Proceedings Articles

License

Authors who publish with this journal agree to the following terms:

  1. The Author retains copyright in the Work, where the term “Work” shall include all digital objects that may result in subsequent electronic publication or distribution.
  2. Upon acceptance of the Work, the author shall grant to the Publisher the right of first publication of the Work.
  3. The Author shall grant to the Publisher and its agents the nonexclusive perpetual right and license to publish, archive, and make accessible the Work in whole or in part in all forms of media now or hereafter known under a Creative Commons Attribution 4.0 International License or its equivalent, which, for the avoidance of doubt, allows others to copy, distribute, and transmit the Work under the following conditions:
    1. Attribution—other users must attribute the Work in the manner specified by the author as indicated on the journal Web site;
    with the understanding that the above condition can be waived with permission from the Author and that where the Work or any of its elements is in the public domain under applicable law, that status is in no way affected by the license.
  4. The Author is able to enter into separate, additional contractual arrangements for the nonexclusive distribution of the journal's published version of the Work (e.g., post it to an institutional repository or publish it in a book), as long as there is provided in the document an acknowledgement of its initial publication in this journal.
  5. Authors are permitted and encouraged to post online a prepublication manuscript (but not the Publisher’s final formatted PDF version of the Work) in institutional repositories or on their Websites prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work. Any such posting made before acceptance and publication of the Work shall be updated upon publication to include a reference to the Publisher-assigned DOI (Digital Object Identifier) and a link to the online abstract for the final published Work in the Journal.
  6. Upon Publisher’s request, the Author agrees to furnish promptly to Publisher, at the Author’s own expense, written evidence of the permissions, licenses, and consents for use of third-party material included within the Work, except as determined by Publisher to be covered by the principles of Fair Use.
  7. The Author represents and warrants that:
    1. the Work is the Author’s original work;
    2. the Author has not transferred, and will not transfer, exclusive rights in the Work to any third party;
    3. the Work is not pending review or under consideration by another publisher;
    4. the Work has not previously been published;
    5. the Work contains no misrepresentation or infringement of the Work or property of other authors or third parties; and
    6. the Work contains no libel, invasion of privacy, or other unlawful matter.
  8. The Author agrees to indemnify and hold Publisher harmless from Author’s breach of the representations and warranties contained in Paragraph 6 above, as well as any claim or proceeding relating to Publisher’s use and publication of any content contained in the Work, including third-party content.
  9. The Author agrees to digitally sign the Publisher’s final formatted PDF version of the Work.

Revised 7/16/2018. Revision Description: Removed outdated link.