Naming in Multichannel with Beeps in the Strong Model
In this paper, a system of anonymous processes is considered that communicates with beeps through multiple channels in a synchronous communication model. In beeping channels, processes are limited to hearing either a beep or a silence from the channel with no collision detection. A strong model is a...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-10-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/10/20/7164 |
| _version_ | 1797550937362923520 |
|---|---|
| author | Layla S. Aldawsari Tom Altman |
| author_facet | Layla S. Aldawsari Tom Altman |
| author_sort | Layla S. Aldawsari |
| collection | DOAJ |
| description | In this paper, a system of anonymous processes is considered that communicates with beeps through multiple channels in a synchronous communication model. In beeping channels, processes are limited to hearing either a beep or a silence from the channel with no collision detection. A strong model is assumed in which a process can beep on any single channel and listen on any specific channel during a single round. The goal is to develop distributed naming algorithms for two models where the number of processes is either known or unknown. A Las Vegas algorithm was developed for naming anonymous processes when the number of processes is known. This algorithm has an optimal time complexity of <inline-formula><math display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mrow><mo>(</mo><mi>n</mi><mo form="prefix">log</mo><mi>n</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> rounds and uses <inline-formula><math display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mrow><mo>(</mo><mi>n</mi><mo form="prefix">log</mo><mi>n</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> random bits, where <i>n</i> is the number of processes for the largest group. For the model with an unknown number of processes, a Monte Carlo algorithm was developed, which has an optimal running time of <inline-formula><math display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mrow><mo>(</mo><mi>n</mi><mo form="prefix">log</mo><mi>n</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> rounds and a probability of success that is at least <inline-formula><math display="inline"><semantics><mrow><mn>1</mn><mo>−</mo><msup><mfrac><mn>1</mn><mn>2</mn></mfrac><mrow><mi mathvariant="sans-serif">Ω</mi><mrow><mo>(</mo><mo form="prefix">log</mo><mi>n</mi><mo>)</mo></mrow></mrow></msup></mrow></semantics></math></inline-formula>. The algorithms solve the naming problem in new models where processes communicate through multiple channels. |
| first_indexed | 2024-03-10T15:37:33Z |
| format | Article |
| id | doaj.art-7d2ab37568674032b0b1a053f9de07cc |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-10T15:37:33Z |
| publishDate | 2020-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-7d2ab37568674032b0b1a053f9de07cc2023-11-20T17:07:22ZengMDPI AGApplied Sciences2076-34172020-10-011020716410.3390/app10207164Naming in Multichannel with Beeps in the Strong ModelLayla S. Aldawsari0Tom Altman1Department of Computer Science and Engineering, College of Engineering, Design and Computing, University of Colorado Denver, Denver, CO 80204, USADepartment of Computer Science and Engineering, College of Engineering, Design and Computing, University of Colorado Denver, Denver, CO 80204, USAIn this paper, a system of anonymous processes is considered that communicates with beeps through multiple channels in a synchronous communication model. In beeping channels, processes are limited to hearing either a beep or a silence from the channel with no collision detection. A strong model is assumed in which a process can beep on any single channel and listen on any specific channel during a single round. The goal is to develop distributed naming algorithms for two models where the number of processes is either known or unknown. A Las Vegas algorithm was developed for naming anonymous processes when the number of processes is known. This algorithm has an optimal time complexity of <inline-formula><math display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mrow><mo>(</mo><mi>n</mi><mo form="prefix">log</mo><mi>n</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> rounds and uses <inline-formula><math display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mrow><mo>(</mo><mi>n</mi><mo form="prefix">log</mo><mi>n</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> random bits, where <i>n</i> is the number of processes for the largest group. For the model with an unknown number of processes, a Monte Carlo algorithm was developed, which has an optimal running time of <inline-formula><math display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mrow><mo>(</mo><mi>n</mi><mo form="prefix">log</mo><mi>n</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> rounds and a probability of success that is at least <inline-formula><math display="inline"><semantics><mrow><mn>1</mn><mo>−</mo><msup><mfrac><mn>1</mn><mn>2</mn></mfrac><mrow><mi mathvariant="sans-serif">Ω</mi><mrow><mo>(</mo><mo form="prefix">log</mo><mi>n</mi><mo>)</mo></mrow></mrow></msup></mrow></semantics></math></inline-formula>. The algorithms solve the naming problem in new models where processes communicate through multiple channels.https://www.mdpi.com/2076-3417/10/20/7164anonymous processesnaming algorithmbeeping channelsdistributed naming |
| spellingShingle | Layla S. Aldawsari Tom Altman Naming in Multichannel with Beeps in the Strong Model Applied Sciences anonymous processes naming algorithm beeping channels distributed naming |
| title | Naming in Multichannel with Beeps in the Strong Model |
| title_full | Naming in Multichannel with Beeps in the Strong Model |
| title_fullStr | Naming in Multichannel with Beeps in the Strong Model |
| title_full_unstemmed | Naming in Multichannel with Beeps in the Strong Model |
| title_short | Naming in Multichannel with Beeps in the Strong Model |
| title_sort | naming in multichannel with beeps in the strong model |
| topic | anonymous processes naming algorithm beeping channels distributed naming |
| url | https://www.mdpi.com/2076-3417/10/20/7164 |
| work_keys_str_mv | AT laylasaldawsari naminginmultichannelwithbeepsinthestrongmodel AT tomaltman naminginmultichannelwithbeepsinthestrongmodel |