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: University of Colorado at Denver
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 119
Ö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
- Çok robotlu kapsama ve randevu için dağıtık algoritmalar
Distributed algorithms for multi robot rendezvous and coverage
DENİZ ÖZSOYELLER
Doktora
Türkçe
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiUluslararası Bilgisayar Ana Bilim Dalı
PROF. DR. KAYHAN ERCİYEŞ
DOÇ. DR. VOLKAN İŞLER
- Distributed algorithms based on fictitious play for near optimal sequential decision making
Başlık çevirisi yok
ESRA ŞİŞİKOĞLU
Doktora
İngilizce
2009
Endüstri ve Endüstri MühendisliğiUniversity of MichiganDOÇ. DR. MARINA A. EPELMAN
PROF. ROBERT L. SMITH
- Resilient distributed algorithms for solving linear algebraic equations in faulty networks
Doğrusal cebir denklemlerinin hatalı ağlarda çözümü için dirençli dağıtık algoritmalar
OĞUZHAN ÇİFTÇİ
Yüksek Lisans
İngilizce
2022
Elektrik ve Elektronik MühendisliğiBoğaziçi ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET AKAR