Global Data Computation in a Dedicated Chordal Ring
Existing Global Data Computation (GDC) protocols for asynchronous systems are designed for fully connected networks. In this paper, we discuss GDC in a dedicated asynchronous chordal ring, a type of un-fully connected networks. The virtual links approach, which constructs t+1 (t<n) process-disjoi...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/30247 |
| _version_ | 1811088140555780096 |
|---|---|
| author | Wang, Xianbing Teo, Yong Meng |
| author_facet | Wang, Xianbing Teo, Yong Meng |
| author_sort | Wang, Xianbing |
| collection | MIT |
| description | Existing Global Data Computation (GDC) protocols for asynchronous systems are designed for fully connected networks. In this paper, we discuss GDC in a dedicated asynchronous chordal ring, a type of un-fully connected networks. The virtual links approach, which constructs t+1 (t<n) process-disjoint paths for each pair of processes without direct connection to tolerate failures (where t is the maximum number of processes that may crash and n is the total number of processes), can be applied to solve the GDC problem in the chordal but the virtual links approach incurs high message complexity. To reduce the high communication cost, we propose a non round-based GDC protocol for the asynchronous chordal ring with perfect failure detectors. The main advantage of our approach is that there is no notion of round, processes only send messages via direct connections and the implementation of failure detectors does not require process-disjoint paths. Analysis and comparison with the virtual links approach shows that our protocol reduces the message complexity significantly. |
| first_indexed | 2024-09-23T13:56:54Z |
| format | Article |
| id | mit-1721.1/30247 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:56:54Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | mit-1721.1/302472019-04-12T08:25:05Z Global Data Computation in a Dedicated Chordal Ring Wang, Xianbing Teo, Yong Meng data computation chordal rings perfect failure detector Existing Global Data Computation (GDC) protocols for asynchronous systems are designed for fully connected networks. In this paper, we discuss GDC in a dedicated asynchronous chordal ring, a type of un-fully connected networks. The virtual links approach, which constructs t+1 (t<n) process-disjoint paths for each pair of processes without direct connection to tolerate failures (where t is the maximum number of processes that may crash and n is the total number of processes), can be applied to solve the GDC problem in the chordal but the virtual links approach incurs high message complexity. To reduce the high communication cost, we propose a non round-based GDC protocol for the asynchronous chordal ring with perfect failure detectors. The main advantage of our approach is that there is no notion of round, processes only send messages via direct connections and the implementation of failure detectors does not require process-disjoint paths. Analysis and comparison with the virtual links approach shows that our protocol reduces the message complexity significantly. Singapore-MIT Alliance (SMA) 2005-12-14T19:17:36Z 2005-12-14T19:17:36Z 2006-01 Article http://hdl.handle.net/1721.1/30247 en Computer Science (CS) 293646 bytes application/pdf application/pdf |
| spellingShingle | data computation chordal rings perfect failure detector Wang, Xianbing Teo, Yong Meng Global Data Computation in a Dedicated Chordal Ring |
| title | Global Data Computation in a Dedicated Chordal Ring |
| title_full | Global Data Computation in a Dedicated Chordal Ring |
| title_fullStr | Global Data Computation in a Dedicated Chordal Ring |
| title_full_unstemmed | Global Data Computation in a Dedicated Chordal Ring |
| title_short | Global Data Computation in a Dedicated Chordal Ring |
| title_sort | global data computation in a dedicated chordal ring |
| topic | data computation chordal rings perfect failure detector |
| url | http://hdl.handle.net/1721.1/30247 |
| work_keys_str_mv | AT wangxianbing globaldatacomputationinadedicatedchordalring AT teoyongmeng globaldatacomputationinadedicatedchordalring |