Distributed algorithms for naming anonymous processes
Başlık çevirisi mevcut değil.
- Tez No: 403020
- Danışmanlar: DOÇ. DR. BOGDAN S. CHLEBUS
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2016
- Dil: İngilizce
- Üniversite: Unıversıty Of Colorado At Denver
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Özet yok.
Özet (Çeviri)
We investigate anonymous processors computing in a synchronous manner and communicating via read-write shared memory. This system is known as a parallel random access machine (PRAM). It is parameterized by a number of processors n and a number of shared memory cells. We consider the problem of assigning unique integer names from the interval [1; n] to all n processors of a PRAM. We develop algorithms for each of the eight speci c cases determined by which of the following independent properties hold: (1) concurrently attempting to write distinct values into the same memory cell either is allowed or not, (2) the number of shared variables either is unlimited or it is a constant independent of n, and (3) the number of processors n either is known or it is unknown. Our algorithms terminate almost surely, they are Las Vegas when n is known, they are Monte Carlo when n is not known.We show lower bounds on time, depending on whether the amounts of shared memory are constant or unlimited. In view of these lower bounds, all the Las Vegas algorithms we develop are asymptotically optimal with respect to their expected time, as determined by the available shared memory. Our Monte Carlo algorithms are correct with probabilities that are 1 n (1), which is best possible when terminating almost surely and using O(n log n) random bits. We also consider a communication channel in which the only possible communication mode is transmitting beeps, which reach all the nodes instantaneously. The algorithmic goal is to randomly assign names to the anonymous nodes in such a manner that the names make a contiguous segment of positive integers starting from 1. The algorithms are provably optimal with respect to the expected time O(n log n), the number of used random bits O(n log n), and the probability of error.
Benzer Tezler
- Çoklu etmen ortamında nesne tabanlı dağıtık bellek paylaşımı
Distributed object sharing in the multi-agent environment
METEHAN PATACI
Yüksek Lisans
Türkçe
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. NADİA ERDOĞAN
- How cryptographic implementations affect mobile agent systems
Şifreleme gerçekleştirmelerinin gezgin aracı internet sistemlerini nasıl etkilediği
İSMAİL ULUKUŞ
Yüksek Lisans
İngilizce
2003
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiSistem ve Kontrol Mühendisliği Ana Bilim Dalı
PROF. DR. EMİN ANARIM
- Distributed detection algorithms for parallel and hierarchical wireless sensor networks
Paralel ve hiyerarşik telsiz duyarga ağları için dağıtık sezimleme algoritmaları
KAYHAN ERİTMEN
Yüksek Lisans
İngilizce
2008
Elektrik ve Elektronik MühendisliğiSabancı ÜniversitesiMühendislik ve Doğa Bilimleri Ana Bilim Dalı
DOÇ. DR. MEHMET KESKİNÖZ
- Distributed localization algorithms for target tracking in wireless sensor networks
Telsiz algılayıcı ağlarda hedef takibi için dağıtık yer belirleme algoritmaları
TOLGA TOLGAY
Yüksek Lisans
İngilizce
2009
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Bölümü
PROF. CEM ERSOY
- Genetic algorithms for distributed database design and distributed database query optimization
Dağınık veritabanı tasarımı için genetik algoritma ve dağınık veritabanı sorgu optimizasyonu
ENDER SEVİNÇ
Doktora
İngilizce
2009
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. AHMET COŞAR