Brief Announcement: Partial Reversal Acyclicity
Partial Reversal (PR) is a link reversal algorithm which ensures that an initially directed acyclic graph (DAG) is eventually a destination-oriented DAG. While proofs exist to establish the acyclicity property of PR, they rely on assigning labels to either the nodes or the edges in the graph. In thi...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/73185 https://orcid.org/0000-0003-3045-265X https://orcid.org/0000-0003-1261-6681 |
| _version_ | 1826188341867970560 |
|---|---|
| author | Radeva, Tsvetomira Lynch, Nancy Ann |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Radeva, Tsvetomira Lynch, Nancy Ann |
| author_sort | Radeva, Tsvetomira |
| collection | MIT |
| description | Partial Reversal (PR) is a link reversal algorithm which ensures that an initially directed acyclic graph (DAG) is eventually a destination-oriented DAG. While proofs exist to establish the acyclicity property of PR, they rely on assigning labels to either the nodes or the edges in the graph. In this work we show that such labeling is not necessary and outline a simpler direct proof of the acyclicity property. |
| first_indexed | 2024-09-23T07:58:11Z |
| format | Article |
| id | mit-1721.1/73185 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T07:58:11Z |
| publishDate | 2012 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/731852022-09-30T01:22:11Z Brief Announcement: Partial Reversal Acyclicity Radeva, Tsvetomira Lynch, Nancy Ann Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Radeva, Tsvetomira Lynch, Nancy Ann Partial Reversal (PR) is a link reversal algorithm which ensures that an initially directed acyclic graph (DAG) is eventually a destination-oriented DAG. While proofs exist to establish the acyclicity property of PR, they rely on assigning labels to either the nodes or the edges in the graph. In this work we show that such labeling is not necessary and outline a simpler direct proof of the acyclicity property. National Science Foundation (U.S.) (Grant CCF-0726514) United States. Air Force Office of Scientific Research (Grant FA9550-08-1-0159) Akamai Technologies, Inc. (Presidential Fellowship) 2012-09-26T16:23:21Z 2012-09-26T16:23:21Z 2011 2011 Article http://purl.org/eprint/type/ConferencePaper http://hdl.handle.net/1721.1/73185 Tsvetomira Radeva and Nancy Lynch. "Brief Announcement: Partial Reversal Acyclicity." In Proceedings of the 30th annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC '11). ACM, New York, NY, USA, 353-354. https://orcid.org/0000-0003-3045-265X https://orcid.org/0000-0003-1261-6681 en_US http://dx.doi.org/10.1145/1993806.1993880 Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC '11) Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery (ACM) MIT web domain |
| spellingShingle | Radeva, Tsvetomira Lynch, Nancy Ann Brief Announcement: Partial Reversal Acyclicity |
| title | Brief Announcement: Partial Reversal Acyclicity |
| title_full | Brief Announcement: Partial Reversal Acyclicity |
| title_fullStr | Brief Announcement: Partial Reversal Acyclicity |
| title_full_unstemmed | Brief Announcement: Partial Reversal Acyclicity |
| title_short | Brief Announcement: Partial Reversal Acyclicity |
| title_sort | brief announcement partial reversal acyclicity |
| url | http://hdl.handle.net/1721.1/73185 https://orcid.org/0000-0003-3045-265X https://orcid.org/0000-0003-1261-6681 |
| work_keys_str_mv | AT radevatsvetomira briefannouncementpartialreversalacyclicity AT lynchnancyann briefannouncementpartialreversalacyclicity |