Brooks–Iyengar algorithm
બ્રૂક્સ-આયંગર અલ્ગોરિધમ અથવા ફ્યુઝસીપીએ અલ્ગોરિધમ અથવા બ્રૂક્સ-આયંગર હાઇબ્રિડ અલ્ગોરિધમ એ એક વિતરિત અલ્ગોરિધમ છે જે ખામીયુક્ત સેન્સરની હાજરીમાં પણ વિતરિત સેન્સર નેટવર્ક દ્વારા લેવામાં આવેલા અંતરાલ માપનની ચોકસાઈ અને ચોકસાઈ બંનેમાં સુધારો કરે છે. સેન્સર નેટવર્ક દરેક અન્ય નોડ સાથે દરેક નોડ પર માપેલા મૂલ્ય અને ચોકસાઈ મૂલ્યનું વિનિમય કરીને આ કરે છે, અને એકત્રિત કરેલા તમામ મૂલ્યોમાંથી ચોકસાઈ શ્રેણી અને સમગ્ર નેટવર્ક માટે માપેલા મૂલ્યની ગણતરી કરે છે. જો કેટલાક સેન્સરમાંથી કેટલીક માહિતી ખામીયુક્ત હોય તો પણ સેન્સર નેટવર્કમાં ખામી નહીં આવે. અલ્ગોરિધમ દોષ-સહિષ્ણુ અને વિતરિત છે. તેનો ઉપયોગ સેન્સર ફ્યુઝન પદ્ધતિ તરીકે પણ થઈ શકે છે. આ અલ્ગોરિધમની ચોકસાઈ અને ચોકસાઈ 2016 માં સાબિત થઈ છે. પૃષ્ઠભૂમિ ઘોંઘાટીયા ડેટાની હાજરીમાં વિતરિત નિયંત્રણ માટે બ્રૂક્સ-આયંગર હાઇબ્રિડ અલ્ગોરિધમ સેન્સર ફ્યુઝન સાથે બીઝેન્ટાઇન કરારને જોડે છે. તે સેન્સર ફ્યુઝન અને બીઝેન્ટાઇન ફોલ્ટ ટોલરન્સ વચ્ચેના અંતરને દૂર કરે છે. આ મૂળભૂત અલ્ગોરિધમે પ્રથમ વખત આ અલગ-અલગ ક્ષેત્રોને એકીકૃત કર્યા. અનિવાર્યપણે, તે મહાની અને શ્નાઇડરના ફાસ્ટ કન્વર્જન્સ અલ્ગોરિધમ (એફસીએ) સાથે અંદાજિત સમજૂતી માટે ડોલેવના અલ્ગોરિધમને જોડે છે. અલ્ગોરિધમ એન પ્રોસેસિંગ એલિમેન્ટ્સ (પીઇ) ધારે છે, જેમાંથી ટી ખામીયુક્ત છે અને દુર્ભાવનાપૂર્ણ વર્તન કરી શકે છે. તે ક્યાં તો અંતર્ગત અચોક્કસતા અથવા ઘોંઘાટ (જે અજ્ઞાત હોઈ શકે છે) સાથે વાસ્તવિક મૂલ્યો, અથવા અપ્રિયોરી વ્યાખ્યાયિત અનિશ્ચિતતા સાથે વાસ્તવિક મૂલ્ય, અથવા અંતરાલને ઇનપુટ તરીકે લે છે. અલ્ગોરિધમનો આઉટપુટ એ સ્પષ્ટ રીતે નિર્દિષ્ટ ચોકસાઈ સાથેનું વાસ્તવિક મૂલ્ય છે. અલ્ગોરિધમ O (NlogN) માં ચાલે છે જ્યાં N એ PE ની સંખ્યા છે. ક્રુસેડરના કન્વર્જન્સ અલ્ગોરિધમ (સી. સી. એ.) ને અનુરૂપ આ અલ્ગોરિધમમાં ફેરફાર કરવો શક્ય છે, જો કે, બેન્ડવિડ્થની જરૂરિયાત પણ વધશે. અલ્ગોરિધમનો વિતરણ નિયંત્રણ, સોફ્ટવેર વિશ્વસનીયતા, ઉચ્ચ-પ્રદર્શન કમ્પ્યુટિંગ વગેરેમાં ઉપયોગો ધરાવે છે. એલ્ગોરિધમ બ્રૂક્સ-આયંગર એલ્ગોરિધમ ડિસ્ટ્રિબ્યુટેડ સેન્સર નેટવર્કના દરેક પ્રોસેસિંગ એલિમેન્ટ (PE) માં ચલાવવામાં આવે છે. દરેક PE નેટવર્કમાં અન્ય તમામ PE સાથે તેમના માપેલા અંતરાલનું આદાનપ્રદાન કરે છે. "ફ્યુઝ્ડ" માપ એ મળેલા પ્રદેશોના મધ્યબિંદુઓની ભારિત સરેરાશ છે. બ્રૂક્સ-આયંગર અલ્ગોરિધમનો નક્કર પગલાઓ આ વિભાગમાં દર્શાવવામાં આવ્યા છે. દરેક PE અલગથી અલ્ગોરિધમ કરે છેઃ ઇનપુટઃ PE k દ્વારા PE i ને મોકલવામાં આવેલ માપ એક બંધ અંતરાલ છે, આઉટપુટઃ PE i ના આઉટપુટમાં એક બિંદુ અંદાજ અને એક અંતરાલ અંદાજ PE i અન્ય તમામ PE થી માપ મેળવે છે. એકત્રિત કરેલા માપના જોડાણને આંતરછેદ કરતા માપની સંખ્યાના આધારે પરસ્પર વિશિષ્ટ અંતરાલોમાં વિભાજીત કરો, જેને અંતરાલના વજન તરીકે ઓળખવામાં આવે છે. ઓછા વજનવાળા અંતરાલો દૂર કરો, ખામીયુક્ત PE ની સંખ્યા ક્યાં છે જો ત્યાં L અંતરાલો બાકી હોય, તો ચાલો બાકીના અંતરાલોના સમૂહને સૂચવીએ. આપણી પાસે અંતરાલ છે અને તે અંતરાલ સાથે સંકળાયેલ વજન છે. આપણે પણ ધારીએ છીએ. PE i ના બિંદુ અંદાજની ગણતરી કરો અને અંતરાલ અંદાજ ઉદાહરણ છેઃ 5 PE નું ઉદાહરણ ધ્યાનમાં લો, જેમાં PE 5 () અન્ય PE ને ખોટા મૂલ્યો મોકલી રહ્યું છે અને તે બધા મૂલ્યોની આપ-લે કરે છે. દ્વારા પ્રાપ્ત મૂલ્યો આગામી કોષ્ટકમાં છે. આપણે આ અંતરાલોની ભારિત પ્રદેશ આકૃતિ (ડબલ્યુ. આર. ડી.) દોરીએ છીએ, પછી આપણે એલ્ગોરિધમ અનુસાર પી. ઈ. 1 માટે નક્કી કરી શકીએ છીએઃ જેમાં અંતરાલો હોય છે જ્યાં ઓછામાં ઓછા 4 (= = 5−1) માપ છેદે છે. PE 1 નું આઉટપુટ સમાન છે અને અંતરાલ અંદાજ સમાન છે, આપણે 5 PE ના તમામ ઇનપુટ્સ અને પરિણામો મેળવી શકીએ છીએઃ સંબંધિત અલ્ગોરિધમ્સ 1982 બીઝેન્ટાઇન સમસ્યાઃ બે જનરલ્સની સમસ્યાના વિસ્તરણ તરીકે બીઝેન્ટાઇન સામાન્ય સમસ્યાને દ્વિસંગી સમસ્યા તરીકે જોઈ શકાય છે. 1983 અંદાજિત સર્વસંમતિઃ આ પદ્ધતિ સમૂહમાંથી કેટલાક મૂલ્યોને દૂર કરે છે જેમાં સ્કેલર્સથી સહનશીલ ખામીયુક્ત ઇનપુટ્સનો સમાવેશ થાય છે. 1985 ચોક્કસ સર્વસંમતિઃ આ પદ્ધતિ ઇનપુટ તરીકે સ્કેલરનો પણ ઉપયોગ કરે છે. 1996 બ્રૂક્સ-આયંગર અલ્ગોરિધમઃ આ પદ્ધતિ અંતરાલો પર આધારિત છે. 2013 બીઝેન્ટાઇન વેક્ટર સર્વસંમતિઃ પદ્ધતિ ઇનપુટ તરીકે વેક્ટરનો ઉપયોગ કરે છે. 2013 બહુ-પરિમાણીય કરારઃ આ પદ્ધતિ વેક્ટરનો ઉપયોગ ઇનપુટ તરીકે પણ કરે છે જ્યારે અંતરનું માપ અલગ હોય છે. અમે અંતરાલ ઇનપુટ્સ સાથે વ્યવહાર કરવા માટે અંદાજિત સર્વસંમતિ (સ્કેલર-આધારિત), બ્રૂક્સ-આયંગર અલ્ગોરિધમ (અંતરાલ-આધારિત) અને બીઝેન્ટાઇન વેક્ટર સર્વસંમતિ (વેક્ટર-આધારિત) નો ઉપયોગ કરી શકીએ છીએ, અને પેપર સાબિત કરે છે કે બ્રૂક્સ-આયંગર અલ્ગોરિધમ અહીં શ્રેષ્ઠ છે. એપ્લિકેશન બ્રૂક્સ-આયંગર અલ્ગોરિધમ એ એક નિર્ણાયક કાર્ય છે અને ડિસ્ટ્રિબ્યુટેડ સેન્સિંગમાં એક મુખ્ય સીમાચિહ્નરૂપ છે, અને તેનો ઉપયોગ ઘણા રીડન્ડન્સી દૃશ્યો માટે દોષ સહિષ્ણુ ઉકેલ તરીકે થઈ શકે છે. ઉપરાંત, કોઈપણ નેટવર્કિંગ સિસ્ટમમાં અમલ અને એમ્બેડ કરવું સરળ છે. 1996 માં, વધુ ચોકસાઈ અને ચોકસાઇ પ્રદાન કરવા માટે મિનિક્સમાં અલ્ગોરિધમનો ઉપયોગ કરવામાં આવ્યો હતો, જે આરટી-લિનક્સના પ્રથમ સંસ્કરણના વિકાસ તરફ દોરી જાય છે. 2000 માં, અલ્ગોરિધમ DARPA SensIT પ્રોગ્રામના ડિસ્ટ્રિબ્યુટેડ ટ્રેકિંગ પ્રોગ્રામ માટે પણ કેન્દ્રિય હતું. બહુવિધ સેન્સરમાંથી ધ્વનિ, ધરતીકંપ અને ગતિ શોધ વાંચનને જોડવામાં આવે છે અને વિતરિત ટ્રેકિંગ સિસ્ટમમાં આપવામાં આવે છે. આ ઉપરાંત, તેનો ઉપયોગ બી. બી. એન. ટેક્નોલોજીસ, બી. એ. ઈ. સિસ્ટમ્સ, પેન સ્ટેટ એપ્લાઇડ રિસર્ચ લેબ (એ. આર. એલ.) અને યુ. એસ. સી./આઈ. એસ. આઈ. દ્વારા તૈયાર કરવામાં આવેલી એપ્લિકેશનમાં વિજાતીય સેન્સર ફીડ્સને જોડવા માટે કરવામાં આવ્યો હતો. યુકેના સંરક્ષણ ઉત્પાદક થેલ્સ ગ્રૂપે તેની ગ્લોબલ ઓપરેશનલ એનાલિસિસ લેબોરેટરીમાં આ કાર્યનો ઉપયોગ કર્યો હતો. તે રેથિયોનના કાર્યક્રમો પર લાગુ થાય છે જ્યાં ઘણી સિસ્ટમોને અવિશ્વસનીય સેન્સર નેટવર્કમાંથી વિશ્વસનીય ડેટા કાઢવાની જરૂર હોય છે, આ સેન્સરની વિશ્વસનીયતામાં સુધારો કરવા માટે વધતા રોકાણને મુક્તિ આપે છે. ઉપરાંત, આ અલ્ગોરિધમ વિકસાવવામાં સંશોધન યુ. એસ. નૌકાદળ દ્વારા તેના દરિયાઇ ડોમેન જાગૃતિ સોફ્ટવેરમાં ઉપયોગમાં લેવાતા સાધનોમાં પરિણમે છે. શિક્ષણમાં, યુનિવર્સિટી ઓફ વિસ્કોન્સિન, પર્ડ્યુ, જ્યોર્જિયા ટેક, ક્લેમ્સન યુનિવર્સિટી, યુનિવર્સિટી ઓફ મેરીલેન્ડ વગેરે જેવા શિક્ષણ વર્ગોમાં બ્રૂક્સ-આયંગર અલ્ગોરિધમનો વ્યાપકપણે ઉપયોગ કરવામાં આવે છે. સેન્સર નેટવર્કના ક્ષેત્ર ઉપરાંત, સમય-પ્રેરિત આર્કિટેક્ચર, સાયબર-ફિઝિકલ સિસ્ટમ્સની સલામતી, ડેટા ફ્યુઝન, રોબોટ કન્વર્જન્સ, ઉચ્ચ પ્રદર્શન કમ્પ્યુટિંગ, સોફ્ટવેર/હાર્ડવેર વિશ્વસનીયતા, આર્ટિફિશિયલ ઇન્ટેલિજન્સ સિસ્ટમ્સમાં એન્સેમ્બલ લર્નિંગ જેવા અન્ય ક્ષેત્રોને પણ બ્રૂક્સ-આયંગર અલ્ગોરિધમનો લાભ મળી શકે છે. અલ્ગોરિધમ લાક્ષણિકતાઓ ખામીયુક્ત PEs સહન કરે છે <N/3 મહત્તમ ખામીયુક્ત PEs <2N/3 જટિલતા = O (N log N) નેટવર્ક બેન્ડવિડ્થનો ક્રમ = O (N) કન્વર્જન્સ = 2t/N ચોકસાઈ = ચોકસાઇ માટે ઇનપુટ દ્વારા મર્યાદિત Iterates = ઘણીવાર ચોકસાઈ પર ચોકસાઈ = ચોકસાઈ પર કોઈ ચોકસાઈ નહીં = કોઈ વિતરણ સેન્સર નેટવર્ક સેન્સર ફ્યુઝન ફોલ્ટ ટોલરન્સ સર્વસંમતિ (કમ્પ્યુટર વિજ્ઞાન) ચંદ્ર-તુએગ સર્વસંમતિ અલ્ગોરિધમ પેક્સોસ સર્વસંમતિ પ્રોટોકોલ રાફ્ટ સર્વસંમતિ અલ્ગોરિધમ માર્ઝુલોના અલ્ગોરિધમ ઇન્ટરસેક્શન અલ્ગોરિધમ બે જનરલ્સ પ્રોબ્લેમ એવોર્ડ્સ અને માન્યતા બ્રૂક્સ આયંગર અલ્ગોરિધમ ડૉ. બ્રૂક્સ અને ડૉ. એસ. આયંગરના શોધકોને પ્રાપ્ત થઈ ઉચ્ચ અસર સંશોધન અને આ કાર્યએ યુએસ સરકારના અસંખ્ય કાર્યક્રમો અને વ્યાપારી ઉત્પાદનોને કેવી રીતે પ્રભાવિત કર્યા છે. ડૉ. એસ. એસ. આયંગર પ્રોફેસર સ્ટીવ યાઉ, આઈ. ઈ. ઈ. ઈ. ડૉ. એસ. એસ. આયંગર પાસેથી તેમના વિદ્યાર્થી ડૉ. બ્રૂક્સ રેફરન્સ ડિસ્ટ્રિબ્યુટેડ કમ્પ્યુટિંગ પ્રોબ્લેમ્સ ફોલ્ટ ટોલરન્સ થિયરી ઓફ કમ્પ્યુટેશન સાથે પુરસ્કાર પ્રાપ્ત કરી રહ્યા છે.