Geri Dön

Distributed algorithms for naming anonymous processes

Başlık çevirisi mevcut değil.

  1. Tez No: 403020
  2. Yazar: MUHAMMED TALO
  3. Danışmanlar: DOÇ. DR. BOGDAN S. CHLEBUS
  4. Tez Türü: Doktora
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2016
  8. Dil: İngilizce
  9. Üniversite: University of Colorado at Denver
  10. Enstitü: Yurtdışı Enstitü
  11. Ana Bilim Dalı: Belirtilmemiş.
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. Ç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

    Türkçe

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. NADİA ERDOĞAN

  2. 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

    İngilizce

    2003

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi Üniversitesi

    Sistem ve Kontrol Mühendisliği Ana Bilim Dalı

    PROF. DR. EMİN ANARIM

  3. Ç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

    Türkçe

    2015

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge Üniversitesi

    Uluslararası Bilgisayar Ana Bilim Dalı

    PROF. DR. KAYHAN ERCİYEŞ

    DOÇ. DR. VOLKAN İŞLER

  4. Distributed algorithms based on fictitious play for near optimal sequential decision making

    Başlık çevirisi yok

    ESRA ŞİŞİKOĞLU

    Doktora

    İngilizce

    İngilizce

    2009

    Endüstri ve Endüstri MühendisliğiUniversity of Michigan

    DOÇ. DR. MARINA A. EPELMAN

    PROF. ROBERT L. SMITH

  5. 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

    İngilizce

    2022

    Elektrik ve Elektronik MühendisliğiBoğaziçi Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    PROF. DR. MEHMET AKAR