Skip to main content

ASU Global menu

Skip to Content Report an accessibility problem ASU Home My ASU Colleges and Schools Sign In
Arizona State University Arizona State University
ASU Library KEEP

Main navigation

Home Browse Collections Share Your Work
Copyright Describe Your Materials File Formats Open Access Repository Practices Share Your Materials Terms of Deposit API Documentation
Skip to Content Report an accessibility problem ASU Home My ASU Colleges and Schools Sign In
  1. KEEP
  2. Theses and Dissertations
  3. Barrett, The Honors College Thesis/Creative Project Collection
  4. Compression in Self-Organizing Particle Systems
  5. Full metadata

Compression in Self-Organizing Particle Systems

Full metadata

Description

Many programmable matter systems have been proposed and realized recently, each often tailored toward a particular task or physical setting. In our work on self-organizing particle systems, we abstract away from specific settings and instead describe programmable matter as a collection of simple computational elements (to be referred to as particles) with limited computational power that each perform fully distributed, local, asynchronous algorithms to solve system-wide problems of movement, configuration, and coordination. In this thesis, we focus on the compression problem, in which the particle system gathers as tightly together as possible, as in a sphere or its equivalent in the presence of some underlying geometry. While there are many ways to formalize what it means for a particle system to be compressed, we address three different notions of compression: (1) local compression, in which each individual particle utilizes local rules to create an overall convex structure containing no holes, (2) hole elimination, in which the particle system seeks to detect and eliminate any holes it contains, and (3) alpha-compression, in which the particle system seeks to shrink its perimeter to be within a constant factor of the minimum possible value. We analyze the behavior of each of these algorithms, examining correctness and convergence where appropriate. In the case of the Markov Chain Algorithm for Compression, we provide improvements to the original bounds for the bias parameter lambda which influences the system to either compress or expand. Lastly, we briefly discuss contributions to the problem of leader election--in which a particle system elects a single leader--since it acts as an important prerequisite for compression algorithms that use a predetermined seed particle.

Date Created
2016-05
Contributors
  • Daymude, Joshua Jungwoo (Author)
  • Richa, Andrea (Thesis director)
  • Kierstead, Henry (Committee member)
  • Computer Science and Engineering Program (Contributor)
  • School of Mathematical and Statistical Sciences (Contributor)
  • Barrett, The Honors College (Contributor)
Topical Subject
  • Mathematics
  • Programmable Matter
  • Algorithms
  • Theory
  • Computer Science
Resource Type
Text
Extent
37 pages
Language
eng
Copyright Statement
In Copyright
Primary Member of
Barrett, The Honors College Thesis/Creative Project Collection
Series
Academic Year 2015-2016
Handle
https://hdl.handle.net/2286/R.I.37219
Level of coding
minimal
Cataloging Standards
asu1
System Created
  • 2017-10-30 02:50:57
System Modified
  • 2021-08-11 04:09:57
  •     
  • 10 months 2 weeks ago
Additional Formats
  • OAI Dublin Core
  • MODS XML

Quick actions

About this item

Overview
 Copy permalink

Share this content

Feedback

ASU University Technology Office Arizona State University.
KEEP

Contact Us

Repository Services
Home KEEP PRISM Dataverse
Resources
Terms of Deposit Sharing Materials: ASU Digital Repository Guide Open Access at ASU

The ASU Library acknowledges the twenty-two Native Nations that have inhabited this land for centuries. Arizona State University's four campuses are located in the Salt River Valley on ancestral territories of Indigenous peoples, including the Akimel O’odham (Pima) and Pee Posh (Maricopa) Indian Communities, whose care and keeping of these lands allows us to be here today. ASU Library acknowledges the sovereignty of these nations and seeks to foster an environment of success and possibility for Native American students and patrons. We are advocates for the incorporation of Indigenous knowledge systems and research methodologies within contemporary library practice. ASU Library welcomes members of the Akimel O’odham and Pee Posh, and all Native nations to the Library.

Number one in the U.S. for innovation. #1 ASU, #2 Stanford, #3 MIT. - U.S. News and World Report, 5 years, 2016-2020
Maps and Locations Jobs Directory Contact ASU My ASU
Copyright and Trademark Accessibility Privacy Terms of Use Emergency