SwarmDAG: A Partition Tolerant Distributed Ledger Protocol for Swarm Robotics

  • 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
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.

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