Algoritma "Bad apple", atau memproses crash kotak pasir bersama

9

Saya mencari algoritme untuk menangani masalah berikut, yang saya (untuk saat ini) menyebut algoritma "apel buruk".

Masalah

  • Saya memiliki N proses yang berjalan di kotak pasir M, di mana N >> M.
  • Tidak praktis untuk memberikan setiap proses kotak pasirnya sendiri.
  • Setidaknya salah satu dari proses tersebut berperilaku buruk, dan menjatuhkan seluruh kotak pasir, sehingga membunuh semua proses lainnya di kotak pasir yang sama.

Jika itu adalah satu proses berperilaku buruk, maka saya bisa menggunakan pembelahan sederhana untuk meletakkan setengah dari proses dalam satu kotak pasir, dan setengah di kotak pasir lain, sampai saya menemukan pelakunya.

Pertanyaan

Jika lebih dari satu proses berperilaku buruk - termasuk kemungkinan bahwa mereka semua berperilaku buruk - apakah algoritma naif ini "bekerja"? Apakah dijamin bekerja dalam batas yang masuk akal?

Penyederhanaan

Demi argumen, mari kita asumsikan bahwa proses yang buruk menjatuhkan kotak pasirnya secara instan, dan proses yang baik tidak pernah terjadi.

algorithms Roger Lipscombe
sumber
Seberapa terjaminkah proses berperilaku buruk akan menurunkan kotak pasir? Maksud saya - bisakah kita mengasumsikan waktu yang terbatas ketika kita tahu pasti bahwa kotak pasir hanya menjalankan proses "bersih" karena tidak macet?
SF.
Sayangnya tidak: fakta bahwa kotak pasir tidak mogok selama 5 menit tidak berarti bahwa semua proses berperilaku baik, tetapi itu memberi kita lebih percaya diri akan fakta itu.
Roger Lipscombe
... tetapi untuk keperluan pertanyaan ini, kami dapat memperkirakan dengan memberikan waktu yang terbatas, saya kira.
Roger Lipscombe
Anda harus melakukan atomisasi apa yang Anda anggap sebagai proses "lulus" dan "gagal". Jika berjalan 5 menit tanpa gagal, secara teknis masih bisa menjadi apel yang buruk, tetapi seperti masalah penghentian, Anda tidak akan pernah memiliki kepastian 100% ketika melewati tanpa membuat garis keras di pasir.
Neil
Sepertinya Anda berada di jalur yang benar. Jika ada banyak proses dan banyak apel yang rusak, maka Anda mungkin harus menggunakan nilai M yang besar, atau kelompok yang tidak rata sehingga Anda dapat mengisolasi apel yang dikenal baik, lalu simpan yang dikenal baik di satu kotak pasir dan terus membagi proses yang tidak diketahui antara kotak pasir Anda yang lain sampai Anda telah mengidentifikasi individu-individu tersebut. Semakin banyak kotak pasir yang Anda miliki, semakin cepat ini akan pergi. Seperti yang ditunjukkan oleh @Neil, ini adalah O besar dari basis log M dari algoritma N, jadi meningkatkan M akan memotong percobaan Anda.
GlenPeterson

Jawaban:

2

Jika Anda menemukan satu apel buruk, maka Anda dapat menerapkan algoritme:

  1. Bagilah N menjadi kelompok M
  2. Lakukan tes pada setiap kelompok.
  3. Jika ukuran grup lebih besar dari 1, kembali ke langkah 1, ganti N dengan jumlah item dalam grup buruk.

Demikian juga, jika Anda menemukan satu apel "baik", maka algoritma yang sama berlaku, tetapi menemukan kelompok yang baik.

Algoritma ini memiliki tingkat kinerja O (log_M (N)) tetapi tergantung pada kenyataan bahwa hanya ada satu apel yang buruk.

Jika Anda tidak tahu berapa banyak apel baik / buruk, maka Anda bisa menggunakan algoritma berikut:

For each M processes in N
  Test M processes

Ini adalah skenario kasus terburuk, tetapi ini berjalan dalam O(N/M)waktu (atau O(N)tergantung pada apakah Anda menganggap lulus tunggal sebagai tes tunggal atau sebagai kumpulan tes yang dilakukan secara paralel). Semua hal dipertimbangkan, ini bukan pendekatan yang buruk dengan cara apa pun.

Mungkin ada algoritma yang berkinerja lebih baik dari ini, tetapi mengharuskan Anda tahu berapa banyak apel buruk / apel baik yang ada dalam kelompok. Tidak mengetahui faktor ini, sementara saya tidak dapat membuktikannya, saya berani bertaruh bahwa Anda tidak dapat melakukan lebih baik daripada algoritma yang disebutkan di atas.

Semoga itu bisa membantu!

Sunting : Dari perspektif praktis, saya memahami bahwa beberapa operasi ini tidak mudah dilakukan. Itu benar, bagaimanapun, kenyataan yang disayangkan adalah bahwa Anda tidak dapat menentukan apel buruk hanya dari mana proses berjalan di kotak pasir yang berjalan pada saat itu tanpa setidaknya untuk mengaktifkan atau menonaktifkan proses. Jika pertanyaannya berkaitan dengan algoritma, saya pikir saya telah menjawabnya. Jika pertanyaannya berkaitan dengan bagaimana menghadapi situasi seperti ini, maka mungkin pertanyaannya akan lebih cocok untuk pengguna super SE.

Neil
sumber
1
Sayangnya, saya tidak bisa "menguji" prosesnya; yang saya tahu adalah bahwa salah satu kotak pasir jatuh, dan itu disebabkan oleh satu atau lebih proses di dalamnya.
Roger Lipscombe
1
Masalahnya adalah, setelah membagi dua set, kedua partisi bisa memiliki apel yang buruk di dalamnya. Yang membuat saya berpikir bahwa saya membutuhkan lebih dari satu partisi sederhana ...
Roger Lipscombe
@RogerLipscombe Anda mencoba menerapkan algoritme ke skenario dunia nyata. Tentu saja Anda tidak akan dapat menguji proses satu per satu, dan mungkin terbukti sulit untuk menguji proses ini pada mesin yang berbeda, namun, jika Anda ingin membahas ini, Anda akan harus menemukan cara satu atau lain cara. Jika Anda memasukkan variabel yang tidak dapat diselesaikan, Anda tidak akan dapat menemukan algoritma yang dapat secara akurat menunjukkan apel buruk.
Neil
OK, jadi dengan "tes", Anda hanya berarti "biarkan mereka berjalan cukup lama untuk percaya diri" ...?
Roger Lipscombe
@RogerLipscombe saya kira begitu. Mungkin butuh lebih banyak waktu, tetapi kaulah yang harus mencari tahu berapa lama menunggu. Mengetahui hal itu dan mengikuti algoritme ini, secara teknis Anda bisa mengetahui ada dan semua apel buruk. Namun, mungkin lebih cepat untuk hanya melihat log kejadian windows untuk crash.
Neil