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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Conference or Workshop Item |
| Language: | English |
| Published: |
Springer
2013
|
| Subjects: | |
| Online Access: | http://irep.iium.edu.my/33051/1/linearizingp2pwithoracles.pdf http://irep.iium.edu.my/33051/ http://dx.doi.org/10.1007/978-3-319-03089-0_16 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|