Linearizing peer-to-peer systems with Oracles
We study distributed linearization or topological sorting in peer-to-peer networks. We define strict and eventual variants of the problem. We consider these problems restricted to existing peer identifiers or without this restriction. None of these variants are solvable in the asynchronous message-p...
| Main Authors: | , , |
|---|---|
| Format: | Proceeding Paper |
| Language: | English |
| Published: |
Springer
2013
|
| Subjects: | |
| Online Access: | http://irep.iium.edu.my/33051/ http://irep.iium.edu.my/33051/1/linearizingp2pwithoracles.pdf |
| _version_ | 1848780677282004992 |
|---|---|
| author | Mohd. Nor, Rizal Nesterenko, Mikhail Tixeuil, Sébastien |
| author_facet | Mohd. Nor, Rizal Nesterenko, Mikhail Tixeuil, Sébastien |
| author_sort | Mohd. Nor, Rizal |
| building | IIUM Repository |
| collection | Online Access |
| description | We study distributed linearization or topological sorting in peer-to-peer networks. We define strict and eventual variants of the problem. We consider these problems restricted to existing peer identifiers or without this restriction. None of these variants are solvable in the asynchronous message-passing system model. We define a collection of oracles and prove which oracle combination is necessary to enable a solution for each variant of the linearization problem. We then present a linearization algorithm. We prove that this algorithm and a specific combination of the oracles solves each stated variant of the linearization problem. |
| first_indexed | 2025-11-14T15:37:28Z |
| format | Proceeding Paper |
| id | iium-33051 |
| institution | International Islamic University Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T15:37:28Z |
| publishDate | 2013 |
| publisher | Springer |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | iium-330512015-12-18T13:56:59Z http://irep.iium.edu.my/33051/ Linearizing peer-to-peer systems with Oracles Mohd. Nor, Rizal Nesterenko, Mikhail Tixeuil, Sébastien QA75 Electronic computers. Computer science We study distributed linearization or topological sorting in peer-to-peer networks. We define strict and eventual variants of the problem. We consider these problems restricted to existing peer identifiers or without this restriction. None of these variants are solvable in the asynchronous message-passing system model. We define a collection of oracles and prove which oracle combination is necessary to enable a solution for each variant of the linearization problem. We then present a linearization algorithm. We prove that this algorithm and a specific combination of the oracles solves each stated variant of the linearization problem. Springer 2013 Proceeding Paper PeerReviewed application/pdf en http://irep.iium.edu.my/33051/1/linearizingp2pwithoracles.pdf Mohd. Nor, Rizal and Nesterenko, Mikhail and Tixeuil, Sébastien (2013) Linearizing peer-to-peer systems with Oracles. In: 15th Internationl Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2013), 13-16 Nov 2013, Osaka. http://dx.doi.org/10.1007/978-3-319-03089-0_16 10.1007/978-3-319-03089-0_16 |
| spellingShingle | QA75 Electronic computers. Computer science Mohd. Nor, Rizal Nesterenko, Mikhail Tixeuil, Sébastien Linearizing peer-to-peer systems with Oracles |
| title | Linearizing peer-to-peer systems with Oracles |
| title_full | Linearizing peer-to-peer systems with Oracles |
| title_fullStr | Linearizing peer-to-peer systems with Oracles |
| title_full_unstemmed | Linearizing peer-to-peer systems with Oracles |
| title_short | Linearizing peer-to-peer systems with Oracles |
| title_sort | linearizing peer-to-peer systems with oracles |
| topic | QA75 Electronic computers. Computer science |
| url | http://irep.iium.edu.my/33051/ http://irep.iium.edu.my/33051/ http://irep.iium.edu.my/33051/ http://irep.iium.edu.my/33051/1/linearizingp2pwithoracles.pdf |